*********************************************************************
*                       Ecole Normale Supe'rieure                   *
*                                                                   *
*                              Se'minaire                           *
*                SEMANTIQUE ET INTERPRETATION ABSTRAITE             *
*                              P. Cousot                            *
*                                                                   *
*                        Vendredi, 14h00--15h30                     *
*                             Salle R, etage -1                     *
*                  DI  ENS  45 rue d'Ulm  75005 Paris               *
*********************************************************************

*** Vendredi 14 septembre 2001 **** 14h00 *****************************

Leslie LAMPORT (Compaq)

Arbiter-Free Synchronization

Re'sume' : Implementing traditional forms of multiprocess synchronization
requires a hardware arbiter.  This talk considers what forms of
synchronization are possible without an arbiter.  A simple
arbiter-free communication mechanism consists of a one-bit bit
register with two asynchronous operations: setting the bit and waiting
until the bit is set.  Several variations of such a register are
described that can be shown to have equal power.  The class of
synchronization problems solvable with such registers can be
characterized.  However, more power arbiter-free communication devices
exist, and characterizing the most general form of arbiter-free
synchronization remains an unsolved problem.

*********************************************************************
Pour recevoir l'annonce par courrier electronique: cousot@di.ens.fr
WWW: http://www.di.ens.fr/~cousot/annonceseminaire.shtml
*********************************************************************