Ordering versus Bounded Delay: Timely Consensus

74 pagesTraditionally, 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