Distributed computing - Algorithms Models and Complexity

Distributed and Parallel Computing: Theoretical Foundations and Algorithms Introduction Distributed algorithms solve problems where computation is spread across multiple independent processors that communicate by exchanging messages. This is fundamentally different from traditional sequential algorithms and even from parallel algorithms running on shared-memory systems. Understanding the models, key algorithms, and complexity measures for distributed systems is essential for analyzing how real-world systems coordinate and compute efficiently. Computing Models: From Shared Memory to Distributed Systems When designing algorithms, we need formal models that capture how processors interact. There are several key models that sit on a spectrum from centralized to fully distributed: The PRAM Model assumes a synchronous shared-memory architecture where multiple processors access a common memory. Think of this as having a pool of processors that can all read from and write to the same data, and all operations happen in lock-step synchrony. This is primarily theoretical—real hardware doesn't work this way—but it's useful for understanding parallel algorithm design. Asynchronous Shared Memory Models are closer to reality. In these models, processors still share memory, but they don't operate in lockstep. Instead, they execute real-world machine instructions like compare-and-swap, which atomically read a memory location, compare it to an expected value, and conditionally write a new value. This is the basis for designing efficient concurrent data structures in practice. Graph-Based Distributed Models represent the most distributed scenario. Each node in a network is a finite-state machine that can only communicate with its immediate neighbors. A node knows its own unique identifier and the identifiers of its neighbors, but it has no global view of the network. The key insight here is that algorithms must be local: they compute results using only information from nearby nodes, with global coordination emerging through message passing. The image above illustrates these architectures. Diagram (a) shows a distributed graph model where each node communicates only with neighbors. Diagram (b) shows distributed shared memory where processors can access a common memory. Diagram (c) shows a classical shared-memory parallel system where all processors access a single memory. Interaction Between Parallel and Distributed Algorithms An important observation is that some algorithms can work in both parallel and distributed settings. A classic example is the Cole–Vishkin graph-coloring algorithm, which colors the vertices of a graph using far fewer colors than might initially seem necessary. In a parallel setting, multiple processors work on this problem with shared memory. The same algorithm can be adapted for a distributed setting where each node only knows its neighbors' colors and must exchange messages to eventually compute its own color. This flexibility shows that the distinction between "parallel" and "distributed" is sometimes blurry—it's more about the communication model than the fundamental algorithm structure. Key Distributed Algorithms Minimum-Weight Spanning Tree One fundamental distributed problem is constructing a minimum-weight spanning tree (MST) of a network. In a distributed setting, no single processor knows the entire network structure. The Gallager–Humblet–Spira algorithm solves this by having each node communicate only with its immediate neighbors. Nodes cooperatively build fragments of the MST and gradually merge them into a single tree. The beauty of this approach is that it requires only local information—each node doesn't need to know the global structure to participate correctly. Leader Election Another critical problem is leader election (also called coordinator election). A distributed system often needs to designate a single processor as the coordinator for some task, whether that's initiating a protocol, breaking a deadlock, or managing distributed resources. The challenge is that all nodes start in identical states and must deterministically elect a single leader without a central authority. Leader Election: The Core Problem Problem Definition and Symmetry Breaking The problem is simple to state but subtle to solve: all nodes must agree on exactly one leader. In a network where every node is initially identical, how can they ever distinguish one? The answer is symmetry breaking: nodes are assigned unique identifiers (like unique integers or MAC addresses), and the election algorithm ensures that the node with the highest identifier becomes the leader. The process works as follows: nodes communicate information about their identifiers through the network. A node announces itself as a candidate and sends a message around the network. When this message reaches another node with a higher identifier, that node suppresses the first node's candidacy. Eventually, only the node with the globally highest identifier remains a candidate—this node becomes the leader. Design Goals When designing leader election algorithms, we optimize for two main metrics: Message Complexity: The total number of messages exchanged, or equivalently, the total bytes transmitted. This is critical because communication is often the bottleneck in distributed systems. Time Complexity: How many communication rounds are needed until a leader is elected. A communication round is one step where each node can send one message to its neighbors and receive messages from all neighbors. Different topologies benefit from different algorithms, so solutions are tailored to the network structure: rings (circular arrangements of processors), complete graphs (where every node connects to every other), grids (rectangular arrangements), and directed Euler graphs (specialized graphs with particular properties). Linearizability: Correctness for Concurrent Systems As we move toward understanding distributed systems, we need a way to verify that concurrent operations behave correctly. Linearizability is a key correctness condition. The idea is simple: even though operations in a distributed or concurrent system may overlap in real time, we want to ensure they behave as though they occurred sequentially in some order. More precisely, an execution is linearizable if we can assign each operation a single point in time between its invocation (when a process calls the operation) and its response (when the operation completes), such that operations appear to execute in the order of these time points and each operation sees the effects of all operations that happened before it. Think of it this way: from a client's perspective, even if multiple requests are processed concurrently, the system behaves as though they were processed one at a time. This is a strong guarantee that makes reasoning about concurrent systems much easier. Complexity Measures in Distributed Algorithms Understanding how to measure the efficiency of distributed algorithms is crucial. Unlike sequential algorithms where we simply count operations, distributed algorithms have multiple dimensions of complexity. Time Complexity and Parallel Speedup In parallel algorithms, one fundamental question is: what speedup do we get from additional processors? If a sequential algorithm takes $T$ time and we have $P$ processors, we might hope to reduce time to roughly $T/P$. However, due to synchronization overhead and dependencies between tasks, linear speedup is often unachievable. This motivates the definition of the complexity class NC (Nick's Class): problems solvable in polylogarithmic time—roughly $O(\log^k n)$ for some constant $k$—using a polynomial number of processors. Problems in NC are considered "highly parallelizable" because they can achieve good speedup even with many processors. The LOCAL Model: Measuring Rounds of Communication In distributed computing, the most natural measure is the number of communication rounds. In the LOCAL model, we count synchronous rounds where: In each round, every node can send one message to each neighbor Every node simultaneously receives all messages sent to it The algorithm terminates once all nodes have computed their local answer Why this model? Because latency (time between rounds) is often more important than bandwidth in geographically distributed systems. A fundamental insight is the relationship between rounds and network diameter. The diameter $D$ of a network is the longest shortest path between any two nodes. Any problem can be solved in roughly $2D$ rounds: gather all network information to one node (costs $\leq D$ rounds), compute a solution, and broadcast the answer (costs $\leq D$ more rounds). This is rarely optimal, but it provides an upper bound. The CONGEST Model: Measuring Total Bits In the LOCAL model, we assumed each message can contain any amount of information. In reality, network links have bandwidth limits. The CONGEST model is more realistic: each message is limited to $B$ bits (typically $B = O(\log n)$ where $n$ is the number of nodes). This model measures the total number of bits transmitted across all edges in the network. This distinction matters significantly. In the LOCAL model, a node can describe its entire neighborhood in one message. In the CONGEST model, with limited bandwidth, describing a large neighborhood requires multiple rounds. As a result, algorithms optimized for the CONGEST model often look quite different from those optimized for LOCAL. Summary: Distributed algorithms operate in fundamentally different settings than sequential or even parallel algorithms. The key challenges are handling asynchrony, managing limited local knowledge, and coordinating through message passing. By understanding different computational models (shared memory vs. distributed graphs), key problems (leader election and MST construction), correctness conditions (linearizability), and complexity measures (rounds in LOCAL model, bits in CONGEST model), you now have the foundation for analyzing and designing distributed systems.