benaloh@theory.toronto.edu (Josh Benaloh) (07/13/89)
Benny Chor will be visiting the department from July 10 until August 4
under I.T.R.C. sponsorship. He will be sitting in Al's office (2303B)
while he's here and will be happy to talk to students/faculty/etc.
He will be giving two talks -- the first of which will be this Friday.
Information on the first talk follows.
Friday, July 14 at 2:00pm in GB305
Solvability in Asynchronous Environments
Benny Chor
Computer Science Dept.
Technion, Israel
Abstract:
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.