Algorithmic Foundations of Supervised Distributed Computing

• Applicant: Professor Dr. Christian Scheideler
• Subject Area: Theoretical Computer Science
• Term: since 2025
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 549499840

Distributed approaches that are robust against faults and malicious behavior have a long history. With the rise of open distributed systems, also known as peer-to-peer systems, such approaches are particularly useful since in these systems, faults and adversarial behavior are not an exception but the norm. However, existing solutions have a large overhead or wouldn't even work at all if the system is under a massive adversarial attack. Therefore, we investigate in this proposal, to which extent a trusted third party, called supervisor, might be able to help a community of peers with potentially no trust relationships to reliably solve a computational problem in a distributed fashion with minimal overhead for the supervisor and the peers. Besides abstract solutions to classes of computational problems that can be modeled as directed acyclic task graphs, we will also investigate solutions to specific problems that have been studied by the research community.

• DFG Programme: Research Grants