Keynote: A Graph Theoretic Approach for Resilient Distributed Algorithms
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 unified 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. We will discuss recent developments along the following two lines of research:
- Designing distributed algorithms that can handle various adversarial settings, such as, node crashes and Byzantine attacks. We will mainly provide general compilation schemes that are based on exploiting the high-connectivity of the graph. Our key focus will be on the efficiency of the resilient algorithms in terms of the number of communication rounds.
- Initiating and establishing the theoretical exploration of security in distributed graph algorithms. Such a notion has been addressed before mainly in the context of secure multi-party computation (MPC). The heart of our approach is to develop new graph theoretical infrastructures to provide graphical secure channels between nodes in a communication network of an arbitrary topology.
Finally, I will highlight future directions that call for strengthening the connections between the areas of fault tolerant network design, distributed graph algorithms and information theoretic security.
Keywords: Distributed Graph Algorithms, Information Theoretic Security,
Merav Parter is a faculty member in the Department of Computer Science and Applied Mathematics at the Weizmann Institute of Science. Before joining Weizmann, she was a Fulbright and Rothschild Postdoctoral Researcher in the EECS department of MIT. In the past, she was a Google European Fellow in Distributed Computing, 2012. Her research interests include reliable distributed communication, graph theory, and neural networks. Parter’s research is supported (in part) by the European Research Council (starting grant DistRES, 2020-2025), the Israeli Science Foundation (ISF) and the NSF-BSF organization. She is the recipient of the Krill prize for Excellence in Scientific Research of 2021.