# Nancy Lynch

> 1948– · Computer Scientist
>
> **Recorded contribution:** Distributed algorithms; FLP impossibility result; Distributed Algorithms textbook

## How to use this dossier

Read for a causal chain, not a hero story: inherited problem → contribution → mechanism → downstream capability → limit. Then close the page and complete the reconstruction exercise from memory.

## 1. Historical orientation

Nancy Lynch (born 1948) developed foundational models, algorithms, and impossibility results for distributed computing. With Michael Fischer and Michael Paterson she proved the FLP theorem: in a fully asynchronous message-passing system, even one possible crash prevents any deterministic consensus protocol from guaranteeing termination in every admissible execution. The result does not say consensus is never achieved; it says safety plus guaranteed termination cannot be assured under that exact model. Lynch's I/O automata and textbook provided compositional ways to specify distributed components and proofs. Her work teaches engineers to identify which timing, failure, randomness, or detector assumption makes progress possible.

## 2. The problem inherited

Distributed processes needed to agree despite crashes and arbitrary message delay, but proposed protocols blurred what they assumed about time and failure detection.

## 3. The central contribution

Lynch and collaborators formalized distributed behavior and proved a sharp consensus impossibility that forces protocols to expose additional progress assumptions.

## 4. Reconstruct the mechanism

1. Model processes as deterministic state machines communicating through messages whose delivery can be delayed arbitrarily.
2. Define configurations as bivalent when future decisions can still be either value and univalent when only one remains possible.
3. Show some initial configuration is bivalent and that, from a bivalent state, an admissible next event can preserve bivalence.
4. Schedule such events indefinitely while respecting at most one crash, producing an execution that never decides.

## 5. What changed downstream

- FLP became a foundational boundary for databases, replicated services, and consensus protocols.
- I/O automata supported modular specifications and simulation proofs for distributed algorithms.
- Practical protocols became clearer about partial synchrony, timeouts, randomness, quorums, and failure detectors.

## 6. Attribution, limits, and uncertainty

- Fischer and Paterson are equal FLP coauthors; the proof builds on a broad distributed-computing lineage.
- FLP guarantees existence of a nonterminating schedule, not that normal deployments always stall.
- Real systems can weaken guarantees or add timing/randomness assumptions, which must be analyzed separately.

## 7. Reconstruction lab

Implement deterministic consensus for three processes, then write an adversarial scheduler that delays the pivotal message while one process may crash. Identify the extra timing or randomness assumption that restores termination.

## 8. Evidence trail

- [Impossibility of Distributed Consensus with One Faulty Process](https://doi.org/10.1145/3149.214121) — Journal of the ACM
- [Nancy Lynch](https://www.csail.mit.edu/person/nancy-lynch) — MIT CSAIL

---

*Research checked 2026-08-09. Dates, roles, and claims about living people are historical snapshots. Linked sources remain the authority; this dossier is original instructional synthesis.*