Hubbry Logo
State machine replicationState machine replicationMain
Open search
State machine replication
Community hub
State machine replication
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
State machine replication
State machine replication
State machine replication
View on Wikipedia
from Wikipedia

In computer science, state machine replication (SMR) or state machine approach is a general method for implementing a fault-tolerant service by replicating servers and coordinating client interactions with server replicas. The approach also provides a framework for understanding and designing replication management protocols.[1]

Problem definition

[edit]

Distributed service

[edit]

In terms of clients and services, each service comprises one or more servers and exports operations that clients invoke by making requests. Although using a single, centralized server is the simplest way to implement a service, the resulting service can only be as fault tolerant as the processor executing that server. If this level of fault tolerance is unacceptable, then multiple servers that fail independently can be used. Usually, replicas of a single server are executed on separate processors of a distributed system, and protocols are used to coordinate client interactions with these replicas.

State machine

[edit]
Main article: Finite-state machine

For the subsequent discussion a State Machine will be defined as the following tuple of values [2] (See also Mealy machine and Moore Machine):

  • A set of States
  • A set of Inputs
  • A set of Outputs
  • A transition function (Input × State → State)
  • An output function (Input × State → Output)
  • A distinguished State called Start.

A State Machine begins at the State labeled Start. Each Input received is passed through the transition and output function to produce a new State and an Output. The State is held stable until a new Input is received, while the Output is communicated to the appropriate receiver.

This discussion requires a State Machine to be deterministic: multiple copies of the same State Machine begin in the Start state, and receiving the same Inputs in the same order will arrive at the same State having generated the same Outputs.

Typically, systems based on State Machine Replication voluntarily restrict their implementations to use finite-state machines to simplify error recovery.

Fault Tolerance

[edit]

Determinism is an ideal characteristic for providing fault-tolerance. Intuitively, if multiple copies of a system exist, a fault in one would be noticeable as a difference in the State or Output from the others.

The minimum number of copies needed for fault-tolerance is three; one which has a fault, and two others to whom we compare State and Output. Two copies are not enough as there is no way to tell which copy is the faulty one.

A three-copy system can support at most one failure (after which it must repair or replace the faulty copy). If more than one of the copies were to fail, all three States and Outputs might differ, and there would be no way to choose which is the correct one.

In general, a system which supports F failures must have 2F+1 copies (also called replicas).[3] The extra copies are used as evidence to decide which of the copies are correct and which are faulty. Special cases can improve these bounds.[4]

All of this deduction pre-supposes that replicas are experiencing only random independent faults such as memory errors or hard-drive crash. Failures caused by replicas which attempt to lie, deceive, or collude can also be handled by the State Machine Approach, with isolated changes.

Failed replicas are not required to stop; they may continue operating, including generating spurious or incorrect Outputs.

Special Case: Fail-Stop

[edit]

Theoretically, if a failed replica is guaranteed to stop without generating outputs, only F+1 replicas are required, and clients may accept the first output generated by the system. No existing systems achieve this limit, but it is often used when analyzing systems built on top of a fault-tolerant layer (Since the fault-tolerant layer provides fail-stop semantics to all layers above it).

Special Case: Byzantine Failure

[edit]

Faults where a replica sends different values in different directions (for instance, the correct Output to some of its fellow replicas and incorrect Outputs to others) are called Byzantine Failures.[5] Byzantine failures may be random, spurious faults, or malicious, intelligent attacks. 2F+1 replicas, with non-cryptographic hashes suffices to survive all non-malicious Byzantine failures (with high probability). Malicious attacks require cryptographic primitives to achieve 2F+1 (using message signatures), or non-cryptographic techniques can be applied but the number of replicas must be increased to 3F+1.[5]

The State Machine Approach

[edit]

The preceding intuitive discussion implies simple technique for implementing a fault-tolerant service in terms of a State Machine:

  1. Place copies of the State Machine on multiple, independent servers.
  2. Receive client requests, interpreted as Inputs to the State Machine.
  3. Choose an ordering for the Inputs.
  4. Execute Inputs in the chosen order on each server.
  5. Respond to clients with the Output from the State Machine.
  6. Monitor replicas for differences in State or Output.

The remainder of this article develops the details of this technique.

The appendix contains discussion on typical extensions used in real-world systems such as Logging, Checkpoints, Reconfiguration, and State Transfer.

Ordering Inputs

[edit]

The critical step in building a distributed system of State Machines is choosing an order for the Inputs to be processed. Since all non-faulty replicas will arrive at the same State and Output if given the same Inputs, it is imperative that the Inputs are submitted in an equivalent order at each replica. Many solutions have been proposed in the literature.[2][6][7][8][9]

A Visible Channel is a communication path between two entities actively participating in the system (such as clients and servers). Example: client to server, server to server

A Hidden Channel is a communication path which is not revealed to the system. Example: client to client channels are usually hidden; such as users communicating over a telephone, or a process writing files to disk which are read by another process.

When all communication paths are visible channels and no hidden channels exist, a partial global order (Causal Order) may be inferred from the pattern of communications.[8][10] Causal Order may be derived independently by each server. Inputs to the State Machine may be executed in Causal Order, guaranteeing consistent State and Output for all non-faulty replicas.

In open systems, hidden channels are common and a weaker form of ordering must be used. An order of Inputs may be defined using a voting protocol whose results depend only on the visible channels.

The problem of voting for a single value by a group of independent entities is called Consensus. By extension, a series of values may be chosen by a series of consensus instances. This problem becomes difficult when the participants or their communication medium may experience failures.[3]

Inputs may be ordered by their position in the series of consensus instances (Consensus Order).[7] Consensus Order may be derived independently by each server. Inputs to the State Machine may be executed in Consensus Order, guaranteeing consistent State and Output for all non-faulty replicas.

Optimizing Causal & Consensus Ordering
In some cases additional information is available (such as real-time clocks). In these cases, it is possible to achieve more efficient causal or consensus ordering for the Inputs, with a reduced number of messages, fewer message rounds, or smaller message sizes. See references for details [1][4][6][11]
Further optimizations are available when the semantics of State Machine operations are accounted for (such as Read vs Write operations). See references Generalized Paxos.[2][12]

While classical SMR typically enforces a total ordering of requests, recent research into sharded distributed ledgers demonstrates that a partial ordering is sufficient for consistency when transactions do not conflict. Graph-based dependency models, such as those utilized in the Cerberus protocol, allow non-conflicting state transitions to occur in parallel across different replicas, overcoming the throughput limitations of a single linear log.[13]

Sending Outputs

[edit]

