CS Colloquium - Eli Gafni, Computer Science Department, UCLA

Event time: 
Thursday, October 9, 2014 - 4:00pm
Location: 
AKW 200 See map
51 Prospect Street
New Haven, CT 06511
Event description: 

CS Colloquium
Eli Gafni, Computer Science Department, UCLA
Title: Better Late (40 years late!) Than Never: Monday Morning Quarterbacking the Coordinated-Attack Problem.

Refreshments will be available at 3:45 p.m.

Abstract: The Coordinated-Attack problem was posed and prove impossible in 1975. It held the promise that it is the beginning of a new kind of reasoning  - that 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) that followed in 1983, it was purely an impossibility result. A simple minded variation of it to do some coordination possible was trivial and thus uninteresting. In contrast, with FLP, one could see that although consensus was proved impossible, the model of just a single fault still allowed for lesser, yet non-trivial, coordination. 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 the promise.

In this talk I’ll show a simple hindsight-tweak in the Coordinated-Attack problem that allows for some coordination. This possible coordination leads directly and simply to the FLP impossibility, and the Algebraic-Topology connection.

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