distributed-systems-guide

name	distributed-systems-guide
description	Distributed systems design patterns and analysis for CS research
metadata	{"openclaw":{"emoji":"🌐","category":"domains","subcategory":"cs","keywords":["distributed-systems","consensus","replication","fault-tolerance","scalability","cap-theorem"],"source":"wentor"}}

Distributed Systems Guide

A skill for researching and designing distributed systems, covering consensus algorithms, replication strategies, consistency models, fault tolerance, and performance analysis. Provides theoretical foundations and practical implementations relevant to systems research.

Consistency Models

Consistency Hierarchy

Strongest
  |  Linearizability (atomic, real-time ordering)
  |  Sequential consistency (program order respected)
  |  Causal consistency (causally related ops ordered)
  |  PRAM / FIFO consistency (per-process order)
  |  Eventual consistency (converges if updates stop)
Weakest

CAP Theorem and PACELC

The CAP theorem states that during a network partition, a distributed system must choose between consistency and availability:

System	Partition Behavior	Normal Behavior	Classification
ZooKeeper	Consistent (sacrifice A)	Low latency, consistent	CP / PC/EC
Cassandra	Available (sacrifice C)	Low latency, eventual	AP / PA/EL
Spanner	Consistent (sacrifice A)	Higher latency, consistent	CP / PC/EC
DynamoDB	Configurable per-read	Tunable consistency	AP or CP
CockroachDB	Consistent (sacrifice A)	Serializable	CP / PC/EC

Consensus Algorithms

Raft Implementation Sketch

from enum import Enum
from dataclasses import dataclass, field
import random

class NodeState(Enum):
    FOLLOWER = "follower"
    CANDIDATE = "candidate"
    LEADER = "leader"

@dataclass
class LogEntry:
    term: int
    index: int
    command: str

@dataclass
class RaftNode:
    """
    Simplified Raft consensus node for educational purposes.
    Implements leader election and log replication state machine.
    """
    node_id: str
    state: NodeState = NodeState.FOLLOWER
    current_term: int = 0
    voted_for: str = None
    log: list = field(default_factory=list)
    commit_index: int = 0
    last_applied: int = 0

    # Leader state
    next_index: dict = field(default_factory=dict)
    match_index: dict = field(default_factory=dict)

    def start_election(self, peers: list[str]) -> dict:
        """Transition to candidate and request votes."""
        self.state = NodeState.CANDIDATE
        self.current_term += 
        .voted_for = .node_id

        last_log_index = (.log) -   .log  -
        last_log_term = .log[-].term  .log  

         {
            : ,
            : .current_term,
            : .node_id,
            : last_log_index,
            : last_log_term,
        }

     () -> :
        
         term < .current_term:
             {: .current_term, : }

         term > .current_term:
            .current_term = term
            .state = NodeState.FOLLOWER
            .voted_for = 

        
        my_last_term = .log[-].term  .log  
        my_last_index = (.log) -   .log  -

        log_ok = (last_log_term > my_last_term 
                  (last_log_term == my_last_term 
                   last_log_index >= my_last_index))

        vote_granted = (
            (.voted_for    .voted_for == candidate_id)
             log_ok
        )

         vote_granted:
            .voted_for = candidate_id

         {: .current_term, : vote_granted}

     () -> LogEntry:
        
        entry = LogEntry(
            term=.current_term,
            index=(.log),
            command=command,
        )
        .log.append(entry)
         entry

Paxos vs Raft vs PBFT Comparison

Algorithm	Fault Model	Tolerance	Rounds	Complexity
Paxos	Crash faults	f < n/2	2 (normal)	Difficult to implement correctly
Raft	Crash faults	f < n/2	2 (normal)	Designed for understandability
PBFT	Byzantine faults	f < n/3	3	O(n^2) message complexity
HotStuff	Byzantine faults	f < n/3	3	O(n) with pipelining

Replication Strategies

State Machine Replication

class ReplicatedStateMachine:
    """
    State machine replication with configurable consistency.
    Demonstrates read/write quorum intersection for correctness.
    """

    def __init__(self, n_replicas: int, read_quorum: int = None,
                 write_quorum: int = None):
        self.n = n_replicas
        self.R = read_quorum or (n_replicas // 2 + 1)
        self.W = write_quorum or (n_replicas // 2 + 1)

        # Quorum intersection guarantees: R + W > N
        assert self.R + self.W > self.n, (
            f"Quorum intersection violated: R({self.R}) + W({self.W}) "
            f"must be > N({self.n})"
        )

        self.replicas = [{} for _ in range(n_replicas)]
        self.version_clock = 0

    def write(self, key: str, value: str) -> dict:
        """Write to W replicas."""
        self.version_clock += 1
        # Select W replicas (in practice, based on availability)
        targets = random.sample((.n), .W)
         i  targets:
            .replicas[i][key] = (value, .version_clock)

         {
            : key,
            : .version_clock,
            : (targets),
            : ,
        }

     () -> :
        
        targets = random.sample((.n), .R)
        responses = []
         i  targets:
             key  .replicas[i]:
                responses.append(.replicas[i][key])

          responses:
             {: key, : , : }

        
        latest = (responses, key= x: x[])
         {
            : key,
            : latest[],
            : latest[],
            : ,
        }

Clock Synchronization and Ordering

Vector Clocks

class VectorClock:
    """Vector clock for tracking causality in distributed systems."""

    def __init__(self, process_id: str, processes: list[str]):
        self.pid = process_id
        self.clock = {p: 0 for p in processes}

    def increment(self):
        """Local event: increment own counter."""
        self.clock[self.pid] += 1

    def send(self) -> dict:
        """Prepare clock for sending with a message."""
        self.increment()
        return dict(self.clock)

    def receive(self, other_clock: dict):
        """Merge received clock: element-wise max, then increment."""
        for p in self.clock:
            self.clock[p] = max(self.clock[p], other_clock.get(p, 0))
        self.increment()

    def happened_before(self, other: dict) -> :
        
         ((.clock[p] <= other.get(p, )  p  .clock) 
                (.clock[p] < other.get(p, )  p  .clock))

Performance Analysis

Latency and Throughput Modeling

Key metrics for evaluating distributed systems:

• Tail latency (p99, p999): Critical for real-world SLAs; often dominated by slow replicas
• Throughput under contention: How performance degrades with conflict rate
• Scalability: Linear vs sub-linear throughput increase with added nodes
• Recovery time: Time to restore consistency after node failure

Key Research Papers

• Lamport, L. (1998). The Part-Time Parliament (Paxos). ACM TOCS.
• Ongaro, D. and Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm (Raft). USENIX ATC.
• Corbett, J. et al. (2013). Spanner: Google's Globally-Distributed Database. ACM TOCS.
• DeCandia, G. et al. (2007). Dynamo: Amazon's Highly Available Key-value Store. SOSP.

Tools and Frameworks

• etcd / ZooKeeper: Production consensus stores for coordination
• Jepsen: Distributed systems correctness testing framework
• TLA+ / PlusCal: Formal specification and model checking
• ns-3 / OMNeT++: Network simulation for distributed protocols
• gRPC / Cap'n Proto: High-performance RPC frameworks
• FoundationDB: Multi-model distributed database with strong consistency