Client requests are interpreted as Inputs to the State Machine, and processed into Outputs in the appropriate order. Each replica will generate an Output independently. Non-faulty replicas will always produce the same Output. Before the client response can be sent, faulty Outputs must be filtered out. Typically, a majority of the Replicas will return the same Output, and this Output is sent as the response to the client.

System Failure

[edit]
If there is no majority of replicas with the same Output, or if less than a majority of replicas returns an Output, a system failure has occurred. The client response must be the unique Output: FAIL.

Auditing and Failure Detection

[edit]

The permanent, unplanned compromise of a replica is called a Failure. Proof of failure is difficult to obtain, as the replica may simply be slow to respond,[14] or even lie about its status.[5]

Non-faulty replicas will always contain the same State and produce the same Outputs. This invariant enables failure detection by comparing States and Outputs of all replicas. Typically, a replica with State or Output which differs from the majority of replicas is declared faulty.

A common implementation is to pass checksums of the current replica State and recent Outputs among servers. An Audit process at each server restarts the local replica if a deviation is detected.[15] Cryptographic security is not required for checksums.

It is possible that the local server is compromised, or that the Audit process is faulty, and the replica continues to operate incorrectly. This case is handled safely by the Output filter described previously (see Sending Outputs).

Appendix: extensions

[edit]

Input log

[edit]

In a system with no failures, the Inputs may be discarded after being processed by the State Machine. Realistic deployments must compensate for transient non-failure behaviors of the system such as message loss, network partitions, and slow processors.[15]

One technique is to store the series of Inputs in a log. During times of transient behavior, replicas may request copies of a log entry from another replica in order to fill in missing Inputs.[7]

In general the log is not required to be persistent (it may be held in memory). A persistent log may compensate for extended transient periods, or support additional system features such as Checkpoints, and Reconfiguration.

Checkpoints

[edit]

If left unchecked a log will grow until it exhausts all available storage resources. For continued operation, it is necessary to forget log entries. In general a log entry may be forgotten when its contents are no longer relevant (for instance if all replicas have processed an Input, the knowledge of the Input is no longer needed).

A common technique to control log size is store a duplicate State (called a Checkpoint), then discard any log entries which contributed to the checkpoint. This saves space when the duplicated State is smaller than the size of the log.

Checkpoints may be added to any State Machine by supporting an additional Input called CHECKPOINT. Each replica maintains a checkpoint in addition to the current State value. When the log grows large, a replica submits the CHECKPOINT command just like a client request. The system will ensure non-faulty replicas process this command in the same order, after which all log entries before the checkpoint may be discarded.

In a system with checkpoints, requests for log entries occurring before the checkpoint are ignored. Replicas which cannot locate copies of a needed log entry are faulty and must re-join the system (see Reconfiguration).

Reconfiguration

[edit]

Reconfiguration allows replicas to be added and removed from a system while client requests continue to be processed. Planned maintenance and replica failure are common examples of reconfiguration. Reconfiguration involves Quitting and Joining.

Quitting

[edit]

When a server detects its State or Output is faulty (see Auditing and Failure Detection), it may selectively exit the system. Likewise, an administrator may manually execute a command to remove a replica for maintenance.

A new Input is added to the State Machine called QUIT.[2][6] A replica submits this command to the system just like a client request. All non-faulty replicas remove the quitting replica from the system upon processing this Input. During this time, the replica may ignore all protocol messages. If a majority of non-faulty replicas remain, the quit is successful. If not, there is a System Failure.

Joining

[edit]

After quitting, a failed server may selectively restart or re-join the system. Likewise, an administrator may add a new replica to the group for additional capacity.

A new Input is added to the State Machine called JOIN. A replica submits this command to the system just like a client request. All non-faulty replicas add the joining node to the system upon processing this Input. A new replica must be up-to-date on the system's State before joining (see State Transfer).

State Transfer

[edit]

When a new replica is made available or an old replica is restarted, it must be brought up to the current State before processing Inputs (see Joining). Logically, this requires applying every Input from the dawn of the system in the appropriate order.

Typical deployments short-circuit the logical flow by performing a State Transfer of the most recent Checkpoint (see Checkpoints). This involves directly copying the State of one replica to another using an out-of-band protocol.

A checkpoint may be large, requiring an extended transfer period. During this time, new Inputs may be added to the log. If this occurs, the new replica must also receive the new Inputs and apply them after the checkpoint is received. Typical deployments add the new replica as an observer to the ordering protocol before beginning the state transfer, allowing the new replica to collect Inputs during this period.

Optimizing State Transfer

[edit]

Common deployments reduce state transfer times by sending only State components which differ. This requires knowledge of the State Machine internals. Since state transfer is usually an out-of-band protocol, this assumption is not difficult to achieve.

Compression is another feature commonly added to state transfer protocols, reducing the size of the total transfer.

Leader Election (for Paxos)

[edit]

Paxos[7] is a protocol for solving consensus, and may be used as the protocol for implementing Consensus Order.

Paxos requires a single leader to ensure liveness.[7] That is, one of the replicas must remain leader long enough to achieve consensus on the next operation of the state machine. System behavior is unaffected if the leader changes after every instance, or if the leader changes multiple times per instance. The only requirement is that one replica remains leader long enough to move the system forward.

Conflict resolution

[edit]

In general, a leader is necessary only when there is disagreement about which operation to perform,[11] and if those operations conflict in some way (for instance, if they do not commute).[12]

When conflicting operations are proposed, the leader acts as the single authority to set the record straight, defining an order for the operations, allowing the system to make progress.

With Paxos, multiple replicas may believe they are leaders at the same time. This property makes Leader Election for Paxos very simple, and any algorithm which guarantees an 'eventual leader' will work.

Historical background

[edit]

A number of researchers published articles on the replicated state machine approach in the early 1980s. Anita Borg described an implementation of a fault tolerant operating system based on replicated state machines in a 1983 paper, A Message System Supporting Fault Tolerance.[16] Leslie Lamport also proposed the state machine approach, in his 1984 paper on "Using Time Instead of Timeout In Distributed Systems". Fred Schneider later elaborated the approach in his paper "Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial".

Ken Birman developed the virtual synchrony model in a series of papers published between 1985 and 1987. The primary reference to this work is "Exploiting Virtual Synchrony in Distributed Systems", which describes the Isis Toolkit, a system that was used to build the New York and Swiss Stock Exchanges, French Air Traffic Control System, US Navy AEGIS Warship, and other applications.

Recent work by Miguel Castro and Barbara Liskov used the state machine approach in what they call a "Practical Byzantine fault tolerance" architecture that replicates especially sensitive services using a version of Lamport's original state machine approach, but with optimizations that substantially improve performance.

