🚀 go-pugleaf

DATE Tuesday December 1, 1992
TIME 4:30-6:00 P.M.
PLACE 3400 Boelter Hall
Cookies & Coffee Will Be Served
Starting at 4:00 PM

GENERALIZED FLP IMPOSSIBILITY RESULT FOR 
t-RESILIENT ASYNCHRONOUS COMPUTATIONS.
Eli Gafni
Computer Science Department
UCLA

ABSTRACT 
Demarcation of the border between solvable and unsolvable distributed
tasks under various models is the holy grail of the theory of 
distributed computing. One of the most celebrated of these results 
is (FLP) which established the impossibility of asynchronous 
consensus that can tolerate a single undetected fail-stop processor. 
Indeed, it has led to  the precise characterization of tasks solvable 
and unsolvable under single fault. In this talk we show how to
generalize FLP to multiple faults, and in the process resolves a 
number of open problems.

We diverge from the classic FLP in studying the ``leader election''
problem, and arguing impossibility within the wait-free context only.
Then we show that the wait-free version t-equivalent to the 
non-wait-free one.  Concentrating on the wait-free version for 
impossibility allows us to deal with bounded executions and views 
of processors there in.  We prove the impossibility using a variant 
of the k-dimensional Sperner Lemma.  When k=1 we obtain a completely 
different simple proof of the FLP result.

We show that ``multiple leader election'' is fundamental by reducing
to it the previously suggested problems of k-set consensus, 
k-set test-and- set, and renaming, thus resolving when these problems
are solvable and when  they are not.  A by-product of our proof 
technique is a wait-free read/write simulation of t-resilient
computation by t+1-processors, which shows that resilient computations 
can be investigated by concentrating on the corresponding waitfree
computation.

(Joint work with Elizabeth Borowsky)