Making a distributed system, n=18 and beyond

[NailLegProcessorDivide]

I know @bertie2 and @datdenkikniet have also both also mentioned the possibility of a distributed system which the current DFS solutions should theoretically lend them self to extremely well.

This seems like something that comes with a lot of additional problems and would need some coordination between people to develop a concrete api as well as if we want to have at least basic guarantees for data integrity or security.

What I'm mainly asking is how would such a solution be arranged and does anyone have any experience with similar systems?

[datdenkikniet]

I think the basic building blocks we need look something like this:

1. Determine a size N that we wish to calculate.
2. A server has a set of positions P of some size S < N to hand out to clients (the size of P depends on the amount of clients we expect to serve, the transfer to compute time ratio, etc. There is no need for it to be fixed either, so long as there is something that ensures none of the transmitted positions are duplicated unknowingly).
3. Clients request set of starting positions P_c from the server.
4. Clients calculate the amount of children C_c of size N for each position in P_c.
5. Clients report P_c and the calculated C_c.
6. Server stores and/or sums all the results

This would only work exactly in this setup if all clients always complete their work and we always trust the computed values, of course. It'd need some extra things to make it "secure", like duplicating items in P across multiple P_c to double-check that the returned values are the same, and perhaps some sort of timeout. I think tackling the basic setup first will be challenge enough, though :)

In order to reduce upload bandwidth to the server(s) we could identify P_cs with some hash, so that the client doesn't have to re-upload it in it's entirety when reporting C_c.

If we ever get to a large enough load, we could store P in some sort of shared database and have multiple servers serving P_c, but I think it will be a while before we consume enough bandwidth that that starts becoming a concern.

I think doing all the transfers over HTTP is a decent idea, as it would make our life a lot easier and isn't likely to be the bottleneck.

[hidny]

@datdenkikniet
I like your idea, but I feel I should clarify that this problem is a little bit easier than what you described. Because the algorithm doesn't even need to hash the solutions, all the worker nodes have to do is send back the number of child solutions it found and that's it. Five hours of compute time can easily be summarized by a message like "For Starting shape P_c, I got 1001 solutions.". This system is what they call "Embarrassingly parallel".
https://en.wikipedia.org/wiki/Embarrassingly_parallel

EDIT: I have an over-engineered solution in Java that's probably not very good, but it got the job done:
https://github.com/hidny/MikeTsCubeCode/tree/main/src/MultiplePiecesHandler

EDIT2: I reread your comment and feel like I was too harsh. I like your ideas and think they're the way to go. The only thing I would change is having an agreed numbering for all of the P_c shapes instead of some hash.

[NailLegProcessorDivide]

I agree server throughput shouldnt be a problem. I think it would be nice to have a bit more feedback than "5 hours" (I know this was an example not necessarily a suggestion) of compute per worker but we could easilly distribute ~1-10 minute jobs to workers as either single polycubes to expand or a batch of a few polycubes at the scale of adoption I think we'll have.

1-10mins I think would also give a reasonable range of time for the server to assume the working is working on the problem before redistributing it if there was no response although this is more a question of how solved of a problem workers dropping in and out needs to be.

If bandwidth distributing solutions was a concern we could have a way for workers to store/generate a canonical ordered list of polycubes and enumerate them but as @hidny says I dont think that would be an issue even for a polycube format of 10s of KB(the largest Ive used)

[hidny]

@NailLegProcessorDivide Any update on this? I noticed that you created a PR, and I was wondering how it was going. Unfortunately, I won't be able to help with compute because all I have is an old laptop, and I'm a bit busy...

[NailLegProcessorDivide]

Hi, yes, I created a basic server and client that exchange jobs over a rest API mostly as a proof of concept, I havent worked on it in a little while but the code seemed to be correct in my testing.

I computed up to N=16 and it was correct (using my desktop and laptop as workers). I also have a copy of a debug print containing partial sums for the first 10% of N=18 but due to having just started a new job and working on other projects for a while I havent continued. I expect N=18 would take me around 2 weeks to complete (obviously lowered if there were other interested people joining in), I still plan to do this but wont be in a position to run my PC for that long for a few weeks as well.