Most recently, there has also been the creation of the BFT-SMaRt library,[17] a high-performance Byzantine fault-tolerant state machine replication library developed in Java. This library implements a protocol very similar to PBFT's, plus complementary protocols which offer state transfer and on-the-fly reconfiguration of hosts (i.e., JOIN and LEAVE operations). BFT-SMaRt is the most recent effort to implement state machine replication, still being actively maintained.

Raft, a consensus based algorithm, was developed in 2013.

Motivated by PBFT, Tendermint BFT[18] was introduced for partial asynchronous networks and it is mainly used for Proof of Stake blockchains.

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

State machine replication

View on Grokipedia
from Grokipedia
State machine replication (SMR) is a foundational paradigm in distributed systems for achieving fault tolerance by replicating a deterministic state machine across multiple servers, where all non-faulty replicas execute the same sequence of client requests in identical order to produce consistent outputs and maintain service availability despite failures. This approach ensures that the system's state remains synchronized without requiring centralized control, relying instead on coordination protocols to handle request agreement and ordering. The core mechanism of SMR involves three key requirements: an initial identical state across replicas, deterministic execution of operations (where outputs depend solely on the input sequence), and coordination to deliver requests in a total order to all replicas. For crash-fault tolerance, protocols like Paxos or Viewstamped Replication typically require 2f+1 replicas to tolerate up to f failures, involving at least three communication phases for consensus. In contrast, Byzantine fault-tolerant variants, such as Practical Byzantine Fault Tolerance (PBFT), demand 3f+1 replicas to handle up to f arbitrary faults, incorporating cryptographic measures like message authentication codes (MACs) and executing in four phases: pre-prepare, prepare, commit, and reply. Historically, SMR traces its origins to Leslie Lamport's 1978 work on time, clocks, and the ordering of events in a distributed system, which laid the groundwork for fault-tolerant replication in failure-free environments, later extended to crash-stop models by Schneider in 1982 and to Byzantine models by Lamport in 1984. Landmark protocols include Lamport's Paxos (1998), which influenced modern implementations like Google's Chubby and Apache ZooKeeper, and Castro and Liskov's PBFT (1999), which enabled practical Byzantine tolerance for applications like secure storage systems. Recent advances focus on scalability and performance, such as optimistic execution in Zyzzyva (2007) to reduce latency or modular designs in Aleph (2018) for internet-scale deployments, addressing challenges in wide-area networks and high-throughput scenarios. SMR underpins critical infrastructure, including key-value stores, coordination services (e.g., etcd in Kubernetes), and blockchain consensus mechanisms, providing linearizable consistency and high availability while tolerating partial synchrony in asynchronous networks. Despite its strengths, challenges persist in optimizing for parallelism, reducing communication overhead, and integrating with emerging hardware like trusted execution environments.

Introduction

Overview

State machine replication (SMR) is a technique for implementing fault-tolerant services in distributed systems by replicating a deterministic state machine across multiple nodes, ensuring that all non-faulty replicas process the same sequence of client requests to maintain a consistent service state. This approach, foundational to achieving replication equivalence, originates from the concept of synchronizing distributed processes to simulate a single centralized execution. SMR transforms a centralized, deterministic service into a distributed one by distributing identical copies of the state machine to replicas, which execute client commands in a coordinated manner to produce outputs indistinguishable from the original service. The replicas collectively handle requests, masking failures among them while preserving the service's functional behavior, thereby enabling high availability and fault tolerance without altering the underlying service logic. At its core, SMR relies on three key principles: the determinism of the state machine, which guarantees that identical inputs yield identical state transitions and outputs across replicas; the total ordering of inputs, ensuring all replicas apply commands in the same sequence; and agreement on the replicated state, achieved through protocols that synchronize logs or dependency graphs among nodes. These principles collectively ensure sequential consistency in the face of concurrent operations. For illustration, consider a simple counter service where clients issue increment requests; in SMR, replicas receive these requests via a total order broadcast, each applying increments sequentially to their local counter, resulting in all correct replicas converging on the same value regardless of request arrival order at individual nodes.

Importance and Applications

State machine replication (SMR) is essential for constructing highly available and fault-tolerant distributed systems, as it ensures that services remain operational despite failures in components such as servers or networks. By replicating the state machine across multiple nodes and achieving consensus on input sequences, SMR ensures sequential consistency, which supports strong consistency models critical for maintaining data integrity in services like databases and ledgers. This fault tolerance extends to Byzantine faults, where nodes may behave arbitrarily, enabling resilience in adversarial environments without compromising availability. Key applications of SMR span replicated databases, blockchain consensus, and cloud services. In distributed databases, Google's Spanner employs Paxos-based state machines to replicate data across global regions, supporting externally consistent reads and writes at scale. For blockchain systems, Tendermint in the Cosmos ecosystem uses SMR to replicate application state machines securely across nodes, powering interoperable chains for decentralized applications including those in decentralized finance (DeFi). In cloud infrastructure, etcd leverages the Raft consensus algorithm to implement SMR, providing a reliable key-value store for coordination in systems like Kubernetes. While SMR enhances resilience compared to non-replicated systems, it introduces trade-offs, particularly increased latency from coordination overhead required for total order agreement among replicas. This coordination ensures fault tolerance but can degrade performance in high-throughput scenarios, necessitating optimizations for specific workloads. SMR's relevance continues in edge computing and DeFi, where partial synchrony assumptions enable protocols to handle intermittent connectivity in resource-constrained environments like IoT networks. Recent advances include automated integration of Byzantine fault-tolerant SMR into IoT systems and optimizations for partial synchrony, such as Qsync, enhancing scalability in edge deployments. In DeFi, SMR underpins secure, replicated ledgers for financial primitives on platforms like Cosmos, enabling trustless transactions amid volatile network conditions.

Fundamentals

State Machines

A state machine is a mathematical model that represents the behavior of a system through a collection of states, transitions between states triggered by inputs, and corresponding outputs, with the critical property of determinism ensuring that identical inputs applied to the same state always produce the same next state and output. This abstraction captures the sequential execution of operations in a service, where the system's evolution is fully determined by its current state and the sequence of inputs received. The core components of a state machine include an initial state s0s_0, a transition function δ(s,i)=s′\delta(s, i) = s' that maps the current state ss and input ii to a new state s′s', and an output function λ(s,i)=o\lambda(s, i) = o that generates an output oo based on the same inputs. These functions are defined such that the machine processes inputs one at a time, updating its state accordingly while producing outputs that reflect the effects of each transition. In computing, state machines provide a natural way to model deterministic services, such as key-value stores, where client requests (e.g., put or get operations) serve as inputs that trigger state changes (e.g., updating or retrieving values) and generate responses as outputs. This modeling approach simplifies the specification and verification of service behavior by reducing it to a well-understood computational paradigm. For replication purposes, state machines rely on the assumption of determinism to guarantee consistent behavior across multiple instances. The state space is typically finite or designed to be serializable, enabling the capture and restoration of state for recovery or synchronization. Where applicable, commutativity of operations—meaning the order of certain inputs does not affect the final state or outputs—facilitates efficient replication strategies, though it is not a universal requirement.

