Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Simultaneous Consensus vs Set Agreement
du 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) 
UrlLIP6-Paris 



Aucun document lié à cet événement.

Retour
Retour à l'index