Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!neat.ai.toronto.edu!benaloh
From: benaloh@theory.toronto.edu (Josh Benaloh)
Newsgroups: ont.events
Subject: Benny Chor, Friday 14 July 1989: THEORY SEMINAR
Message-ID: <89Jul13.151731edt.10458@neat.ai.toronto.edu>
Date: 13 Jul 89 18:33:11 GMT
Lines: 31


           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.