An Introduction to Distributed Systems

A distributed system is a mechanism in which multiple nodes connected by a network cooperate so as to behave like a single system. Problems that don’t arise on one machine — partial failure, network partition, message delay and reordering — become the normal state of affairs, so the premises differ from single-process design from the start.

This field has a thick accumulation of books and papers, and learning it piecemeal makes it easy to lose sight of the whole. So this article surveys the main topics of distributed systems while referring to the chapter structures of representative textbooks and papers, and among them digs into Raft (a distributed consensus algorithm) — heavy on implementation and easily misunderstood — with comparisons against other consensus algorithms.

Recent systems such as Kubernetes are designed on the basis of distributed systems theory in order to raise availability. To understand them, this article summarizes distributed systems systematically.

Table of Contents and the Structure I Referred To

Distributed systems textbooks (Tanenbaum & Van Steen’s Distributed Systems, Kleppmann’s Designing Data-Intensive Applications, van Steen’s Distributed Systems (freely available edition), and so on) tend to structure their chapters roughly in the following order. This article follows that flow.

1. What a distributed system is, and why it’s hard
2. The history of distributed systems theory
3. System models (synchronous/asynchronous, failure models)
4. Time and ordering (physical clocks, logical clocks)
5. Communication reliability (RPC, idempotency, delivery guarantees)
6. Consistency models and CAP/PACELC
7. Replication and partitioning
8. The basics of distributed consensus, Paxos, and FLP impossibility
9. The Raft algorithm in detail (including where it sits among consensus algorithms as a whole)
10. Distributed transactions (2PC/3PC, Sagas)
11. Failure detection and membership management (Gossip, SWIM)
12. Combinations seen in real systems (etcd, ZooKeeper, Kafka, Spanner)

1. What Is a Distributed System?

A distributed system refers to a mechanism in which multiple computers that can fail independently cooperate, exchanging only messages over a network, so that from the user’s point of view they act as one coherent system.

What decisively differs from single-process design can be boiled down to the following three points.

Because of these three points, distributed systems design doesn’t assume “it always works correctly,” and instead centers on “can the whole keep behaving sensibly even when part of it breaks?”

2. The History of Distributed Systems Theory

Distributed systems theory is a field where new ideas and algorithms were born each time the problems actually faced changed. Laying it out as a timeline reveals the flow of what the problems were and how they were solved.

Surveying this timeline, distributed systems theory can be organized as having addressed roughly three stages of problems in order.

1. How to define ordering (late 1970s onward): defining the before/after relationship of events in the absence of a single clock (Lamport timestamps, vector clocks)
2. How to achieve consensus safely and understandably (1980s–2014): getting multiple nodes to agree on one value even with failures and network partitions (Paxos, Raft)
3. How to scale consensus (late 2010s onward): addressing the problem of a single-leader consensus group becoming a bottleneck (Multi-Raft, EPaxos, etc.)

The following chapters are easier to follow if you read them in terms of how each of these three stages of problems is solved.

3. System Models (Synchronous/Asynchronous, Failure Models)

To make the discussion rigorous, we first make explicit “what premises we’re placing.” That’s the etiquette of distributed systems.

Synchronous and Asynchronous Models

• Synchronous model: there are known upper bounds on message delivery and process execution time. Failures can be reliably determined by timeout
• Asynchronous model: there is no upper bound on delivery or execution time. In principle you cannot distinguish “merely slow” from “broken”

Real networks are not strictly synchronous, so many distributed algorithms assume a partial synchrony model, “behaves roughly synchronously in practice.” The safety arguments of Raft and Paxos also rest on this realistic premise.

Failure Models

Most consensus algorithms for middleware, Paxos and Raft included, assume crash-stop/crash-recovery and don’t handle Byzantine failures (nodes that lie). This is a deliberate simplification to keep the design simple, and it’s worth remembering as the point that “a consensus algorithm is not an all-purpose fault-tolerance algorithm.” Where each consensus algorithm sits in the overall landscape is organized in the comparison table in chapter 8.

4. Time and Ordering

There is no single correct clock in a distributed system. Each node’s physical clock drifts, and even synchronized with NTP an error of milliseconds to tens of milliseconds remains. So many distributed algorithms use logical ordering rather than physical time.

Lamport Timestamps

Lamport’s logical clock is a simple mechanism where each node just advances a counter by the following rules.

1
2
3
4
5
6
7
8
9

on local event:
  counter = counter + 1

on send message:
  counter = counter + 1
  attach counter to message

