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

即使在没有领导者的情况下，蚂蚁群体、蜂箱和市场又是如何运作的？回答这个问题的一个起点是分布式计算中的基本协议问题：拜占庭协议。拜占庭协议问题是设计一个协议，使得一组代理可以就一个公共输出达成协议，每个代理都有一个私人输入，该输出等于某个代理的输入。一个未知的代理子集出现了拜占庭式的错误，这让问题变得复杂起来：它们可能会随意偏离协议，包括虚假消息和串通。拜占庭协议在许多领域都有应用，包括对等系统、数据库系统、控制系统、网格计算、云计算和博弈论。不幸的是，一个明显的障碍阻碍了继续应用：没有实用的、可伸缩的拜占庭协议算法。特别是，目前所有的拜占庭协议算法都需要全对全的通信：每个代理必须与其他代理进行通信，本研究将通过设计可扩展的拜占庭协议算法以及其他相关问题来直接解决这一障碍。我们的目标是设计可伸缩的算法，即每个代理发送的比特数量为O(SQRT(N)logn)，总延迟为O(Logn)，其中n是处理器的数量；并且健壮的意义是它们可以容忍高达恒定比例的拜占庭错误。除了拜占庭协议之外，我们还将为以下三个相关问题设计可扩展和健壮的算法。第一，小组委员会选举：所有处理机同意一个或多个大小为O(Logn)的小组委员会，其中每个小组委员会中的坏处理机的比例在网络中的坏处理机的百分比内，对于任何正的ε。第二，MapReduceTM：启用MapReduceTM软件框架，即使没有主服务器。最后，健壮的多方计算：每个处理器从一个私有输入开始，有一个关于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.