Abstract
dc:description.abstractNakamoto’s consensus protocol, known for operating in a permissionless model where nodes can join and leave without notice.However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model? This thesis shows that it is not with the Sandglass and Gorilla Sandglass protocols. Sandglass emerges as the first permissionless consensus algorithm that transcends Nakamoto’s probabilistic limitations by guaranteeing deterministic agreement and termination with probability 1, under general omission failures. It operates under a \emph{hybrid synchronous} communication model, where, despite the unknown number and dynamic participation of nodes, a majority are consistently correct and synchronously connected. Further building on the framework of Sandglass, Gorilla Sandglass is the first Byzantine fault-tolerant consensus protocol that preserves deterministic agreement and termination with probability 1 within the same synchronous model adopted by Nakamoto. Gorilla addresses the limitations of Sandglass, which only tolerates benign failures, by extending its robustness to include Byzantine failures. We prove the correctness of Gorilla by mapping executions that would violate agreement or termination in Gorilla to executions in Sandglass, where we know such violations are impossible. Establishing termination proves particularly interesting, as the mapping requires reasoning about infinite executions and their probabilities.
Degree
thesis:*- Name thesis:degree_name
- Ph. D., Computer Science
- Level thesis:degree_level
- Doctor of Philosophy
- Discipline thesis:degree_discipline
- Computer Science
- Grantor
- Cornell University
- Year dc:date.issued
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Pu, Youer
- Chair dc:contributor.chair
-
- Alvisi, Lorenzo
- Committee members dc:contributor.committeemember
-
- Pass, Rafael
- Hodes, Harold
Rights
dc:rights- Statement dc:rights
-
- Attribution 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 16611801
- Dc Identifier Other
-
ProQuest Submission ID: 14483
ProQuest Publication ID: 31485267