on receive message(msg):
  counter = max(counter, msg.counter) + 1

By these rules, whenever there is a “event A happened before event B” (happens-before) relation, necessarily $counter(A) < counter(B)$. The converse, however, does not hold. That is, Lamport timestamps alone cannot determine the before/after relation of two causally unrelated events.

Vector Clocks

Vector clocks make up for the limitation of Lamport timestamps (that they can’t determine whether a causal relation exists). You manage an array with a counter per node, incrementing your own entry on each message send and receive, and taking the element-wise maximum on receive. Comparing two timestamps, if one is greater than or equal to the other in every element you can judge it “happened before,” and otherwise “concurrent.” Dynamo-style key-value stores are known as an example of using vector clocks for conflict detection.

5. Communication Reliability and RPC

Inter-node communication in a distributed system must be designed on the premise that messages can be lost, duplicated, or delayed. There are mainly three kinds of delivery guarantee.

“True exactly-once delivery” is in principle difficult, since the network can’t be fully trusted. Many real systems achieve it pseudo-practically using request IDs for deduplication and operations designed to be idempotent. Raft’s client interaction likewise commonly uses a design that gives each request a unique ID to prevent double application of duplicate commands.

6. Consistency Models and CAP/PACELC

The word “consistency” refers to very different things depending on context, so grasping the levels first makes conversations line up.

The CAP Theorem and PACELC

The CAP theorem is known as the theorem that “you cannot simultaneously satisfy Consistency, Availability, and Partition tolerance,” but since network partitions do happen in reality, it’s more practical to understand it as the choice of “when partitioned, do you take C or A?” The basic idea of the CAP theorem and a concrete explanation using web systems as an example are also covered in an earlier article I wrote, Ensuring high availability of systems, and etcd and Raft (in Japanese), so please refer to that as well.

PACELC extends this and organizes it along two axes: “when partitioned (Partition), do you prioritize Consistency or Availability, and otherwise (Else), in normal times, do you prioritize Latency or Consistency?” Raft- and Paxos-based systems prioritize consistency (C) both when partitioned and in normal times, and as the price, are designed to lose write availability while the leader is unreachable.

7. Replication and Partitioning

Systems handling large-scale data combine replication (fault tolerance through copies) and partitioning (scale-out through splitting).

• Single-leader: only one node accepts writes, and the others become read-only replicas. Consistency is easier to manage, and Raft’s leader is close to this scheme
• Multi-leader: writes are accepted at multiple sites and conflicts are resolved afterward. It’s easier to reduce write latency in geo-distribution, but conflict resolution becomes complex
• Leaderless: as in Dynamo, read/write consistency is ensured by a quorum ($W + R > N$)

In partitioning, consistent hashing is often used to hold down the cost of redistribution when nodes are added or removed. The idea is to treat the hash space as a ring and localize changes in assigned ranges to only some of the nodes.

8. The Basics of Distributed Consensus

Distributed consensus refers to a procedure by which multiple nodes all agree on exactly one value among those proposed, even in the presence of failures and communication faults. It underlies many distributed systems: replicated logs, leader election, distributed locks, and so on.

FLP Impossibility

Fischer, Lynch, and Paterson (1985) proved that in an environment satisfying all three of the following conditions, there necessarily exist cases where no deterministic algorithm whatsoever can establish consensus (FLP impossibility).

• The asynchronous model (no upper bound on message delivery time)
• One or more processes may crash (fail-stop)
• The algorithm is deterministic (the same input always produces the same output)

The intuition of the proof is as follows. In the asynchronous model, the receiver cannot in principle distinguish whether a message is merely delayed or whether the sending process has failed and it will never arrive. Even if a consensus algorithm tries to finalize a conclusion at some point, positing an adversarial scheduler that can manipulate message delivery timing in the worst possible order, that scheduler can keep delaying just the one message right before the decision is finalized, postponing the finalization of consensus indefinitely. This isn’t a defect of a particular implementation; it’s a theoretical limit applying to any algorithm as long as the three conditions above hold.

This does not mean “distributed consensus is impossible.” Paxos and Raft actually work correctly. What FLP impossibility shows is limited strictly to the point that “as long as the premise of the asynchronous model is not broken, there is no deterministic algorithm guaranteeing ‘always terminates in finite time’ including the worst case.” Practical consensus algorithms, like the Paxos and Raft covered next, bring in randomized timeouts and the premise of partial synchrony, sidestepping this theoretical wall in a form that isn’t a problem in practice.

Paxos

