Practical, scalable algorithms for Byzantine agreement

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.

Name thesis:degree_name

Computer Science

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Department of Computer Science

Year

2011

Author dc:creator

• Oluwasanmi, Olumuyiwa

Contributors dc:contributor

• Saia, Jared
• Bridges, Patrick
• Moore, Cristopher
• Valerie, King

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

Language dc:language

English

Identifier

https://digitalrepository.unm.edu/cs_etds/18

OAI identifier oai:identifier

oai:digitalrepository.unm.edu:cs_etds-1017