Distributed Services

A distributed service consists of a collection of cooperating processes interconnected by a communication network, designed to provide functionality that persists in the presence of network partitions, communication delays, or individual node failures. These processes collectively execute operations to deliver the service, such as data storage, computation, or coordination, while maintaining the illusion of a single, reliable entity to clients. Distributed services exhibit key properties including scalability, which allows them to handle increased load by distributing workload across additional nodes, and high availability, enabling continued operation despite partial failures. However, without proper coordination mechanisms, they are vulnerable to inconsistencies, where different nodes may arrive at divergent states due to asynchronous processing or partial updates. Interactions between clients and distributed services typically involve asynchronous requests sent over the network, where messages may be lost, delayed, or delivered multiple times, complicating the assurance of correct operation. To enable state machine replication (SMR), such services must be modelable as deterministic state machines, where the overall state evolves through the application of ordered client requests to an initial state.

Problem Statement

Challenges in Distributed Computing

Distributed systems encounter significant challenges stemming from the inherent unreliability of networks, which manifest as unpredictable delays, message losses, and partitions that disrupt communication and coordination among nodes. These issues are exacerbated in large-scale environments, where network partitions have been identified as a primary cause of outages in production cloud systems. Concurrent operations across distributed nodes further complicate matters, often resulting in race conditions where the final system state depends on the non-deterministic timing of events rather than intended logic. Scalability poses another core limitation, as adding nodes does not always yield proportional performance gains due to the quadratic increase in communication overhead and the need for synchronization, constraining systems to sublinear growth in practice. The CAP theorem formalizes a key trade-off in these environments, asserting that a distributed system can only guarantee two out of three properties—consistency, availability, and partition tolerance—in the event of a network partition. For state machine replication, this implies that strong consistency requires forgoing availability during partitions, as replicated state machines prioritize uniform operation sequencing over uninterrupted access. The need for agreement among nodes on a shared sequence of operations is particularly acute in asynchronous settings, where messages can be delayed indefinitely, making it impossible to distinguish between slow processes and failures. The FLP impossibility theorem demonstrates this by proving that no deterministic algorithm can achieve consensus—agreement on a single value or order—while guaranteeing termination in an asynchronous system tolerant to even one crash fault. Non-replicated services, lacking redundancy, are especially prone to failure under these conditions; a single node crash results in total unavailability or data loss, while high loads overwhelm individual components without distribution, potentially leading to divergent client views if partial updates occur before failure.

Fault Tolerance Requirements

State machine replication (SMR) imposes strict fault tolerance requirements to ensure reliable distributed services, primarily through the properties of safety and liveness. Safety guarantees that all non-faulty replicas maintain identical states and generate consistent outputs for the same sequence of inputs, preventing divergent behaviors that could compromise system integrity. This property is fundamental to SMR, as it ensures agreement among replicas regardless of the number or type of failures, provided the system operates within its tolerance bounds. For instance, in crash-fault tolerant models, safety is achieved by requiring that non-faulty replicas execute operations in the same total order, mimicking deterministic state transitions of a centralized service. Liveness complements safety by ensuring that the system makes progress and responds to client requests despite the occurrence of faults, up to a maximum of f faulty replicas in a system with n = 2f + 1 total replicas for crash faults, or n = 3f + 1 for Byzantine faults. Under partial synchrony assumptions—where the system eventually stabilizes after transient asynchrony—liveness requires that valid client requests are eventually processed and acknowledged, preventing indefinite stalls. This progress property is conditional on the absence of excessive faults and the eventual delivery of messages, allowing the system to recover and continue operation without violating safety. Uniformity in SMR mandates that the replicated service exhibits behavior indistinguishable from a non-faulty, centralized implementation, ensuring that clients interact with a logically singular entity despite underlying replication. This equivalence extends to both the sequencing of operations and the final state outcomes, preserving the semantics of the original service. Key metrics for evaluating these requirements include the maximum number of tolerated faults f (typically f < n/3 in Byzantine settings), recovery time (the duration to detect faults and restore consensus), and throughput under partial synchrony (measured as operations per second while maintaining liveness amid delays). These metrics quantify the system's resilience, with recovery times typically low for modern protocols and throughput scaling with network conditions but bounded by fault assumptions.

Failure Models

State machine replication (SMR) must contend with diverse failure models that capture potential faults in nodes and networks, ranging from benign halts to adversarial actions. These models inform the design of protocols by specifying the assumptions under which consistency and liveness can be guaranteed, with tolerance thresholds dictating the number of replicas required. The crash-stop failure model represents the simplest case, where a faulty node abruptly halts execution and remains stopped indefinitely, without recovering or producing further outputs. This model assumes failures are permanent but detectable, allowing SMR systems to mask them through redundancy without needing cryptographic verification. It forms the foundation for many basic SMR implementations, as it avoids the complexity of handling unpredictable behaviors. Byzantine failures introduce greater adversity, permitting faulty nodes to behave arbitrarily—such as sending inconsistent messages, colluding with others, or deviating from the protocol in undetectable ways. Unlike crash-stop faults, Byzantine failures can mimic correct operation intermittently, necessitating stronger consensus mechanisms; for instance, protocols like Practical Byzantine Fault Tolerance (PBFT) address them explicitly. To tolerate up to f such faults, SMR systems require at least n = 3f + 1 replicas, ensuring a majority of honest nodes can outvote malicious ones. Network-related failures include omission failures, where a node or link fails to send or receive messages as intended, and timing failures, where messages arrive but exceed specified delivery bounds. These are often analyzed under partial synchrony assumptions, where the system eventually stabilizes despite unbounded delays or losses, contrasting with fully synchronous models that enforce strict timing. Omission and timing faults complicate input ordering in SMR but are typically bounded by the protocol's synchrony model. Distinctions between fail-stop and Byzantine models highlight detectability: fail-stop failures are crashes that can be immediately recognized (e.g., via heartbeat timeouts), enabling simpler recovery with n > 2f replicas for crash tolerance in ordering phases. In contrast, Byzantine malice remains covert, demanding the higher n > 3f threshold to achieve agreement despite potential deception. These thresholds ensure SMR maintains deterministic state equivalence across surviving replicas.

Core Mechanisms

Total Order Broadcast for Inputs

