Key Concepts in Distributed Algorithms

Why This Matters

Distributed algorithms are the invisible backbone of every system where multiple machines need to work together—from cloud databases to blockchain networks to the apps on your phone syncing across devices. You're being tested on your understanding of how nodes coordinate without a single point of control, why failures don't crash entire systems, and what mechanisms ensure consistency when machines can't trust each other or even agree on what time it is. These concepts appear repeatedly in exam questions because they represent the fundamental challenges of building reliable systems at scale.

Don't just memorize algorithm names—know what problem each algorithm solves and why that problem is hard in a distributed context. When you see Paxos, think "agreement despite failures." When you see Chandy-Lamport, think "capturing global state without stopping the world." This conceptual mapping is what separates students who can handle FRQ scenarios from those who just recognize vocabulary.

---

Achieving Agreement: Consensus and Coordination

When distributed nodes must agree on a single value or decision, you need consensus algorithms. The core challenge is that nodes can fail, messages can be delayed or lost, and yet the system must still make progress and never contradict itself.

Consensus Algorithms (Paxos, Raft)

• Consensus ensures all non-faulty nodes agree on the same value—even when some nodes crash or network partitions occur
• Paxos provides the theoretical foundation with proposers, acceptors, and learners, but is notoriously difficult to implement correctly
• Raft was designed for understandability with explicit leader election, log replication, and safety guarantees—making it the go-to choice for practical systems like etcd and Consul

Leader Election Algorithms

• Leader election designates a single coordinator to make decisions, avoiding conflicts when multiple nodes might act simultaneously
• Bully algorithm selects the node with the highest ID through aggressive messaging, while Ring algorithm passes election messages in a logical ring structure
• Critical for reducing coordination overhead—once a leader exists, other nodes simply follow rather than negotiating every decision

Byzantine Fault Tolerance Algorithms

• BFT handles nodes that lie, cheat, or behave unpredictably—not just nodes that crash silently
• PBFT (Practical Byzantine Fault Tolerance) requires $3f + 1$ nodes to tolerate $f$ Byzantine failures, using a three-phase commit protocol
• Foundation of blockchain consensus—systems like Hyperledger use PBFT variants to ensure agreement even when some participants are malicious

---

Managing Shared Resources: Mutual Exclusion and Synchronization

When multiple processes need exclusive access to shared resources, you need mechanisms to prevent simultaneous access. The challenge is coordinating without a central lock server that could become a bottleneck or single point of failure.

Distributed Mutual Exclusion

• Prevents race conditions by ensuring only one process enters a critical section at any time
• Ricart-Agrawala algorithm uses timestamped requests and deferred replies—a process waits until it receives permission from all other processes
• Token Ring approach circulates a single token; only the token holder can access the resource—simple but vulnerable to token loss

Clock Synchronization Algorithms

• Synchronized clocks enable event ordering and timeout-based coordination across nodes that have no shared memory
• NTP (Network Time Protocol) synchronizes to external time sources with millisecond accuracy, while Berkeley Algorithm averages clock values among participating nodes
• Logical clocks (Lamport timestamps) provide ordering without physical synchronization—if event A happened before B, then $timestamp(A) < timestamp(B)$

---

Capturing and Sharing State: Snapshots and Dissemination

Distributed systems need ways to understand global state and spread information efficiently. The challenge is that there's no global clock or instantaneous communication—you can't just "pause" everything to take a picture.

Distributed Snapshot Algorithms

• Chandy-Lamport captures consistent global state without halting system execution—processes continue operating during snapshot collection
• Uses marker messages to delineate pre-snapshot and post-snapshot events, recording both process states and channel states
• Essential for checkpointing, debugging, and detecting stable properties like deadlock or termination

Gossip Protocols

• Epidemic-style information spreading where each node periodically shares state with randomly selected peers
• Achieves eventual consistency with $O(\log n)$ rounds to reach all nodes—highly scalable because no central coordinator exists
• Tolerates node failures gracefully—if one node dies, information still spreads through other paths; used in systems like Cassandra and DynamoDB

---

Organizing Data and Networks: Distributed Structures

Large-scale distributed systems need efficient ways to store data and route messages without centralized indexes. The challenge is maintaining structure and enabling fast lookups when nodes join, leave, and fail constantly.

Distributed Hash Tables (DHTs)

• Decentralized key-value storage where each node is responsible for a portion of the keyspace, determined by hashing
• Chord organizes nodes in a logical ring with $O(\log n)$ lookup time using finger tables; Kademlia uses XOR distance metrics for routing
• Foundation of peer-to-peer systems like BitTorrent and IPFS—enables scalable storage without central servers

Distributed Spanning Tree Algorithms

• Creates loop-free topology for efficient broadcast and routing across network nodes
• Spanning Tree Protocol (STP) elects a root bridge and prunes redundant links to prevent broadcast storms
• Enables optimal resource allocation—messages follow tree edges rather than flooding the entire network

Distributed Graph Algorithms

• Processes graph structures partitioned across multiple nodes—no single machine holds the entire graph
• PageRank iteratively computes node importance through message passing; distributed MST algorithms like GHS build minimum spanning trees in $O(n \log n)$ messages
• Critical for social network analysis, web search ranking, and network optimization at scales where centralized processing is impossible

---

Quick Reference Table

---

Self-Check Questions

1. Both Raft and PBFT achieve consensus—what fundamental assumption about node failures distinguishes when you'd use each one?

2. If a system needs to detect whether a distributed computation has terminated, which algorithm family would you use to capture the necessary global state, and why can't you simply query each node individually?

3. Compare Ricart-Agrawala and Token Ring for distributed mutual exclusion: which has better message complexity, and which is more vulnerable to single points of failure?

4. A peer-to-peer file sharing system needs to locate files across millions of nodes without any central server. Which distributed structure enables $O(\log n)$ lookups, and what mechanism determines which node stores which keys?

5. An FRQ describes a large-scale database where nodes need to share membership information and detect failures, but centralized coordination would create a bottleneck. Which protocol family achieves eventual consistency through randomized peer-to-peer communication, and what is its typical convergence time in terms of network size?