Paxos (Lamport, 1998/2001) is the classic solution to distributed consensus, decomposing the processing into the following three roles.

• Proposer: proposes a value
• Acceptor: votes on whether to accept a proposal (consensus is established with acceptance by a majority)
• Learner: learns the agreed value

The basic form (Basic Paxos) proceeds in the following two phases.

1. Prepare/Promise phase: the proposer draws a unique proposal number and sends Prepare to the acceptors. An acceptor promises not to accept any proposal with a smaller number, and if it has already accepted a value, returns it to the proposer
2. Accept/Accepted phase: the proposer sends, as Accept, the value returned via Promise if there was one, and otherwise its own proposed value, to a majority of acceptors. If a majority return Accepted, consensus is established

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# Pseudocode on the proposer side (simplified)
n = generate_unique_proposal_number()
promises = send Prepare(n) to majority of acceptors, wait for promises

if len(promises) < majority:
  retry with a higher n

# if a value has already been accepted, carry it over (the crux of safety)
value = highest_numbered_accepted_value(promises) or my_own_value

accepted = send Accept(n, value) to majority of acceptors, wait for accepted
if len(accepted) >= majority:
  value is chosen

There are two main reasons Paxos is said to be hard.

1. Agreeing on even a single value requires two phases of round trips, and retries can occur due to collisions of proposal numbers. The safety proof (that with a majority of acceptors no contradiction arises) is robust but hard to follow intuitively
2. To replicate a whole log in production you need Multi-Paxos, which repeatedly runs instances of Paxos, but the original paper doesn’t specify this in detail, leaving much — stable leader election, filling gaps in the log — for implementers to design on their own

Raft (Ongaro & Ousterhout, 2014) is an algorithm redesigned with understandability as its first goal, specifying from the outset even those “parts implementers must fill in,” while retaining safety equivalent to Paxos. Concretely, it fixes as a premise the thing Multi-Paxos left ambiguous — “always stand up exactly one strong leader” — and explicitly decomposes the problem into three independent ones: leader election, log replication, and safety. The paper’s title is likewise “In Search of an Understandable Consensus Algorithm”, and comparative experiments for educational purposes report that Raft is more readily understood.

An Overall Comparison of Distributed Consensus Algorithms

Since Paxos, several derived and alternative algorithms have appeared depending on differences in goals and premises. Organizing where Raft sits in the whole gives the following.

Organized this way, Raft can be seen to occupy the position of “a strong-leader consensus algorithm that has Paxos-family safety while prioritizing understandability and ease of implementation.” Because of the single leader there’s a limit to write scalability, and to compensate, leaderless schemes like the Multi-Raft and EPaxos described later were born.

9. The Raft Algorithm in Detail

As compared in the previous section, among the many distributed consensus algorithms, Raft is designed to “retain Paxos-equivalent safety while prioritizing understandability on the premise of a strong leader.” From here we dig into Raft’s internal operation. Raft is designed by decomposing it into three largely independent subproblems.

1. Leader election: choose one leader from among the cluster
2. Log replication: replicate the commands the leader receives to the other nodes
3. Safety: guarantee that the above two never reach a contradictory state under any combination of failures

9.1 Server State Transitions

A Raft node is always in one of the following three states.

stateDiagram-v2
  [*] --> Follower
  Follower --> Candidate: election timeout
  Candidate --> Candidate: election timeout (re-election)
  Candidate --> Leader: wins a majority of votes
  Candidate --> Follower: another node turns out to be the new Leader / sees a higher term
  Leader --> Follower: sees a term higher than its own

• Follower: the normal state. A passive role that merely responds to RPCs from the leader or candidates
• Candidate: the state of standing for election after detecting the absence of a leader
• Leader: the role of accepting writes from clients and replicating the log to the other nodes

Right after startup all nodes begin as followers, and if no signal (heartbeat) arrives from a leader for a certain time (the election timeout), they transition to candidate.

9.2 Terms

Raft uses a monotonically increasing integer called a term as a logical clock. Each term has at most one leader (there can be terms with none). On every RPC a node compares the other side’s term with its own, and the moment it finds a term higher than its own, it immediately demotes itself to follower and updates its term. This single simple rule prevents a state where “two leaders both keep accepting writes at the same time.”

9.3 Leader Election (RequestVote RPC)

A follower whose election timeout fires increments its term by one, becomes a candidate, and sends RequestVote RPCs in parallel to all other nodes.

