Better Late (40 years late!) Than Never: Monday Morning Quarterbacking the Coordinated- Attack Problem

The Coordinated-Attack problem was posed and proved impossible in 1975. It held the promise of creating a new kind of reasoning about computing: the field of distributed algorithms. It did not pan out that way. Only old-timers still remember this problem. There was not much to learn from it, since unlike the impossibility result of Fischer, Lynch and Patterson (FLP) for asynchronous agreement with a single fault that followed in 1983, straightforward variants of the underlying problem turned out to be trivial and uninteresting. In contrast, with FLP, the model of just a single fault still allowed for lesser coordination mechanisms than agreement that were still non-trivial. Indeed, the discovery a decade later of the connection between algebraic topology and distributed algorithms can be traced back to the FLP result. Thus FLP, rather than the Coordinated Attack, delivered on the original promise.

In this talk, I will show a simple tweak to the Coordinated-Attack problem that allows for some coordination. This possible coordination leads directly and simply to the FLP impossibility result, and the subsequent connection between distributed computing and algebraic topology.

The talk is aimed at a general audience and borrows from prior work with Yehuda Afek, and Elizabeth Borowsky, Nancy Lynch, and Sergio Rajsbaum.

This seminar is being jointly hosted by TOC and LIDS with LIDS