Skip to main content

Tolerating Slowdowns in Replicated State Machines using Copilots

Author(s): Ngo, Khiem; Sen, Siddhartha; Lloyd, Wyatt

To refer to this page use:
Abstract: Replicated state machines are linearizable, fault-tolerant groups of replicas that are coordinated using a consensus algorithm. Copilot replication is the first 1-slowdown-tolerant consensus protocol: it delivers normal latency despite the slowdown of any 1 replica. Copilot uses two distinguished replicas—the pilot and copilot—to proactively add redundancy to all stages of processing a client’s command. Copilot uses dependencies and deduplication to resolve potentially differing orderings proposed by the pilots. To avoid dependencies leading to either pilot being able to slow down the group, Copilot uses fast takeovers that allow a fast pilot to complete the ongoing work of a slow pilot. Copilot includes two optimizations—ping-pong batching and null dependency elimination—that improve its performance when there are 0 and 1 slow pilots respectively. Our evaluation of Copilot shows its performance is lower but competitive with Multi-Paxos and EPaxos when no replicas are slow. When a replica is slow, Copilot is the only protocol that avoids high latencies.
Publication Date: 2020
Citation: Ngo, Khiem, Siddhartha Sen, and Wyatt Lloyd. "Tolerating Slowdowns in Replicated State Machines using Copilots." In 14th USENIX Symposium on Operating Systems Design and Implementation (2020): pp. 583-598.
Pages: 583 - 598
Type of Material: Conference Article
Journal/Proceeding Title: 14th USENIX Symposium on Operating Systems Design and Implementation
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.