sequenceDiagram
  participant C as Candidate (term=5)
  participant F1 as Follower1
  participant F2 as Follower2
  C->>F1: RequestVote(term=5, lastLogIndex, lastLogTerm)
  C->>F2: RequestVote(term=5, lastLogIndex, lastLogTerm)
  F1-->>C: VoteGranted=true
  F2-->>C: VoteGranted=true
  Note over C: wins a majority (2 of 3) -> promoted to Leader
  C->>F1: AppendEntries(term=5, heartbeat)
  C->>F2: AppendEntries(term=5, heartbeat)

Written as pseudocode, the decision logic on the voting side is roughly as follows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

on receive RequestVote(term, candidateId, lastLogIndex, lastLogTerm):
  if term < currentTerm:
    return VoteGranted=false

  if term > currentTerm:
    currentTerm = term
    become Follower
    votedFor = null

  # vote only if "haven't voted yet in this term" and "the other's log is as new as mine or newer"
  if (votedFor is null or votedFor == candidateId) and
     candidateLogIsAtLeastUpToDate(lastLogIndex, lastLogTerm):
    votedFor = candidateId
    reset election timer
    return VoteGranted=true

  return VoteGranted=false

There are two key points.

• Per term, a node casts at most one vote (guaranteed by votedFor). This limits to at most one the number of candidates that can win a majority in the same term
• The voting side votes only if the candidate’s log is “about as new as its own, or newer.” This becomes the crux of the safety explained later

If a majority of votes doesn’t gather within a certain time (split votes, network delay, etc.), the election timeout fires again, the term is incremented further, and there is a re-election. By randomizing the timing of this re-election per node, Raft keeps the probability of consecutive split votes low enough for practical purposes.

9.4 Log Replication (AppendEntries RPC)

A node promoted to leader appends commands received from clients to its own log and replicates them to the other nodes with AppendEntries RPCs. AppendEntries is sent periodically even when empty, and that functions directly as the heartbeat (heartbeat and log replication are unified into the same RPC).

sequenceDiagram
  participant Client
  participant L as Leader
  participant F1 as Follower1
  participant F2 as Follower2
  Client->>L: Command "SET x=1"
  L->>L: append entry to log (uncommitted)
  L->>F1: AppendEntries(entries=[SET x=1], prevLogIndex, prevLogTerm)
  L->>F2: AppendEntries(entries=[SET x=1], prevLogIndex, prevLogTerm)
  F1-->>L: Success=true
  F2-->>L: Success=true
  Note over L: replicated to a majority, so advance commitIndex
  L->>Client: response (commit complete)
  L->>F1: AppendEntries(leaderCommit updated)
  L->>F2: AppendEntries(leaderCommit updated)
  Note over F1,F2: see leaderCommit and apply to their own logs too

The follower’s consistency check always confirms “whether the previous entry matches,” as in the pseudocode below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

on receive AppendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries, leaderCommit):
  if term < currentTerm:
    return Success=false

  if log[prevLogIndex].term != prevLogTerm:
    # the immediately preceding entry disagrees -> reject this AppendEntries
    return Success=false

  # if there are conflicting entries, delete them and overwrite
  for entry in entries:
    if log has conflicting entry at same index:
      truncate log from that index
    append entry to log

  if leaderCommit > commitIndex:
    commitIndex = min(leaderCommit, index of last new entry)

  return Success=true

Thanks to the consistency check via prevLogIndex/prevLogTerm, if a follower’s log is missing even one entry or disagrees, replication to that follower keeps failing. On detecting failure, the leader retransmits while walking that follower’s nextIndex back one at a time, ultimately rewinding to the point where they match and then overwriting with the correct content.

9.5 Safety

What the Raft paper puts particular effort into is this discussion of safety. Here are three representative properties.

Intuitively, Leader Completeness holds for the following reason. That an entry was committed means a majority of nodes hold it. To become the next leader you need a majority of votes, and by the Election Restriction a “node whose log is old” cannot obtain votes. Therefore a new candidate that obtains a majority of votes necessarily overlaps in at least one node with the group holding the committed entry. Consequently the new leader’s log necessarily contains the existing committed entries.

9.6 The Pitfall in the Commit Rule

Raft’s simple rule of “commit as soon as it’s replicated to a majority” has exactly one exception. A leader must not commit, on the basis of replication count alone, any entry other than one created in its own current term. When committing an entry from a past term indirectly, the condition is that a later entry from its own term be committed first.

Without this constraint, there’s a counterexample — illustrated in the Raft paper itself — where an entry replicated to a majority is later overwritten. This is one of the more counterintuitive parts of Raft’s correctness, and a breeding ground for common implementation bugs.

