Wait-free coordination:

Séminaire de Travers corentin <corentin.travers@gmail.com> le 21  mai 2010 à 10h00, ENS de Lyon, amphi K

abstract : In a distributed system, several entities (nodes,
processors, sensors, etc.)  have to cooperate in order to solve some
tasks. Unfortunately, the very fact that processing entities are
distributed often makes difficult or even impossible to solve even
simple tasks.      In particular, message transfers may experience
unpredictable delays due to network asynchrony and nodes may fail.

An important question is to understand what can be computed in a
distributed system prone to a given level of uncertainty. Uncertainty
being characterized by the kind of failure nodes may suffer and the
timing assumptions of the underlying communication network.

This talk will focus on the wait-free case in which any number of
processes may crash and the network is totally asynchronous. The first
part will give a brief overview of the deep connection between
algebraic/combinatorial topology and distributed computing.
Topological methods have yielded a variety of lower bounds for
distributed computing . One of the most celebrated result is a
characterization of wait-free computability. If time permits, the
second part will try to demonstrate that the wait-free case is central
: the computability question in other models with different
timing/failures assumptions can often be reduced to the wait-free
case. More, this can be done by appropriate algorithmic construction.