A Topological Treatment of Early-Deciding Set-Agreement

This paper considers the k-set-agreement problem in a synchronous message passing distributed system where up to t processes can fail by crashing. We determine the number of communication rounds needed for all correct processes to reach a decision in a given run, as a function of k, the degree of coordination, and f <= t the number of processes that actually fail in the run. We prove a lower bound of min(\floor{f/k}+2,\floor{t/k}+1) rounds. Our proof uses simple topological tools to reason about runs of a full information set-agreement protocol. In particular, we introduce a new topological operator, which we call the early deciding operator, to capture rounds where k processes fail but correct processes see only k-1 failures.


Publié dans:
Proceedings of the 10th International Conference On Principles Of Distributed Systems (OPODIS '06)
Présenté à:
OPODIS 2006, Bordeaux, France, December 12-15, 2006
Année
2006
Laboratoires:


Note: Le statut de ce fichier est: Anyone


 Notice créée le 2006-10-05, modifiée le 2020-07-30

n/a:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)