Fischer Lynch Paterson

Fischer Lynch Paterson
Name	Fischer Lynch Paterson
Fields	Computer science, Distributed computing
Known for	FLP impossibility result
Notable works	FLP paper (1985)
Institutions	Cornell University, MIT

Fischer Lynch Paterson was a trio of researchers—Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson—whose collaborative work produced a landmark 1985 result in distributed computing and theoretical computer science. Their joint paper established an impossibility theorem about reaching consensus in asynchronous systems with even a single faulty process, reshaping research at institutions such as MIT, Cornell University, and influencing projects at organizations including Bell Labs and IBM Research. The result, commonly abbreviated as FLP, has become central to studies involving protocols like Paxos and Raft, and to analysis undertaken in conferences such as PODC and STOC.

History

The collaboration among Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson occurred in the context of 1970s–1980s advances in algorithms and concurrency theory emerging from groups at MIT, Harvard University, and Cornell University. Prior work on consensus by researchers such as Leslie Lamport and Rachid Guerraoui addressed synchronous or partially synchronous models; Fischer, Lynch, and Paterson formalized an asynchronous model inspired by earlier studies like Dijkstra’s work on self-stabilization and results from Edsger W. Dijkstra. The FLP paper was presented to communities frequenting venues like ACM conferences and was rapidly cited alongside foundational results such as the Cook–Levin theorem and Gödel-related undecidability discussions.

Formal Definition

Fischer, Lynch, and Paterson defined an asynchronous distributed system as a collection of deterministic processes connected by reliable but unordered channels, modeled similarly to process calculi used in analyses at Carnegie Mellon University and Bell Labs. Their model specifies processes executing steps determined by local states and incoming messages, with failure characterized as a crash-stop fault, comparable to fault models studied at SRI International and Bell Labs research groups. Consensus is defined with three properties: termination, agreement, and validity—terms paralleling requirements in protocols like Paxos by Leslie Lamport and consensus terms used in Byzantine fault tolerance literature initiated by researchers such as Leslie Lamport, Marshall Pease, and Ronald Rivest.

Impossibility Result (FLP)

The FLP theorem shows that in an asynchronous system with even one potential crash failure, no deterministic algorithm can guarantee consensus with both safety and liveness under all admissible schedules. This impossibility stands alongside seminal negative results like Rice's theorem and the Halting problem, and it has a role analogous to impossibility statements in distributed settings such as the Fischer–Lynch–Paterson result’s impact on later impossibility proofs in Byzantine generals problem contexts studied by Lamport, Shostak, and Pease. The FLP result clarified limits faced by designers of consensus protocols used in systems developed by Google, Amazon, and Microsoft.

Proof Outline

Their proof constructs an execution starting from a bivalent initial configuration—one in which the eventual decision could be either of two values—and shows that from any bivalent configuration there exists a step leading to another bivalent configuration unless a process crashes. The argument employs the adversarial scheduling of messages akin to adversary models discussed in works from Eugene W. Myers and uses indistinguishability arguments related to techniques used in communication complexity and automata theory from researchers at Princeton University and UC Berkeley. By repeatedly extending the execution while avoiding decisions, the authors demonstrate that an execution can be constructed in which no process ever decides, contradicting termination. This style of proof echoes combinatorial constructions in papers presented at FOCS and STOC.

Implications and Applications

The FLP impossibility led to two main responses: weakening the model or the guarantees. Practical systems adopt timing assumptions from the partially synchronous model by Dwork, Lynch, and Stockmeyer or rely on randomized algorithms such as Ben-Or’s randomized consensus and protocols like Paxos or Raft that assume eventual synchrony. The result influenced distributed databases at Google (Chubby) and Amazon (Dynamo), and cloud orchestration projects at Kubernetes and Apache ZooKeeper. It also motivated formal verification efforts using tools from model checking research at NASA and theorem provers developed at Cambridge and INRIA.

Subsequent Research and Extensions

Following FLP, work expanded into randomized consensus, partial synchrony, and alternative failure models including Byzantine fault tolerance and hybrid models studied by researchers at ETH Zurich and UC Berkeley. Extensions analyzed adversary power, resilience bounds, and time complexity, producing lower bounds analogous to FLP in broadcast and agreement settings considered by Dolev, Peleg, and Attiya. The FLP framework also inspired algorithmic designs combining synchrony assumptions with failure detectors introduced by Chandra and Toueg, and spurred ongoing research presented at venues such as DISC, PODC, and SOSP.

Category:Distributed computing Category:Theoretical computer science