9.7 Membership Changes

Changing the cluster’s node configuration (adding or removing nodes) must itself be done without breaking consensus. Simply switching the configuration all at once can produce a “dual leader,” where separate majorities in the old and new configurations elect leaders simultaneously.

• Joint consensus (the original paper’s scheme): pass through an intermediate state $C_{old,new}$ requiring majority agreement in both the old configuration $C_{old}$ and the new configuration $C_{new}$, then finally switch to $C_{new}$ alone. Safe, but somewhat complex to implement
• Single-server change scheme: by imposing the constraint that nodes are added or removed only one at a time, it guarantees that the majority sets of $C_{old}$ and $C_{new}$ necessarily overlap, omitting the intermediate state. Many implementations, such as etcd, adopt this

In either scheme, the safety hinge is that “the majority sets of the old and new configurations necessarily overlap in at least one node.”

9.8 Log Compaction and Snapshots

Since the log grows without bound, production systems periodically take snapshots and discard log entries preceding them. A snapshot holds “the state machine’s state up to that point” and “the index and term of the last included log entry,” and lagging followers are sent the snapshot itself via an InstallSnapshot RPC instead of the log.

After introducing snapshots, implementation branches increase — how to handle a prevLogIndex older than the snapshot boundary, for example. This boundary handling is known as a spot where many Raft implementations tend to have bugs.

9.9 Client Interaction and Linearizable Reads

Raft maintains consistency by “committing writes to the log through the leader,” but returning reads directly from the leader’s local state can in fact cause problems. That’s because an old leader that still believes it is the leader (a node isolated by a network partition) may return a stale value even though a new leader has already been elected.

Here are two representative techniques for avoiding this.

• Read index scheme: on receiving a read request, the leader records its commitIndex at that moment, then does one heartbeat round trip to a majority confirming that it is still the leader before responding
• Lease scheme: the leader assumes no other leader exists within a certain time (a lease period accounting for clock skew) and responds to local reads without a heartbeat. Lighter to implement, but safety depends on clock accuracy

Both are devices for achieving “linearizable reads,” and the point that naively reading the leader’s memory is not enough is often overlooked in operating Raft.

9.10 Multi-Raft

In a single Raft group, the leader processes all commands in order, so write throughput is capped by the processing capacity of one leader machine. Multi-Raft is the configuration that resolves this by splitting data by key range or the like and running many independent Raft groups (often called ranges or regions) in parallel, one per range.

• Since each Raft group performs leader election and log replication independently, increasing the number of groups scales write throughput horizontally
• Because one node concurrently serves as leader and follower for multiple Raft groups, optimizations are needed to bundle heartbeats and snapshot transfers and hold down communication overhead (CockroachDB’s coalesced heartbeats, for example)
• Transactions spanning groups (writes across multiple ranges) aren’t completed by Raft consensus alone and must be combined with the distributed transactions covered in the next chapter

CockroachDB and TiKV use this Multi-Raft configuration to reconcile scalability and consistency as distributed SQL databases. If EPaxos (the leaderless scheme) listed in the comparison table in chapter 8 is the solution in the direction of eliminating the single-leader bottleneck itself, Multi-Raft can be positioned as the solution in the direction of “increasing single-leader consensus groups horizontally.”

9.11 Representative Implementations

The basic algorithm in all of these is faithful to the Raft paper, but it’s worth keeping in mind that for performance they pile on pipelining, batching, and their own optimizations such as Multi-Raft.

10. Distributed Transactions

A family of techniques used when you want to perform writes spanning multiple partitions or services atomically (either all succeed or all fail).

• Two-phase commit (2PC): a coordinator proceeds in two stages, Prepare (confirm readiness) → Commit (instruct finalization). The mechanism is simple, but there’s a “blocking” problem where, if the coordinator dies after Prepare, participants keep waiting while holding locks
• Three-phase commit (3PC): a scheme that adds one stage to mitigate 2PC’s blocking problem, but it can’t fully solve it on an asynchronous network and adoption in production is limited
• Sagas: a scheme where each step is executed as a local transaction and, on failure, rolled back with compensating transactions (undo operations). It doesn’t strictly guarantee atomicity, but is often used for long-running transactions across microservices

Google’s Spanner is known as an example that combines TrueTime (a time API with error bounds) with Paxos-based replication to achieve distributed transactions with external consistency even in a geo-distributed environment.

