benaloh@theory.toronto.edu (Josh Benaloh) (07/14/89)
Department of Computer Science, University of Toronto
(GB = Gailbraith Building, 35 St. George Street)
-------------------------------------------------------------
THEORY SEMINAR
GB305, at 2:00 p.m., Friday 14 July 1989
Benny Chor
Technion
Solvability in Asynchronous Environments
Distributed decision tasks, where each of $n$ processors starts with a
local input and terminates after deciding on a local output, are the basis
for distributed algorithms. We investigate the solvability of distributed
decision tasks in asynchronous environments where processors may fail-stop.
We focus on two models of interprocess communication -- "shared memory",
and "message passing".
Denote by $SM_t$ (resp. $MP_t$) the class of distributed decision tasks
that are solvable in the shared memory (resp. message passing) model by a
$t$-resilient "randomized" protocol. We give combinatorial characterizions
of the classes $SM_t(0 <= t < n)$ and $MP_t(0 <= t <= floor{(n-1)/2})$.
Structural results on the nature of the $SM$ and $MP$ hierarchies, and on
the relations between them, are derived. In particular, we show that
wait-free consensus is a complete problem in $SM_t$, while $t$-resilient
consensus is complete in $MP_t$.
This is joint work with Lior Moscovici.