Back to search

Cornell University

Ordering versus Bounded Delay: Timely Consensus

Abstract

dc:description.abstract

Traditionally, consensus protocols have been designed under the best-effort delivery communication model. Motivated by the fact that datacenter networks enable co-designing network communication protocols and consensus protocols, an exciting recent line of research has demonstrated that it is possible to design high-performance consensus and state machine replication protocols by enabling a stronger communication model, one where the network provides message ordering. This thesis explores a very different communication model that can be enabled by datacenter networks---bounded message delays---and demonstrates that, under this model, it is possible to design consensus protocols that guarantee strong properties, including safety and termination even when all but one replica fails. Our contributions are three-fold. First, we present a network communication protocol that enables a novel Timely Unreliable Multicast (TUM) primitive; TUM guarantees that, for every message sent by a sender: (1) all receivers that receive the message receive it within a bounded amount of time that is known a priori; and (2) messages may be lost due to hardware failures only, and not due to buffer overflows. Second, we design Timely consensus and state machine replication protocols that build upon the TUM primitive to guarantee safety and termination, even with all but one replica failures (under the crash recovery failure model). Finally, using an end-to-end implementation of the TUM primitive and the Timely protocols, we demonstrate that \name protocols enable these properties while achieving high performance even under worst-case network hardware failures.

Degree

thesis:*
Name thesis:degree_name
M.S., Computer Science
Level thesis:degree_level
Master of Science
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gioioso, Katherine Rose
Chair dc:contributor.chair
  • Agarwal, Rachit
Committee member dc:contributor.committeemember
  • Tardos, Eva

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
15160287
Dc Identifier Other
ProQuest Submission ID: 11255
ProQuest Publication ID: 28651534

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gioioso, Katherine Rose. Ordering versus Bounded Delay: Timely Consensus. Master of Science thesis, Cornell University, 2021. https://hdl.handle.net/1813/110403