Merav Parter: A Graph Theoretic Approach for Resilient Distributed Algorithms
Monday, December 6, 2021 - 4:00pm to 5:00pm
Location:
Hewlett G882 and Zoom (email dlehto@mit.edu for link)
Speaker:
Merav parter
Seminar group:
Abstract:
Following the immense recent advances in distributed networks, the explosive growth of the Internet, and our increased dependency on these infrastructures, guaranteeing the uninterrupted operation of communication networks has become a major objective in network algorithms. The modern instantiations of distributed networks, such as the Bitcoin network and cloud computing, introduce new security challenges that deserve urgent attention in both theory and practice.
In this talk, I will present a recent framework for obtaining fast, resilient, and secure distributed algorithms for fundamental graph problems. Our approach is based on a graph-theoretic perspective in which common notions of resilient requirements are translated into suitably tailored combinatorial graph structures. I will illustrate two main applications of this framework. The first application considers cryptographic adversaries (semi-honest, eavesdroppers, etc.), and this second considers Byzantine adversaries. One of our key results provides the first sublinear-time algorithm for solving Byzantine broadcast in general networks in the congest model of distributed computing. Finally, I will highlight open directions that call for collaborations between the distributed and the cryptographic communities.
Following the immense recent advances in distributed networks, the explosive growth of the Internet, and our increased dependency on these infrastructures, guaranteeing the uninterrupted operation of communication networks has become a major objective in network algorithms. The modern instantiations of distributed networks, such as the Bitcoin network and cloud computing, introduce new security challenges that deserve urgent attention in both theory and practice.
In this talk, I will present a recent framework for obtaining fast, resilient, and secure distributed algorithms for fundamental graph problems. Our approach is based on a graph-theoretic perspective in which common notions of resilient requirements are translated into suitably tailored combinatorial graph structures. I will illustrate two main applications of this framework. The first application considers cryptographic adversaries (semi-honest, eavesdroppers, etc.), and this second considers Byzantine adversaries. One of our key results provides the first sublinear-time algorithm for solving Byzantine broadcast in general networks in the congest model of distributed computing. Finally, I will highlight open directions that call for collaborations between the distributed and the cryptographic communities.