Generalizing State Machine Replication

Eli Gafni, Rachid GuerraouiInfoscience 2010

Abstract

We show that, with $k$-set consensus, any number of processes can emulate $k$ state machines of which at least one progresses. This generalizes the celebrated universality of consensus which enables to build a state machine that always progresses. Besides some interesting extensions and even potential “practical” applications, theoretically, a fundamental ramification of our main result, derived by considering the state machines to be interacting read-write threads, is a flagpole to the thesis that distributed computing is all about wait-freedom. We indeed show that the set of tasks that are read-write solvable “$k$-concurrently”, i.e., when concurrency goes below $k$, is the same set of tasks that are read-write solvable with $k$-set consensus.

Introduction

In the realm of distributed systems, State Machine Replication (SMR) stands as the gold standard for constructing fault-tolerant services. Traditionally, SMR relies on the "universality of consensus"—the principle that if processes can agree on a single value (the next command), they can build any shared service that makes progress as long as the system remains functional.

However, achieving consensus is notoriously difficult in asynchronous environments prone to failures. This challenge led to the study of $k$-set consensus, a weaker primitive where processes agree on at most $k$ different values. In "Generalizing State Machine Replication," Eli Gafni and Rachid Guerraoui address a fundamental question: What can be built with $k$-set consensus? If we cannot agree on a single "next step" for one state machine, can we still ensure useful progress?

The Baseline: Standard State Machine Replication

To understand the generalization, one must first consider the standard SMR model. In a typical setup, processes maintain a local copy of a state machine and a list of commands to execute. They use a sequence of consensus objects to agree on which command from which process should be executed next.

Figure 1: A standard state machine replication algorithm using a single consensus object per step.

As shown in Figure 1, the process picks a command, proposes it to a consensus object, and then executes the command that the consensus object returns. If the returned command matches its own proposal, it moves to its next command; otherwise, it retries its current command in the next consensus round. This mechanism ensures that all processes execute the same sequence of commands, maintaining a consistent state.

Methodology: From Consensus to $k$-Set Consensus

The authors generalize this protocol by replacing the single consensus instance with a vector of $k$ consensus objects. This allows for "$k$-universality": while standard consensus enables one state machine to progress, $k$-set consensus allows a system to run $k$ state machines where at least one is guaranteed to make progress.

The core of their approach involves a "Synchronization Filter" using adopt-commit objects. The process follows these steps:

  1. Vector Proposing: Processes propose a vector of commands to $k$ different state machines.
  2. Synchronization: Instead of immediate execution, the output of the consensus vector passes through adopt-commit objects.
  3. Adopt vs. Commit: If an object returns "Committed," the process executes the command. If it returns "Adopted," the process adopts that value for the next round without executing it yet, as it cannot be sure other processes have seen it.
  4. Catch-up Mechanism: To maintain safety, processes encode information about previously committed commands into new proposals, allowing lagging processes to catch up.

Key Insights and Theoretical Ramifications

The paper's most striking insight is that $k$-set consensus is not merely a "broken" version of consensus but a robust tool for multi-machine progress. It ensures that even in unstable systems where total agreement is impossible, progress is not entirely halted.

Furthermore, this result reinforces the "Wait-Freedom" thesis. The authors demonstrate a formal equivalence: solving a task with $k$-set consensus is computationally equivalent to solving it in a model where concurrency is restricted to $k$ processes. This provides a powerful theoretical bridge between different types of system constraints and agreement primitives.

From a practical perspective, the paper suggests that in highly unstable environments, it is preferable to have multiple state machines where at least one progresses rather than a single machine that is completely blocked. While these machines might diverge, their states can potentially be reconciled once stability returns.

Results and Limitations

The authors prove several key theorems:

  • Liveness (Theorem 3): An infinite number of commands will be executed on at least one of the $k$ state machines at all correct processes.
  • Generalization (Theorem 4): If disagreement stabilizes to $j$, then at least $m - j + 1$ machines will progress (where $m$ is the number of processes).
  • Solvability Equivalence: The set of tasks solvable "$k$-concurrently" is identical to those solvable with $k$-set consensus.

Despite these breakthroughs, the paper leaves some open questions. It does not provide a specific algorithm for reconciling divergent state machine views once the system stabilizes. Additionally, the protocol focuses on theoretical possibility over performance; managing $k$ state machines and adopt-commit vectors introduces significant overhead. Finally, fairness is not guaranteed in the basic protocol, though the authors suggest "helping" mechanisms as a potential solution.

Summary updated

Abstract

We show that, with k-set consensus, any number of processes can emulate k state machines of which at least one progresses. This generalizes the celebrated universality of consensus which enables to build a state machine that always progresses. Besides some interesting extensions and even potential “practical” applications, theoretically, a fundamental ramification of our main result, derived by considering the state machines to be interacting read-write threads, is a flagpole to the thesis that distributed computing is all about wait-freedom. We indeed show that the set of tasks that are read-write solvable “k-concurrently” , i.e., when concurrency goes below k, is the same set of tasks that are read-write solvable with k-set consensus.
BibTeX
@inproceedings{gafni2010generalizing,
  author = {Eli Gafni and Rachid Guerraoui},
  title = {{Generalizing State Machine Replication}},
  booktitle = {Infoscience},
  year = {2010},
}
Figure