COMPUTING RESEARCH HIGHLIGHT OF THE WEEK [January 7 - 14, 2011]
Breaking the O(n^2) Bit Barrier
The paper "Breaking the O(n^2) Bit Barrier: Scalable Byzantine Agreement with an Adaptive Adversary" by Valerie King, of the University of Victoria BC, and Jared Saia, of the University of New Mexico, recently received the best paper award at the prestigious Principles of Distributed Computing (PODC) conference. This paper describes an algorithm that solves the Byzantine agreement problem with significantly less communication than any previous results. The venerable Byzantine agreement problem addresses the question of how we can create a reliable system out of unreliable components. In particular, it requires a set of processors to come to agreement on a single bit, even when there is no trusted external party, and, moreover, a hidden fraction of the processors are controlled by an adversary. The problem has applications in many areas including: control systems, cloud computing, grid computing, peer-to-peer networks, data base systems, sensor networks and game theory.
The key breakthrough in this new paper is an algorithm that is scalable in the sense that each processor is required to send a number of bits that is only asymptotically close to the square root of the number of processors in the network. In contrast, all previous algorithms require sending a number of bits that grew at least linearly with the network size. The algorithm in the new paper is also robust to a particularly strong adversary: one that can choose which processors to take over at any time during the algorithm, up to taking over up to a 1/3 fraction of the nodes. This paper makes use of several novel mathematical and algorithmic tools including: combinatorial samplers, a new distributed data structure called a (s,t)-random source, and an iterative secret sharing scheme. The full paper is available here.
Researchers:
Jared Saia, University of New Mexico
Valerie King, University of Victoria
Agencies (that have supported the research):
Pennsylvania State University, University Park and Simmons College
‹ Current Highlight | Past Highlights ›
Computing Research Highlight of the Week is a service of the Computing Community Consortium and the Computing Research Association designed to highlight some of the exciting and important recent research results in the computing fields. Each week a new highlight is chosen by CRA and CCC staff and volunteers from submissions from the computing community. Want your research featured? Submit it!.
