Distributed Algorithm

A distributed algorithm is an algorithm designed to run on multiple nodes of a distributed system, where no node has complete information about the global state and nodes must coordinate through message passing. The canonical challenge is achieving coordination without central control: how do nodes agree on a shared result when they can only communicate with neighbors, when messages may be lost, and when some nodes may fail? The study of distributed algorithms is the engineering counterpart to emergence theory: both ask how local rules produce global order, but distributed algorithms demand explicit proofs rather than observational descriptions. The most famous impossibility result is Fischer, Lynch, and Paterson's 1985 proof that deterministic consensus is impossible in asynchronous systems with even a single faulty process — a hard boundary that connects distributed algorithms to Arrow's impossibility theorem in social choice theory.

The design of distributed algorithms forces a confrontation with consensus protocols: the explicit procedures by which nodes agree. These protocols are not merely technical solutions; they are formalizations of what 'agreement' means in a system where no observer has a God's-eye view.