Computing without a Leader: Building Blocks for Internet-Scale, Robust Computing

即使没有领导者，蚁群、蜂巢和市场是如何运作的？回答这个问题的起点是分布式计算中协议的基本问题：拜占庭协议。拜占庭协议问题是设计一种协议，使一组具有私有输入的代理可以就一个等于某些代理输入的公共输出达成一致。由于未知的代理子集遭受拜占庭错误（Byzantine fault），问题变得更加复杂：它们可以任意偏离协议，包括错误消息和串通。拜占庭协议在许多领域都有应用，包括点对点系统、数据库系统、控制系统、网格计算、云计算和博弈论。不幸的是，继续应用受到一个明显障碍的阻碍：拜占庭协议没有实用的、可扩展的算法。特别是，所有当前的拜占庭协议算法都需要全对全通信：每个代理必须与其他所有代理进行通信。本研究将通过设计拜占庭协议和其他相关问题的可扩展算法直接解决这一障碍。我们的目标是设计可扩展的算法，即每个代理发送的比特数为O(sqrt(n) log n)，总延迟为O(log n)，其中n为处理器的数量；从某种意义上说，它们可以容忍拜占庭式故障的恒定部分。除了拜占庭协议，我们将为以下三个相关问题设计可扩展和健壮的算法。首先，小组委员会选举：所有处理器同意一个或多个大小为O（log n）的小组委员会，其中每个小组委员会中的坏处理器的比例在网络中坏处理器比例的epsilon内，对于任何正的epsilon。第二，MapReduce：启用MapReduce软件框架，即使没有master。最后，鲁棒多方计算：每个处理器从一个私有输入开始，在n个变量上有一个公开的函数F；目标是让所有用户学习F在私有输入给定点的输出。长期愿景是开发一种基于拜占庭协议的技术，该技术与密码学和纠错码等技术相当，1)在实践中经常使用并适用于广泛的应用；2)在理论和实践之间有一个清晰的界面。

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.