Computer Science ETDs

Publication Date

12-1-2011

Abstract

With the growth of the Internet, there has been a push toward designing reliable algorithms that scale effectively in terms of latency, bandwidth and other computational resources. Scalability has been a serious problem especially with peer-to-peer (p2p) networks which may have sizes of more than a million nodes. An important problem in designing reliable algorithms is Byzantine agreement. For reasons of scalability, message complexity is a critical resource for this problem. Unfortunately, previous solutions to Byzantine agreement require each processor to send $O(n)$ messages, where $n$ is the total number of processors in the network. In this dissertation, we show that the Byzantine agreement problem can be solved with significantly less that a linear number of messages both in theory and in practice. We implement and test algorithms that solve the classical problem with each processor sending only $\ ilde{O}(\sqrt{n})$ messages. Further, we consider the problem in the case where we assume the existence of a random beacon: a global source of random bits. We show that with this assumption, the required number of messages drops to $O(\log n)$, with small hidden constants. Our algorithms are Monte Carlo and succeed with high probability, that is probability $1-o(n^k)$ for some positive constant $k$. Our empirical results suggest that our algorithms may outperform classical solutions to Byzantine agreement for network of size larger than 30,000 nodes.

Language

English

Keywords

Byzantine Agreement, Fault-Tolerant, Fault-Tolerance, Randomized Algorithm, Monte Carlo, Random Beacon, Distributed Algorithm, Consensus, Byzantine

Document Type

Dissertation

Degree Name

Computer Science

Level of Degree

Doctoral

Department Name

Department of Computer Science

First Committee Member (Chair)

Bridges, Patrick

Second Committee Member

Moore, Cristopher

Third Committee Member

Valerie, King

Project Sponsors

NSF, AFOSR MURI Grant.

Download

Share

COinS