{"id":{"repo_id":"unm","oai_identifier":"oai:digitalrepository.unm.edu:cs_etds-1017"},"canonical_url":"https://search.dev.ndltd.org/etd/unm/oai:digitalrepository.unm.edu:cs_etds-1017","repository":{"repo_id":"unm","name":"University of New Mexico","base_url":"https://digitalrepository.unm.edu/do/oai/"},"display":{"title":"Practical, scalable algorithms for Byzantine agreement","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.","abstract_html":"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 <span class=\"etd-inline-math\"> ilde{O}(\\sqrt{n})</span> 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 <span class=\"etd-inline-math\">1-o(n<sup>k</sup>)</span> 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.","abstract_has_math":true,"creators":["Oluwasanmi, Olumuyiwa"],"institution":null,"degree_name":"Computer Science","degree_level":"Dissertation","degree_discipline":"Department of Computer Science","degree_department":null,"school":null,"contributors":["Saia, Jared","Bridges, Patrick","Moore, Cristopher","Valerie, King"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-12-01T08:00:00Z","date_published":"2011-12-01T08:00:00Z","updated_at":"2026-07-24T05:26:07Z","subjects":["Byzantine Agreement","Fault-Tolerant","Fault-Tolerance","Randomized Algorithm","Monte Carlo","Random Beacon","Distributed Algorithm","Consensus","Byzantine"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalrepository.unm.edu/cs_etds/18"],"render_values":[{"text":"https://digitalrepository.unm.edu/cs_etds/18","href":"https://digitalrepository.unm.edu/cs_etds/18","code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/1928/17495","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Saia, Jared","Bridges, Patrick","Moore, Cristopher","Valerie, King"]},{"key":"dc:creator","label":"Author","values":["Oluwasanmi, Olumuyiwa"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_discipline","label":"Discipline","values":["Department of Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation","Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Computer Science"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Byzantine Agreement","Fault-Tolerant","Fault-Tolerance","Randomized Algorithm","Monte Carlo","Random Beacon","Distributed Algorithm","Consensus","Byzantine"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/1928/17495","https://digitalrepository.unm.edu/cs_etds/18"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Practical, scalable algorithms for Byzantine agreement"]}]}],"canonical_facts":{"dc:contributor":["Saia, Jared","Bridges, Patrick","Moore, Cristopher","Valerie, King"],"dc:creator":["Oluwasanmi, Olumuyiwa"],"dc:description.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."],"dc:identifier":["http://hdl.handle.net/1928/17495","https://digitalrepository.unm.edu/cs_etds/18"],"dc:language":["English"],"dc:subject":["Byzantine Agreement","Fault-Tolerant","Fault-Tolerance","Randomized Algorithm","Monte Carlo","Random Beacon","Distributed Algorithm","Consensus","Byzantine"],"dc:title":["Practical, scalable algorithms for Byzantine agreement"],"thesis:degree_discipline":["Department of Computer Science"],"thesis:degree_level":["Dissertation","Doctoral"],"thesis:degree_name":["Computer Science"]},"updated_at":"2026-07-24T05:26:07Z"}