How do ant colonies, bee hives, and markets function even when there is no leader? A starting point for answering this question is the fundamental problem of agreement in distributed computing: Byzantine agreement. The Byzantine agreement problem is to devise a protocol so that a group of agents, each with a private input can agree on a single common output that is equal to some agent's input. The problem is complicated by the fact that an unknown subset of the agents suffer Byzantine faults: they can engage in arbitrary deviations from the protocol, including false messages and collusion. Byzantine agreement has found applications in many areas, including peer-to-peer systems, database systems, control systems, grid computing, cloud computing and game theory. Unfortunately, continued application is hampered by a stark barrier: there is no practical, scalable algorithm for Byzantine agreement. In particular, all current Byzantine agreement algorithms require all-to-all communication: each agent must talk with every other agent.
This research will directly address this barrier by designing scalable algorithms for Byzantine agreement and other related problems. Our goal is to design algorithms that are scalable in the sense that each agent sends a number of bits that is O(sqrt(n) log n), and total latency is O(log n), where n is the number of processors; and robust in the sense that they can tolerate up to a constant fraction of Byzantine faults. In addition to Byzantine agreement, we will design scalable and robust algorithms for the following three related problems. First, Subcommittee Election: All processors agree on one or more subcommittees of size O(log n), where the fraction of bad processors in each subcommittee is within epsilon of the fraction of bad processors in the network, for any positive epsilon. Second, MapReduce: Enable the MapReduce software framework, even when there is no master. Finally, Robust Multiparty Computation: Each processor starts with a private input and there is a publicly known function F on n variables; the goal is for all users to learn the output of F at the point given by the private inputs. The long-term vision is to develop a technique, based on Byzantine agreement, that is on par with techniques like cryptography and error-correcting codes by 1) being frequently used in practice and applicable across a wide range of applications; and 2) having a clean interface between theory and practice.
