Distributed Systems
Algorithms for consensus, logical and physical clocks, leader election, replication, and cluster partitioning.
Distributed systems algorithms coordinate state across networked nodes without shared memory, providing quorum consensus, causal and physical clock synchronization, leader election, conflict-free replication (CRDTs), and minimal-disruption key routing.
Consistent Hashing Load Balancing
Distributed hash ring partitioning scheme with virtual nodes that maps both cache servers and keys onto a 32-bit/64-bit circle so node joins or failures remap only O(K/N) keys.
Raft Distributed Consensus
Maintains a replicated state-machine log across a cluster via leader election (randomized 150–300ms timeouts, §5.4.1 up-to-date log check) and majority-quorum AppendEntries replication.
Paxos Consensus
Reaches fault-tolerant distributed consensus across asynchronous replicated servers using two-phase Prepare/Promise and Accept/Accepted quorum rounds.
Lamport Logical Clocks
Orders events across distributed processes without synchronized physical clocks using a monotonically increasing scalar logical counter.
Vector Clocks
Tracks exact causal history across N distributed nodes using an N-element counter vector to detect both causal ordering and concurrent conflicts.
Cristian's Algorithm
Synchronizes a client's physical wall clock with a reference time server by measuring round-trip network delay and setting time to T_server + RTT / 2.
Berkeley Algorithm
Synchronizes physical clocks across a cluster without an external UTC time source by polling all nodes, discarding outlier skews, and adjusting each node to the fault-tolerant average time.
Marzullo's Algorithm (NTP Clock Selection)
Finds the smallest confidence interval intersecting the maximum number of noisy time-server intervals in O(M log M) time, forming the core of NTP clock selection.
Bully Algorithm
Elects a coordinator in a distributed system by having any node that detects leader failure challenge all higher-ID nodes, so the live process with the highest numeric ID wins.
Ring Leader Election (Chang-Roberts)
Elects the highest-ID leader among processes arranged in a unidirectional logical ring by forwarding only the maximum candidate ID around the ring.
CRDT G-Counter & PN-Counter
Conflict-free replicated counter that allows offline or partitioned replicas to increment (G-Counter) and decrement (PN-Counter) concurrently and merge without a central server via element-wise maximum.
CRDT OR-Set (Observed-Remove Set)
Conflict-free replicated set that resolves concurrent offline add and remove operations deterministically (add-wins) by tagging each added element with a unique token.
Rendezvous Hashing (Highest Random Weight / HRW)
Assigns each key to the server node s that maximizes hash(key, s), achieving uniform load and minimal O(K/N) key remapping when servers join or leave without maintaining a virtual-node ring.