What we did was take a very slow algorithm and a large input and parallelize it across multiple computers. What's more interesting is we ran the code in people's web browsers. Most projects of this nature require you to download and install software. This project requires you to just open a web browser tab.
The most interesting problems we ran into were the following:
1) We realized that we needed to scale based on how many people had their web browser's connected. Our application distributes portions of the algorithm to solve based on how many web browsers nodes are available at start. This means that the algorithm will make its best attempt to always make sure that the portions are divided evenly.
2) We realized that due to the fact that some computers finished their tasks slower than others, those slower computers were a bottleneck for the finishing the algorithm. So we implemented a task queue that issued portions in a meritocratic way. When a computer was finished with their task, and there were more tasks to be done, they would be given another task even though that task might be in progress on another computer. This means that each computer is racing to complete as many tasks as they can. The result is that the bottleneck is removed, and the algorithm is much faster.
3) Web socket messaging was key to make this all work. We had to carefully coordinate messages sent to worker nodes in a way where nodes only received tasks when they were ready. Also that they sent back the result and that result was accumulated. When tasks were done we needed to appropriately adjust the state of the task queue. We also wanted to show the status of each node in the UI. Green means they are ready, a spinner means they are busy, and red means there was an error. Lastly, implemented a reset button that refreshes the web browser page. This allowed us to reload a crashed web browser page, update the code, or just stop the process for that node.
Project Members: Daniel Hollcraft & Abel Mcelroy