Another issue for if people were interested in doing a collective distributed system is I have no easy way to host it (would be cheap on a VPS but again would only do with other people being interested).

Codewise its still a completely seperate codebase to the solutions in this repo it could be merged to some degree but I havent put any time into doing so yet

[hidny]

Hi NailLeg,
Thanks for the quick update, and congratulations on your new job!

[NailLegProcessorDivide]

Just got done running N=18, it was a lot quicker than I initially feared as it sped up over time due to how the first instance of polycubes worked. I think it took between 5 and 6 days (I ran it in a few chunks so its hard to have a more exact time).
assuming my code is correct including the python script I used to scrape the partial sums from the debug print I mentioned above.

My total was 3516009200564

gziped debug file (875MB decompressed text) with all partial sums here https://drive.google.com/file/d/1qQV5OrJnVBwkZ_c-XbF2l2L3JXGhoI_e/view?usp=sharing

That should be tied world record according to wikipedia and the first place not paywalled

[hidny]

Hi @NailLegProcessorDivide,

That's awesome! Congratulations! I actually think you're the first person to find that number. I looked at the paywalled paper and they were only concerned with a slightly easier version of the problem where the shapes can only be symmetric under translation.

This is the sequence of numbers they were after: https://oeis.org/A001931

This is the sequence of numbers you extended: https://oeis.org/A000162

When I have time, I'll look at some of your partial sums to verify it, but I think you got it! The number fits well within the pattern in the OEIS. There's a lot of options for what to do next including just taking 2 months to search for the solution to N=19, but I think I'll share those options later...

[hidny]

I decided not to share all my ideas about what can be done because that would be a huge post that I'm not interested in writing, and you're probably not interested in reading it either.
Instead I want to highlight a stretch goal that is slightly harder than just computing the solution for N=19:

1. Find the number of 3D shapes symmetric under 4D rotations (i.e. rotations and reflections)
   * Sequence can be found here: https://oeis.org/A038119
   * I already have a proof-of-concept program that does this. All you need to do is add the 24 nudges associated with the reflective symmetries...

[snowmanam2]

Sorry to interject here, but I just want to confirm the correctness of NailLegProcessorDivide's result. I, too, got 3516009200564 for N=18, while simultaneously producing 457409613979 for N=17. Results for N=13 through N=16 were in line with Kevin Gong's 3-d rotation numbers.

For reference, I ran my own server on Vercel with a wide variety of my own hardware over the last 2 weeks to generate N=18 from a common N=12 cache file, and it just finished this morning. My code is a bit different, but it seems we have the same results.

[pbj4]

I can also confirm the value of 3516009200564 for the n = 18 polycubes with rotations.

Additionally, my implementation did the version including reflections at the same time and it got the value of 1758309223457 using a total run time of 2d22h. The extra results from n = 10 to n = 17 agree with the ones found by Kevin Gong, 457409613979 for n = 17 rotation, and my previous value of 228779330204 for n = 17 reflection at #52.

[pbj4]

I've just finished running n = 19 and got the following results (r is rotation and p is rotation + reflection):

n: 11, r: 2522522, p: 1279537
n: 12, r: 18598427, p: 9371094
n: 13, r: 138462649, p: 69513546
n: 14, r: 1039496297, p: 520878101
n: 15, r: 7859514470, p: 3934285874
n: 16, r: 59795121480, p: 29915913663
n: 17, r: 457409613979, p: 228779330204
n: 18, r: 3516009200564, p: 1758309223457
n: 19, r: 27144143923583, p: 13573319825615

The results for n = 11 to 18 agree with all previously found values, and the values 27144143923583 and 13573319825615 for n = 19 should be new unless I've made a mistake somewhere.

The total run time was 17d5h4m7s which is faster than expected from my n = 18 run but that's just because I obtained more hardware. My peak rotation polycube enumeration rate was 30M/s and I averaged 21M/s overall.

This will be my final contribution to this project. If anyone else has significantly more computing power or time feel free to use my code to run n = 20. Big thanks to Computerphile for popularizing the problem and everyone in the community who shared optimizations and algorithms; this would not have been possible without all of your contributions.

[mikepound]

This is fantastic! 😁