🚀 go-pugleaf

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.