Fundamentals of Distributed Systems: Models, Replication, Consistency, and Core Protocols

1 Concepts

A node in a distributed system is typically a process on an operating system; a node can be split into multiple logical nodes if a process consists of independent parts.

1.1 Model

Nodes are treated as indivisible units in the model, and replicas provide redundancy for data or services.

1.2 Replica

Replica (copy) refers to redundant data or service instances. Data replicas store the same data on multiple nodes to survive data loss, while service replicas provide the same service without relying on local storage.

Replica Consistency

Consistency levels include strong, monotonic, session, eventual, and weak consistency, each offering different guarantees for read/write operations.

1.3 Metrics for Distributed Systems

Key metrics are performance (throughput, latency, concurrency), availability, scalability, and consistency.

2 Distributed System Principles

2.1 Data Distribution Methods

Data can be distributed by hash, range, or size. Hash distribution suffers from poor scalability and data skew; range and size distribution use metadata servers to manage partitions. Consistent hashing improves scalability by using virtual nodes.

2.2 Basic Replica Protocols

Replica control protocols are either centralized (a single coordinator) or decentralized (peer‑to‑peer). Centralized protocols simplify concurrency control but create a single point of failure.

Primary‑Secondary Protocol

The primary node coordinates updates and reads; secondary nodes replicate updates. The protocol defines update flow, read strategies, primary election, and data reconciliation.

Decentralized Replica Protocol

All nodes are peers; consensus is reached through voting, which increases complexity and latency.

2.3 Lease Mechanism

Leases grant time‑bounded rights to cache data. The server issues a lease with an expiration time; clients may use cached data while the lease is valid, and the server delays writes until all leases expire, ensuring cache consistency.

2.4 Quorum Mechanism

Quorum requires writes to succeed on W out of N replicas and reads from R replicas, with W+R>N to guarantee that a read sees the latest committed write. Variants include write‑all‑read‑one (WARO) and general quorum configurations.

2.5 Log Techniques

Redo logs record the result of each update before applying it to memory, enabling crash recovery by replaying logs. Checkpointing periodically dumps the in‑memory state to reduce replay time. The 0/1 directory technique provides atomic batch updates by switching a master pointer between two directory versions.

2.6 Two‑Phase Commit (2PC)

2PC is a centralized strong‑consistency protocol with a coordinator and participants. It consists of a prepare phase where participants vote, followed by a commit/abort phase. 2PC suffers from poor fault tolerance and performance.

2.7 Multi‑Version Concurrency Control (MVCC)

MVCC creates a new version for each transaction, allowing concurrent reads of older versions while writes produce newer versions, similar to version control systems.

2.8 Paxos Protocol

Paxos achieves strong consistency in a decentralized manner using proposers, acceptors, and learners. It proceeds in numbered rounds with a prepare phase (promises) and an accept phase; a value once chosen cannot be changed.

2.9 CAP Theorem

CAP states that a distributed system cannot simultaneously provide strong consistency, high availability, and partition tolerance. Different protocols (Lease, Quorum, 2PC, Paxos) make different trade‑offs among these properties.