Total order broadcast is a fundamental communication primitive in state machine replication that ensures all non-faulty replicas deliver the same set of input messages in the identical sequence, thereby providing a consistent linear order for processing client requests across distributed nodes. This mechanism is essential for maintaining replica determinism, as it prevents discrepancies that could arise from varying delivery orders in asynchronous networks. In systems tolerant to crash faults, total order broadcast is typically implemented via atomic broadcast protocols, which guarantee three properties: validity (if a correct process broadcasts a message, it eventually delivers it), agreement (no two correct processes deliver different sets of messages), and total order (if one correct process delivers message m1m_1 before m2m_2, then every correct process delivers m1m_1 before m2m_2). The total order property can be formally expressed as: If a correct process p delivers m1 before m2, then every correct process q delivers m1 before m2.\text{If a correct process } p \text{ delivers } m_1 \text{ before } m_2, \text{ then every correct process } q \text{ delivers } m_1 \text{ before } m_2. For environments susceptible to Byzantine faults, where replicas may behave arbitrarily, protocols employ uniform total order broadcast to extend these guarantees; here, uniformity ensures that even faulty broadcasters cannot cause inconsistencies among correct replicas, satisfying uniform agreement (all processes, including faulty ones, deliver the same messages as correct ones if they deliver at all) and uniform total order (the delivery order is consistent across all processes that deliver). Leader-based algorithms like Paxos and Raft achieve total order by designating a leader to propose and sequence messages, appending them to a replicated log before dissemination to followers for agreement and commitment. In Paxos, the leader coordinates phases of prepare and accept to ensure a unique value is chosen per log slot, enforcing linearizability and total order among non-faulty replicas. Raft simplifies this with distinct subproblems—leader election, log replication, and safety—where the leader assigns sequence numbers to entries, broadcasting them for replication and ensuring followers apply them in order upon majority acknowledgment. Viewstamped Replication (VR), an earlier protocol, organizes ordering around stable views of replica sets, with a primary proposing messages and backups voting to advance the view and commit operations in sequence; this view-based approach handles primary failures by electing new primaries without reordering prior messages. These algorithms collectively enable state machine replicas to process ordered inputs uniformly, forming the basis for subsequent state updates.

State Synchronization and Processing

In state machine replication, replicas maintain consistency by executing the same state transition function δ\delta on a totally ordered sequence of client requests, starting from an identical initial state s0s_0. Each replica applies δ(si−1,ri)\delta(s_{i-1}, r_i) sequentially for each ordered request rir_i, producing a deterministic sequence of states s1,s2,…,sns_1, s_2, \dots, s_n. This process ensures that all non-faulty replicas evolve their states in lockstep, as long as they receive the same ordered inputs and begin from the same starting point. The transition function δ\delta typically encapsulates the service's logic, such as updating a database or processing transactions, and is invoked atomically to avoid partial executions. To guarantee state equivalence across replicas, the entire execution must be deterministic: identical initial states and input sequences yield identical outputs and final states. This property relies on the absence of non-deterministic elements in the application code, such as platform-specific behaviors or external interactions, which could cause replicas to diverge even under the same inputs. Seminal formulations emphasize that determinism is foundational, with all replicas required to implement the exact same δ\delta and handle inputs uniformly. Non-determinism arises in practical systems from sources like random number generation or asynchronous external calls, potentially leading to inconsistent states. To mitigate this, replicas employ techniques such as seeding pseudo-random number generators with cryptographically secure values agreed upon via the consensus protocol, ensuring all nodes produce identical random sequences. For example, verifiable random functions (VRFs) or shared coins derived from threshold signatures provide deterministic randomness that is tamper-resistant against Byzantine faults. These methods confine non-determinism to controlled, replicable forms without altering the core deterministic execution model. State consistency is verified periodically through cryptographic mechanisms to detect and correct divergences early. Replicas compute hashes of their states at predefined checkpoints—such as after every kk requests—and exchange these hashes to confirm agreement; mismatches trigger recovery actions like state transfer. More efficient verification uses Merkle trees, where the state is represented as a tree of hashes, allowing replicas to prove and compare subtrees without full state transmission. This approach scales well for large states, as seen in durable SMR systems that integrate hashing with logging for ongoing audits.

Output Handling and Client Interactions

In state machine replication (SMR), the output function, denoted as λ(state, input), is applied after updating the state with a client request, producing a deterministic response based on the current state and the input operation. This ensures that all non-faulty replicas generate identical outputs for the same input sequence, maintaining consistency across the system. Clients interact with the replicated service by multicasting requests to replicas or directing them to a primary replica, which sequences and disseminates them for total-order execution. To ensure reliability, clients collect responses from a quorum of replicas—typically f+1 matching replies in Byzantine settings, where f is the maximum number of faulty replicas tolerated—and accept the result only upon receiving this quorum certificate. For read-only operations, clients may multicast requests directly to all replicas and proceed after obtaining matching replies from a quorum, enabling any consistent replica to respond without full write coordination. This quorum-based protocol for reads and writes guarantees linearizability while allowing load distribution among replicas. Optimizations enhance output efficiency, such as the primary-backup model where the primary replica executes requests early and sends speculative responses to nearby clients, reducing latency to as low as one round-trip time when co-located. Speculative execution further accelerates responses by allowing clients to proceed based on early replies from the primary or a single replica, with subsequent quorums validating or aborting operations via dependency tracking, achieving speedups of up to 19× in microbenchmarks for operations like file reads and writes. Digest-based replies, where most replicas send compact hashes and one provides the full result, minimize bandwidth while preserving verifiability. In asynchronous networks, challenges arise from potential message duplicates or losses, which are addressed through sequence numbers and timestamps in requests and replies to detect and discard duplicates, alongside client-initiated retransmissions if no quorum is received within a timeout. Authentication via message authentication codes (MACs) ensures reply integrity, preventing faulty replicas from forging responses, while receiver-side status messages aid in recovering lost replies without unnecessary flooding. These mechanisms maintain output correctness without relying on synchronized clocks.

Failure Handling

Detection and Auditing

