-
Byzantine Agreement with Less Communication by Idit Keidar, Technion - Israel Institute of Technology, Israel
Abstract
Byzantine Agreement (BA) has been studied for four decades by now, but until recently, has been considered at a fairly small scale. In recent years, however, we begin to see practical use-cases of BA in large-scale systems, which motivates a push for reduced communication complexity. Dolev and Reischuk’s well-known lower bound stipulates that any deterministic algorithm requires \Omega(n^2) communication in the worst-case, and until fairly recently, almost all randomized algorithms have had at least quadratic complexity as well. This talk will present two new randomized asynchronous BA algorithms breaking this barrier.
The first part of the talk will consider single-shot randomized BA whose safety and liveness guarantees hold with high probability. It will present the first asynchronous Byzantine Agreement algorithm with sub-quadratic communication complexity. This algorithm exploits VRF-based committee sampling, which it adapts for the asynchronous model.
The second part of the talk will consider Byzantine Atomic Broadcast, which is the underpinning of Byzantine State Machine Replication. In this context, the relevant metric is amortized communication cost. The talk will present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity. DAG-Rider is post-quantum safe and ensures that all messages proposed by correct processes eventually get decided.
The first part of the talk is based on joint work with Shir Cohen and Alexander Spiegelman and the second is based on joint work with Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman.
Biography
Idit Keidar is the Lord Leonard Wolfson Professor at the Technion’s Vitrerbi Faculty of Electrical and Computer Engineering. She received her BSc (summa cum laude), MSc (summa cum laude), and PhD from the Hebrew University of Jerusalem in 1992, 1994, and 1998, respectively. Subsequently, she was a Rothschild Postdoctoral Fellow at MIT’s Laboratory for Computer Science. Prof. Keidar has served as the program chair for a number of leading conferences (PODC, DISC, PPoPP, and SYSTOR). She currently heads the Technion Rothschild Scholars Program for Excellence and consults for Yahoo Labs and Orbs. -
A Liquid Networking Approach to Delivering the Metaverse
by Michael Luby, CEO, BitRIpple, Inc., USA
Abstract
Metaverse applications enable life-like interactions in a shared virtual world. For the experience to feel real to end users, ultra-low latency delivery of the dynamically changing Metaverse is essential. We present an approach to ultra-low latency delivery based on a Liquid Networking approach, based on the RaptorQ erasure code (specified in IETF RFC 6330). The essential idea is that, using RaptorQ, a sender generates and sends liquid packets for each data block to be delivered to a receiver. They are called liquid packets because, like drops of a liquid, they are interchangeable: the receiver recovers each block as soon as enough liquid packets arrive at the receiver, independent of which liquid packets arrive.
Biography
Dr. Michael Luby co-founded and is CEO of BitRipple, Inc. Previously, Mike co-founded and was CTO of Digital Fountain, and after its acquisition was a VP of Technology at Qualcomm Technologies, Inc. Mike earned a BSc in Applied Math from MIT and a PhD in Theoretical Computer Science from UC Berkeley. Awards for his research include the IEEE Richard W. Hamming Medal, the ACM Paris Kanellakis Theory and Practice Award, the IEEE Eric E. Sumner Communications Theory Award, the UC Berkeley Distinguished Alumni in Computer Science Award, and numerous prizes for his research papers in distributed computing, information theory, coding theory, transport technologies, and cryptography. He is a member of the National Academy of Engineering and is an IEEE Fellow and an ACM Fellow. -
Ant Colony House-Hunting Algorithms by Nancy Lynch, Massachusetts Institute of Technology, USA
Abstract
In this talk, I will describe our research over the past few years on certain biological distributed algorithms, specifically, on “House-Hunting” algorithms, used by ant colonies to find and relocate to a new nest. These algorithms have been widely studied in the insect biology community, for example, by Pratt’s group at Arizona State University.
The approach we have taken is interesting: We began by defining abstract, theoretical models for the house-hunting problem and using them to devise algorithms and prove lower bound results. More recently, we progressed to considering much more biologically realistic and complete models. We simulated these extensively and explored their properties, looking for insights about their decision-making behavior. Our most recent work involves trying to prove some of these observed properties.
Joint work with Mira Radeva, Cameron Musco, Mohsen Ghaffari, Jiajia Zhao, Steven Pratt, Emily Zhang, Lili Su, Grace Cai, Wendy Wu, and Wayne Zhao.
Biography
Nancy Lynch is the NEC Professor of Software Science and Engineering in MIT's EECS department. She heads the Theory of Distributed Systems research group in the Computer Science and Artificial Intelligence Laboratory (CSAIL). She received her B.S. from Brooklyn College and her PhD from MIT, both in mathematics.
Lynch has written many research articles about distributed algorithms and impossibility results, and about formal modeling and verification of distributed systems. Her best-known contribution is the "FLP" impossibility result for distributed consensus in the presence of process failures, with Fischer and Paterson. Other contributions include the I/O automata modeling frameworks, with Tuttle, Kaynar, Segala, and Vaandrager. Her recent work is focused on wireless network algorithms and biological distributed algorithms.
Lynch is the author of the book "Distributed Algorithms" and co-author of "The Theory of Timed I/O Automata". She is an ACM Fellow, a Fellow of the American Academy of Arts and Sciences, and a member of the National Academy of Engineering as well as the NAS. She has been awarded the Dijkstra Prize (twice), the van Wijngaarden prize, the Knuth Prize, the Piore Prize, and the Athena Prize. She has supervised approximately 30 PhD students and over 50 Masters students. -
Locality in Computation by Ronitt Rubinfeld, Massachusetts Institute of Technology, USA
Abstract
Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of "local computation algorithms" which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. Though this model describes sequential computations, techniques from local distributed algorithms have been extremely important in designing efficient local computation algorithms. In this talk, we describe results on a variety of problems for which sublinear time and space local computation algorithms have been developed -- we will give special focus to finding maximal independent sets, scheduling problems and generating random objects.
Biography
Ronitt Rubinfeld is a professor in the Department of Electrical Engineering and Computer Science and a member of the Computer Science and Artificial Intelligence Laboratory. Ronitt's main research area is theory of computation. Ronitt received her PhD from the University of California, Berkeley in 1991, and prior to that graduated from the University of Michigan with a BSE in Electrical and Computer Engineering. Before coming to MIT, Ronitt held postdoctoral researcher positions at Princeton University and Hebrew University. In 1992, she joined the faculty of the Computer Science Department at Cornell University, where she was an ONR Young Investigator, a Sloan Research Fellow, the 1995 Cornell Association for Computer Science Undergraduates Faculty of the Year, and a recipient of the Cornell College of Engineering Teaching Award. From 1999 to 2003, Ronitt was a Senior Research Scientist at NEC Research Laboratories, and in 2004, she was a Fellow at the Radcliffe Institute for Advanced Study. -
Actively Dynamic Networks by Paul Spirakis, University of Liverpool ,UK and University of Patras , Greece
Abstract
We discuss here systems of (distributed) entities that can actively modify their communication network. We focus on two broad Issues : (a) distributed algorithms that can reconfigure a network to carry out a given task efficiently (b) Creating a desired network starting from a single entity and allowing entities (nodes) to self-replicate and thus expand the network and its size. Such issues lead to a natural balance between how fast (time) and how efficiently (number of link activations , number of excess links to be eventually deleted) a target network can be generated. Our results include lower bounds and algorithms that try to balance speed and efficiency.
Biography
Paul Spirakis is a Chair Professor in the Department of Computer Science of the University of Liverpool and also a Professor of the University Of Patras. Paul’s main research areas are distributed computing , randomness in algorithms and algorithmic game theory. Paul received his PhD from Harvard University in 1982 and prior to that his MSc also form Harvard University in 1979 and his BSE in Electrical Engineering from the National Technical University of Athens in 1978. Paul held a postdoctoral position at Harvard , then served as a faculty member at NYU and then became an Associate Professor at the University of Patras in 1987 and a Full Professor in 1990 also in the University of Patras. In 2013 he also joined the faculty of the CS Department of the University of Liverpool. Paul has also been a distinguished visiting researcher of Max Planck Informatik. He has directed the Computer Technology Institute (CTI) of Greece from 1996 to 2016. Paul is the co-author of three scientific books of international circulation and of 7 scientific books in Greek. Paul has been the President of the European Association of Theoretical Computer Science (EATCS) from 2016 to 2020. He has chaired the ERC Panel for Informatics twice. He has also been a Member of the European Research Council of ACM and is a Member of the EUACM Policy Body. Paul has been a National Rep. of Research for Greece in the EU and has also served in the ISTAG policy body of the EU. Paul is a Member of Academia Europaea and a Fellow of EATCS. He is the Editor-in-Chief of the Theoretical Computer Science journal (TCS) for Algorithms and Complexity. He has received several awards and has supervised approximately 35 PhD students (and numerous MSc students). Paul has chaired several program committees (including those of PODC, ICALP , SPAA , WINE , SAGT and IPDPS) and has been the Conference Chair of STOC. He has served in over 50 program committees. -
Computational Complexity Theory for MapReduce by Jeffrey Ullman, Stanford University, USA
Abstract
MapReduce, as embodied in systems such as Hadoop and Spark, has proven to be an important tool for developing reliable, resilient, parallel software. But the mechanics of MapReduce require that we think differently about the cost of different algorithms to accomplish a given task. We shall give the elements of a useful algorithm-design theory that involves tradeoffs between the amount of data permitted at any one reducer ("reducer size") and the amount of communication from mappers to reducers ("replication rate"). We shall give the exact form of this tradeoff for several interesting problems, including "all-pairs" comparisons, and detecting strings that differ by one bit.
Biography
Jeff Ullman is the Stanford W. Ascherman Professor of Engineering (Emeritus) in the Department of Computer Science at Stanford and CEO of Gradiance Corp. He received the B.S. degree from Columbia University in 1963 and the PhD from Princeton in 1966. Prior to his appointment at Stanford in 1979, he was a member of the technical staff of Bell Laboratories from 1966-1969, and on the faculty of Princeton University between 1969 and 1979. From 1990-1994, he was chair of the Stanford Computer Science Department. Ullman was elected to the National Academy of Engineering in 1989, the American Academy of Arts and Sciences in 2012, the National Academy of Sciences in 2020, and has held Guggenheim and Einstein Fellowships. He has received the Sigmod Contributions Award (1996), the ACM Karl V. Karlstrom Outstanding Educator Award (1998), the Knuth Prize (2000), the Sigmod E. F. Codd Innovations award (2006), the IEEE von Neumann medal (2010), the NEC C&C Foundation Prize (2017), and the ACM A.M. Turing Award (2020). He is the author of 16 books, including books on database systems, data mining, compilers, automata theory, and algorithms.