Evènement pour le groupe Algorithmique Distribuée

Date 2013-03-25  14:00-15:00
TitreSimultaneous Consensus vs Set Agreement 
RésuméIn the traditional consensus task, processes are required to agree on a common value chosen among the initial values of the participants. It is well known that consensus cannot be solved in crashed-prone, asynchronous distributed systems. Two generalizations of the consensus problem have been introduced: k-set agreement and k-simultaneous consensus. The k-set agreement task has the same requirements as consensus except that processes are allowed to decide up to k distinct values. In the k-simultaneous consensus task, each process participates simultaneously in k instances of consensus and is required to decide in at least one of them; any two processes deciding in the same instance must decide the same value. In this talk, we compare the computability of these problems in two central models in distributed computing: shared memory and message passing. We show that even though the two problems are equivalent in shared memory, k-simultaneous consensus is strictly harder than k-set agreement in the message passing model. This result will serve as a basis for a discussion about different models of computation and their respective power.  
LieuSalle 178 
OrateurZohir Bouzid (LIP6) 

Aucun document lié à cet événement.

Retour à l'index