In state machine replication (SMR), detection of faulty replicas is essential to maintain system liveness and safety, particularly in asynchronous environments where the Fischer-Lynch-Paterson (FLP) impossibility theorem precludes deterministic consensus without additional assumptions. For crash faults, replicas commonly employ heartbeats—periodic messages exchanged among nodes—to monitor liveness, with timeouts triggering failure suspicion if no heartbeat is received within a predefined interval. This mechanism ensures eventual detection of crashed replicas, though the choice of timeout must balance responsiveness against network variability to minimize disruptions. Byzantine faults, involving arbitrary malicious behavior, require stronger authentication to detect deviations from protocol rules. Digital signatures are widely used to verify message authenticity and integrity, preventing faulty replicas from forging votes or commands that could mislead honest ones. In protocols like Practical Byzantine Fault Tolerance (PBFT), MACs authenticate critical messages during pre-prepare, prepare, and commit phases, while digital signatures are used for view-change and new-view messages, enabling replicas to identify and quarantine Byzantine actors through quorum-based validation. Failure detectors provide an abstract oracle for crash detection in asynchronous systems, classified by properties of completeness (eventual detection of all crashes) and accuracy (minimizing false suspicions of healthy processes). The Ω failure detector, the weakest necessary for solving consensus amid FLP constraints, eventually ranks processes by estimating leadership stability, outputting a trusted set excluding crashed nodes with high probability over time. Proof-of-correctness in SMR leverages these detectors alongside cryptographic tools, ensuring verifiable agreement on state transitions. Auditing verifies system integrity post-execution by maintaining logs of inputs, deterministic state transitions, and outputs at each replica, allowing replay to reconstruct and compare states for discrepancies. Cross-replica comparisons, often periodic or triggered by suspicion, involve exchanging checkpoints or hashes of logs to detect inconsistencies arising from faults, with deterministic SMR guaranteeing identical outputs among honest replicas. In execute-verify paradigms, such as those extending traditional SMR, logs enable non-deterministic verification by replaying operations against speculated executions, confirming fault-free behavior without halting progress. In asynchronous settings, detection metrics focus on false positives (suspecting healthy replicas, leading to unnecessary reconfiguration) and false negatives (missing actual crashes, risking stalled progress). Unreliable detectors like Ω permit infinite mistakes but ensure eventual accuracy, with false positive rates approaching zero under partial synchrony, though asynchrony can inflate them during partitions. These metrics guide timeout tuning, prioritizing completeness for safety while bounding accuracy for liveness.

Recovery from Failures

In state machine replication (SMR) systems tolerant to crash faults, recovery from replica failures typically involves restarting the affected replica from a recent checkpoint—a snapshot of the replicated state—and replaying the log of committed operations that occurred since that checkpoint to restore consistency with other replicas. This approach ensures that the recovering replica deterministically reconstructs the exact state it would have reached had it not failed, leveraging the idempotent and deterministic nature of state transitions in SMR. For instance, protocols like those in the original SMR framework store checkpoints periodically on stable storage, allowing recovery without relying on external state transfer, provided the log is durable. For systems handling Byzantine faults, recovery procedures focus on excluding faulty replicas through view changes, where a new configuration (view) of the replica set is established by correct replicas, replacing or isolating nodes exhibiting arbitrary behavior such as sending conflicting messages. In Practical Byzantine Fault Tolerance (PBFT), backups initiate a view change if the primary fails to progress requests, collecting messages from at least 2f+1 replicas (where f is the maximum number of faulty nodes) to reconstruct the latest stable state and elect a new primary, ensuring that quorums intersect in at least f+1 correct nodes for consistent state agreement. This quorum intersection property guarantees that the recovered state reflects decisions made by a majority of honest replicas, preventing faulty nodes from corrupting the global state. SMR protocols establish stable recovery points through coordinated checkpointing, where all correct replicas agree on a sequence number up to which the state is identical and durable, often requiring acknowledgments from a quorum to certify stability. These points serve as anchors for recovery, allowing crashed or faulty replicas to synchronize without reprocessing the entire history, as checkpoints capture the state at agreed-upon milestones in the total order of operations. Under partial synchrony assumptions, SMR recovery guarantees bounded time to restore liveness after failures, as networks eventually stabilize with message delays limited by a known bound Δ following the global stabilization time (GST), enabling correct replicas to complete view changes and checkpoint agreements within O(Δ) time. This ensures that, once GST is reached, the system progresses without indefinite stalls, provided the number of faults remains below the tolerance threshold f < n/3 (for n replicas).

Extensions and Optimizations

Logging and Checkpoints

In state machine replication (SMR), input logs maintain an append-only sequence of client requests ordered via total order broadcast, allowing replicas to replay operations and reconstruct the deterministic state machine's state during recovery or synchronization. These logs ensure that all non-faulty replicas process the same sequence of inputs, preserving consistency even after crashes. To achieve durability, input logs are implemented using write-ahead logging (WAL), where requests are atomically appended to stable storage before execution, guaranteeing that committed operations survive failures without loss. Checkpoints complement logging by creating periodic, stable snapshots of the state machine's state, typically after every k operations (e.g., k = 100 or 256 in practical systems), to bound log size and optimize recovery. During checkpointing, replicas compute a cryptographic hash of the current state and the log suffix since the previous checkpoint, forming a certificate that confirms a consistent point across replicas. A checkpoint becomes stable once 2f+1 replicas confirm the same state digest. This process integrates with WAL by flushing the log to disk synchronously at checkpoint intervals, after which the prefix of the log up to the checkpoint can be truncated. Garbage collection follows once a quorum of replicas acknowledges the checkpoint, discarding obsolete entries to reclaim storage while retaining only the active log tail. The primary benefits of logging and checkpoints in SMR arise during recovery, where a failed replica loads the most recent checkpoint from stable storage and replays only the subsequent log entries, reducing recovery time from O(n)—proportional to the entire operation history—to O(m), where m is the shorter tail length (m ≪ n). This approach minimizes I/O overhead and downtime, as demonstrated in systems like PBFT, where checkpoints every k requests (e.g., k=100), becoming stable after 2f+1 confirmations, enable rapid state restoration without full replays. In Raft-based implementations, snapshots similarly compact logs, allowing followers to install states directly and truncate histories, further enhancing scalability under high throughput. Techniques like parallel WAL writes can further dilute logging latency without compromising durability, as explored in durable SMR optimizations.

Dynamic Reconfiguration

