CS&E Seminar: Corentin Travers - 1 July 2010 - 12.00 @ Aula Magna

Speaker Corentin Travers Laboratoire d'Informatique de Paris 6

Title Weak coordination tasks in asynchronous distributed systems

In an asynchronous distributed system, independent processes run at varying speeds and may even fail; they communicate through unsynchronized primitives, like sending and receiving messages over an asynchronous network or by writing and reading from shared registers. To perform useful computation, processes, however, need to coordinate their actions. This is theoretically modeled as solving a coordination task, where processes start with some inputs and have to output values satisfying certain conditions. A fundamental task is consensus, from which it is possible to solve any other coordination task. However, this task is not solvable in asynchronous failures prone distributed environments.

We study sub-consensus tasks, i.e., coordination tasks that are weaker than consensus. In particular, k-set-consensus extends consensus by allowing processes to decide on a small number (k) of values. Sub-consensus tasks are the only coordination tasks that can be solved in asynchronous systems without relying on strong synchronisation primitives. Therefore it is crucial to understand what make them solvable. This talk explores reduction among various sub-consensus tasks, depending on the amount of synchronism provided by the system.

Corentin Travers is a postdoctoral researcher at LIP6, University of PARIS 6. He received its Ph.D from the university of Rennes 1 in 2007. Between 2007 and 2009, he has been a postdoctoral researcher at UPM, Madrid and at the Technion, Haifa. His research interests are in the theory of distributed computing, especially issues related to algorithms and fault tolerance.

Massimo Mecella and Domenico Lembo (Chairs of the Seminars series)

Web page of the Seminars series: http://www.dis.uniroma1.it/~seminf/