Volunteer computing is based on a simple but powerful idea: millions of computers around the world have unused processing power that can be harnessed to solve large computational problems. At a high level, typical volunteer computing systems follow a master-worker approach. A central server (the master) coordinates the computation by dividing it into many smaller tasks and distributing them to participating clients (the workers). Each worker executes its assigned task independently and returns the result to the master, which collects the results to construct the final outcome.

However, this setup introduces important challenges. Workers may be faulty, or even adversarial, making it necessary to prevent manipulation of the computation. A straightforward and commonly used solution is redundancy: assigning the same task to multiple workers and accepting only the result agreed upon by the majority. As long as most workers behave honestly, this approach yields correct results. Nevertheless, it becomes ineffective when the majority is malicious, and it is inherently inefficient, as each task must be executed by many honest workers.

An alternative approach is to require workers to provide verifiable proofs alongside their results. The master can then check correctness directly and, if necessary, reassign tasks until a valid result is obtained. While this reduces the total work of the honest workers, it shifts the burden to the master, which must perform many verifications and may become a performance bottleneck. 

To address these issues, the Supervised Distributed Computing (SDC) model was introduced. Here, the master, which is now called the supervisor, does not perform the verifications itself. Instead, it tells the workers who to communicate with, enabling them to verify each other's outputs. By delegating verification to the workers, the supervisor remains lightweight and avoids becoming a performance bottleneck. However, this creates new challenges, as malicious workers may provide false verification results. Fortunately, prior work has shown that carefully designed scheduling strategies can overcome this issue. In particular, there exists a strategy that tolerates any constant fraction of adversarial workers while ensuring that the expected workload for honest workers remains close to a single execution per task!

What you'll do

The goal of this project group is to implement and evalute a volunteer computing platform based on the SDC model. Specifically, we want to implement the scheduling strategy that works for any constant fraction of adversarial workers. To achieve this, the project consists of the following tasks:

• Read papers about SDC
• Implement the supervisor logic of the SDC model as a server program
• Implement the worker logic of the SDC model as a client program
• Make sure that the implementation is secure against adversarial actors
• Run experiments and collect statistics in your SDC implementation to aid research

• Design task graphs that solve new problems using the SDC model

   

Prerequisites

• Basic programming skills
• Experience in developing client-server applications or motivation to learn it
• Theoretical foundation to understand and implement distributed algorithms