Dynamic reconfiguration in state machine replication (SMR) enables the adaptation of the replica set by adding or removing nodes while preserving system safety—ensuring consistent state across replicas—and liveness—guaranteeing progress under partial synchrony. This process is critical for handling node failures, scaling resources, or replacing faulty hardware without downtime. Protocols achieve this through structured view changes, where a "view" represents the current configuration of replicas, including their membership and quorum size. For crash-fault tolerant (CFT) protocols like Viewstamped Replication (VR), total replicas are at least 2f+1 to tolerate f crash failures, with quorums of size f+1. For Byzantine fault-tolerant (BFT) variants, total replicas are at least 3f+1, with quorums of size 2f+1. Reconfigurations are treated as special replicated commands, agreed upon using the underlying consensus mechanism, such as Paxos or Viewstamped Replication (VR). Quitting a node occurs via graceful removal during a view change, initiated by a privileged client request to update the configuration. The current primary (or leader) proposes the new view excluding the departing node, committing it only after a quorum of the old configuration agrees. This ensures quorum preservation, as the new quorum must intersect with the old one to maintain safety; for instance, in a CFT system with 2f+1 replicas, removing one node adjusts the fault tolerance threshold, typically reducing the maximum tolerable faults from f to f-1 in minimal configurations, while preserving quorums that intersect with the old configuration for safety. Once committed, non-quorum replicas in the old view are notified to shut down, preventing them from processing further requests. This decentralized approach avoids centralized coordinators, reducing single points of failure. Joining new nodes integrates them into the active view after they catch up to the current state, typically via log dissemination or full state transfer from existing replicas. A reconfiguration request specifies the new members, and upon commitment in the old view, the primary instructs the new nodes to fetch committed operations—often using checkpoints and operation logs—to replicate the state machine. Only after verifying the state (e.g., via Merkle trees for efficiency) do the new nodes transition to the "normal" operating status and begin participating in quorums. This catch-up phase ensures the joining nodes do not violate linearizability, as they start processing requests only from the reconfiguration point onward. Protocols for dynamic reconfiguration leverage consensus phases to agree on new views, exemplified in Paxos-based systems. The process begins with a phase-1 proposal of the new configuration as a value, where a leader collects promises from a quorum to establish a unique proposal number. In phase-2, acceptors respond with prior values if any, allowing the leader to learn the configuration via a phase-2b learn message once a quorum accepts. During reconfiguration, up to f faults are tolerated by requiring quorums to overlap, ensuring no conflicting views form. Viewstamped Replication follows a similar structure, using prepare and commit phases for reconfiguration requests, with the primary halting normal operations until the new view stabilizes. These phases maintain total order on operations across views, treating the reconfiguration as an atomic broadcast. Key challenges include avoiding split-brain scenarios, where disjoint subsets of replicas operate independently, potentially diverging states. This is mitigated by committing the reconfiguration in an intersecting quorum before activating the new view, and by requiring old replicas to confirm shutdown (e.g., via f'+1 acknowledgments, where f' is the new fault tolerance). Additionally, views must increase monotonically—each new view has a higher identifier than predecessors—to prevent reversion to outdated configurations and ensure progress; for example, VR resets view numbers to zero within a new epoch but advances the epoch counter globally. These mechanisms balance availability during changes, though large state transfers can introduce brief pauses in liveness.

State Transfer Techniques

State transfer techniques in state machine replication enable new or recovering replicas to synchronize with the current system state, ensuring consistency across all participants during joins, view changes, or failure recoveries. These methods are crucial for maintaining liveness and safety in distributed systems, particularly when replicas must catch up without halting ongoing operations. By transferring state efficiently, SMR protocols minimize downtime and resource overhead while preserving the deterministic execution model. Key techniques include full state dumps, complete log replays, and hybrid snapshot-plus-delta approaches. A full state dump transfers the entire current state from an operational replica to the target, offering simplicity but consuming significant bandwidth for large states typical in database-backed services. Log replay involves sending the full history of committed operations for the new replica to execute sequentially, which avoids state serialization costs but incurs high computational latency for long logs. The predominant hybrid method combines a periodic checkpoint—essentially a consistent snapshot of the state—with the delta log of subsequent operations; the new replica installs the snapshot and replays only the recent log to reach the current sequence number, balancing transfer volume and processing time. This approach leverages checkpoints, as detailed in prior sections on logging, to bound log growth. In the Practical Byzantine Fault Tolerance (PBFT) protocol, state transfer integrates with view changes and checkpointing to handle Byzantine faults securely. When a replica joins or recovers, it requests the state during the pre-prepare phase or separately; the primary responds with a stable checkpoint containing the state, a sequence number, and a digest (cryptographic hash) for verification, along with the log suffix if needed. For large states, PBFT avoids full dumps by relying on periodic checkpoints created every k requests (e.g., k=100), which become stable after 2f+1 replicas confirm the state, allowing partial transfers authenticated via message authentication codes (MACs). This ensures the receiver can validate state correctness without trusting the sender, using hashes to detect tampering. Trade-offs in PBFT include elevated bandwidth for hash computations and state serialization versus reduced replay time, with empirical results showing transfer times scaling with state size but mitigated by checkpoint frequency. Viewstamped Replication (VR) employs a dedicated state transfer phase for non-crashed but lagged replicas, initiated by a GetState message to the primary. The primary replies with a State message carrying the current view's checkpoint snapshot, view number, and delta log entries up to the last stable sequence, enabling the receiver to replay and verify consistency. VR handles large database states by supporting incremental transfers of log segments, with security ensured through signed messages and state hashes to confirm integrity. In optimizations, VR pipelines log delivery to overlap network latency with replay computation, reducing overall synchronization time. For bandwidth-constrained settings, compression of snapshots or differential syncing—transferring only modified state portions via change vectors—further minimizes data volume, though at the cost of added encoding/decoding overhead. Across these techniques, trade-offs center on bandwidth efficiency versus recovery latency and security overhead. Full dumps or unoptimized replays suit small states but scale poorly, potentially taking minutes for gigabyte-scale databases, while snapshot-delta methods cut bandwidth by up to 90% in log-heavy workloads at the expense of replay CPU cycles. Secure mechanisms like hashes and signatures add negligible latency (e.g., SHA-256 computations) but are essential for Byzantine resilience, verifying transfers without full re-execution. Pipelining and compression, as in VR and PBFT variants, achieve up to 2-3x speedup in geo-distributed setups by parallelizing I/O and reducing payload sizes.

Historical and Modern Developments

Origins and Key Milestones