11. Failure Detection and Membership Management

The mechanism for grasping “which nodes are alive” within a cluster is also an important element of distributed systems.

• Heartbeat scheme: send liveness checks to each other at fixed intervals. Simple, but traffic grows at least linearly as the number of nodes increases
• Gossip protocol: each node exchanges state only with a small number of randomly chosen nodes, and information spreads across the whole cluster by propagation. Easy to scale while keeping traffic down
• SWIM: a protocol that adds indirect liveness checks (pings via other nodes) to gossip, reducing false positives while keeping detection time down
• Phi accrual failure detector: a scheme that expresses suspicion as a continuous value (the phi value) rather than a binary “alive/dead,” letting the application tune the threshold. Adopted in Cassandra and others

Consensus algorithms, Raft included, specialize in “deciding who the leader is,” and loose membership management (liveness monitoring) across a cluster of hundreds to thousands of nodes usually uses gossip-family protocols. It’s common to use them together as technologies with different roles.

12. Combinations Seen in Real Systems

Finally, let’s organize how the elemental technologies so far are actually combined in real systems.

Even under the same words “consensus” and “replication,” the assumed consistency and failure models differ by system. When selecting middleware, it’s better to check not just the algorithm name but “which consistency model it guarantees, under which failure model.”

How to Look at This When Bringing It to Practice

• If you’re stuck on “why is this operation slow,” suspect the consistency model first. Linearizable reads require a round trip to the leader or a majority confirmation, and this is often the main cause of latency
• “Why does only this node return stale data” is, in many cases, best suspected as a node isolated by a network partition responding to local reads
• If writes stall in Raft-based middleware, first check whether the leader is being elected stably (whether frequent re-elections are occurring). It’s worth revisiting the relationship between the election timeout setting and network delay
• Even when distributed transactions seem necessary, it’s worth first considering whether the design can be revised so everything completes within a single partition

Caveats

• Many consensus algorithms, Raft included, assume crash-stop/crash-recovery and don’t handle Byzantine failures (nodes that lie)
• Raft’s safety depends on the overlap of “majorities.” When a network partition splits the cluster, the side that can’t secure a majority stops accepting writes (a design prioritizing consistency over availability)
• FLP impossibility is a theoretical limit and doesn’t mean an implementation “absolutely never stalls.” In production, understanding it as “held down to a sufficiently low probability” is closer to reality
• Around snapshots and membership changes there are many boundary conditions that textbook pseudocode alone can’t cover. If you’re implementing it, it’s safer to consult the original paper’s appendix (the formal specification in TLA+) and the test cases of existing OSS implementations

References

Books

• Kleppmann, M. Designing Data-Intensive Applications. O’Reilly, 2017
• van Steen, M. and Tanenbaum, A. S. Distributed Systems, 3rd edition (freely available on the authors’ site)
• Vitillo, R. Understanding Distributed Systems, 2nd edition, 2023

Papers

• Ongaro, D. and Ousterhout, J. “In Search of an Understandable Consensus Algorithm (Raft)”. USENIX ATC, 2014
• Lamport, L. “Paxos Made Simple”. ACM SIGACT News, 2001
• Lamport, L. “Time, Clocks, and the Ordering of Events in a Distributed System”. Communications of the ACM, 1978
• Fischer, M. J., Lynch, N. A., and Paterson, M. S. “Impossibility of Distributed Consensus with One Faulty Process”. Journal of the ACM, 1985
• Oki, B. M. and Liskov, B. “Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems”. PODC, 1988
• Brewer, E. “CAP Twelve Years Later: How the ‘Rules’ Have Changed”. IEEE Computer, 2012
• Junqueira, F. P., Reed, B. C., and Serafini, M. “Zab: High-performance broadcast for primary-backup systems”. DSN, 2011
• Moraru, I., Andersen, D. G., and Kaminsky, M. “There Is More Consensus in Egalitarian Parliaments”. SOSP, 2013
• Das, A., Gupta, I., and Motivala, A. “SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol”. DSN, 2002
• Corbett, J. C. et al. “Spanner: Google’s Globally-Distributed Database”. OSDI, 2012
• DeCandia, G. et al. “Dynamo: Amazon’s Highly Available Key-value Store”. SOSP, 2007

Primary Sources

• Raft Consensus Algorithm official site
• The Raft Paper (PDF)
• etcd Documentation

Related Articles

• Ensuring high availability of systems, and etcd and Raft — an article (in Japanese) explaining the CAP theorem and Raft based on a concrete web system example