The concept of state machine replication (SMR) emerged from foundational work in distributed systems during the late 1970s, particularly Leslie Lamport's introduction of logical clocks in 1978, which provided a mechanism for totally ordering events across distributed processes without relying on physical time. This innovation addressed the challenge of establishing consistent event sequences in asynchronous environments, laying the groundwork for replicating state deterministically among multiple nodes to ensure fault tolerance. Early explorations in the 1980s built on this by integrating fault-tolerant computing principles, focusing on reliable multicast and ordering protocols to coordinate replicas amid potential failures. This included Fred Schneider's 1982 work on synchronization omissions, which extended the approach to handle crash-stop failures. A key advancement came from Dale Skeen's 1982 work on quorum-based commit protocols, which enabled total order broadcast for atomic operations in distributed databases, ensuring that all non-faulty processes deliver messages in the same sequence despite crashes. This approach influenced subsequent SMR designs by emphasizing quorum mechanisms for agreement on operation order. In parallel, Jim Gray's research in the 1980s, including his 1986 comparison of Byzantine agreement and two-phase commit protocols, highlighted practical implementations of fault tolerance in transaction processing systems, demonstrating how replicated state could tolerate single faults through modular redundancy in environments like Tandem computers. Fred Schneider's 1990 tutorial formalized the state machine approach to fault-tolerant services, articulating SMR as a method to replicate a deterministic state machine across servers, where replicas execute the same sequence of client requests to maintain identical states, even under fail-stop failures. This framework unified prior ideas, proving that non-deterministic services could be transformed into deterministic ones for replication, and it extended to Byzantine fault models by requiring total order delivery. A major milestone arrived in 1999 with Miguel Castro and Barbara Liskov's Practical Byzantine Fault Tolerance (PBFT) protocol, which provided an efficient, partially synchronous algorithm tolerating up to one-third Byzantine faults while achieving practical performance for real-world systems. By the late 1990s, SMR protocols had evolved from strictly synchronous assumptions—where bounded delays enabled simpler consensus—to partially synchronous models that better suited unreliable networks, setting the stage for asynchronous advancements in the 2000s. Lamport's 1998 Paxos protocol exemplified this transition by offering a crash-fault-tolerant consensus mechanism adaptable to SMR, influencing later Byzantine-resilient designs.

Contemporary Implementations and Advances

Contemporary state machine replication (SMR) implementations emphasize practicality, scalability, and integration with blockchain technologies. Raft, introduced in 2014, prioritizes simplicity and understandability in consensus protocols for replicated state machines, decomposing the problem into leader election, log replication, and safety mechanisms to facilitate easier implementation and debugging compared to predecessors like Paxos. Its design has made it widely adopted in distributed systems for fault-tolerant coordination. In blockchain contexts, HotStuff (2018) advances SMR by providing a leader-based Byzantine fault-tolerant (BFT) protocol optimized for partial synchrony, enabling linear communication complexity and scalability for high-throughput applications like permissionless networks. Similarly, Tendermint (2014) serves as a BFT SMR engine that separates consensus from application execution via the Application Blockchain Interface (ABCI), powering the Cosmos ecosystem by allowing developers to build interoperable blockchains with deterministic state transitions across replicas. These implementations highlight SMR's evolution toward modular designs that support blockchain scalability while maintaining fault tolerance up to one-third Byzantine faults (f < n/3). Recent advances focus on compositionality to enable modular SMR systems. A 2024 ACM paper formally defines SMR compositionality, allowing independent development and integration of consensus, execution, and storage components while preserving overall system guarantees, which addresses limitations in monolithic designs and facilitates hybrid architectures. Disaggregated architectures further separate consensus from execution in SMR to enhance scalability. As of 2025, innovations in network synchrony drive low-latency SMR. An arXiv preprint proposes building practical SMR using enhanced network synchrony, achieving sub-2μs latency bounds across clusters via kernel-bypass and multithreading, which boosts throughput without increasing end-to-end delays in real-world deployments. These developments underscore SMR's ongoing adaptation to modern hardware and blockchain demands for efficient, verifiable state synchronization.

References

  1. https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/statemachines.pdf
  2. https://www.di.fc.ul.pt/~bessani/publications/tutorial-smr.pdf
  3. https://arxiv.org/pdf/2008.02512
  4. https://dl.acm.org/doi/pdf/10.1145/3380787.3393681
  5. https://dl.acm.org/doi/10.1145/3436728
  6. https://research.google.com/archive/spanner-osdi2012.pdf
  7. https://dl.acm.org/doi/10.1145/3380787.3393686
  8. https://arxiv.org/pdf/2207.00500
  9. https://dl.acm.org/doi/10.1145/3712031.3712333
  10. https://www.cs.cornell.edu/fbs/publications/SMSurvey.pdf
  11. https://theses.hal.science/tel-04588230v1/document
  12. https://dl.acm.org/doi/10.1145/98163.98167
  13. https://cacm.acm.org/practice/eventual-consistency-today/
  14. https://queue.acm.org/detail.cfm?id=1466448
  15. https://www.usenix.org/system/files/osdi18-alquraan.pdf
  16. https://www.researchgate.net/publication/2346369_What_are_Race_Conditions_-_Some_Issues_and_Formalizations
  17. http://www.sce.carleton.ca/faculty/woodside/pubs/scal00.pdf
  18. https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf
  19. https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf
  20. https://www.baeldung.com/cs/distributed-systems-prevent-single-point-failure
  21. http://pmg.csail.mit.edu/papers/osdi99.pdf
  22. https://www.jaist.ac.jp/jinzai/Paper/p372-defago.pdf
  23. https://raft.github.io/raft.pdf
  24. https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
  25. http://pmg.csail.mit.edu/papers/vr-revisited.pdf
  26. https://cachin.com/cc/papers/byzrepl.pdf
  27. https://www.usenix.org/system/files/conference/atc13/atc13-bessani.pdf
  28. https://eprint.iacr.org/2020/758.pdf
  29. https://www.microsoft.com/en-us/research/wp-content/uploads/2017/01/thesis-mcastro.pdf
  30. https://www.usenix.org/legacy/event/nsdi09/tech/full_papers/wester/wester.pdf
  31. https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p225-chandra.pdf
  32. https://www.usenix.org/system/files/conference/osdi12/osdi12-final-190.pdf
  33. https://opus4.kobv.de/opus4-uni-passau/files/1505/thesis.pdf
  34. https://cse.buffalo.edu/~eblanton/course/cse586-2018-0s/materials/2018S/07-failure_detectors.pdf
  35. https://www4.cs.fau.de/Publications/2021/distler_21_csur.pdf
  36. https://software.imdea.org/~gotsman/papers/multishot-dc.pdf
  37. https://www.usenix.org/system/files/conference/atc12/atc12-final74.pdf
  38. https://lamport.azurewebsites.net/pubs/vertical-paxos.pdf
  39. https://www.inf.usi.ch/faculty/pedone/Paper/2017/2017ICDCSa.pdf
  40. https://lamport.azurewebsites.net/pubs/time-clocks.pdf
  41. https://ecommons.cornell.edu/server/api/core/bitstreams/a4d6f5b4-0d7d-444e-8994-752e9ab6ff8f/content
  42. https://jimgray.azurewebsites.net/papers/tandemtr88.6_comparisonofbyzantineagreementandtwophasecommit.pdf
  43. https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14.pdf
  44. https://arxiv.org/abs/1803.05069
  45. https://docs.cometbft.com/main/spec/abci/
  46. https://css.csail.mit.edu/6.824/2014/papers/castro-practicalbft.pdf
  47. https://dl.acm.org/doi/10.1145/3697090.3697106
  48. https://arxiv.org/abs/2507.12792
Add your contribution
Related Hubs
User Avatar
No comments yet.