The Disagreement Power of an Adversary

At the heart of distributed computing lies the fundamental result that the level of agreement that can be obtained in an asynchronous shared memory model where t processes can crash is exactly t + 1. In other words, an adversary that can crash any subset of size at most t can prevent the processes from agreeing on t values. But what about the remaining (2^2^n - n) adversaries that might crash certain combination of processes and not others? This paper presents a precise way to characterize such adversaries by introducing the notion of disagreement power: the biggest integer k for which the adversary can prevent processes from agreeing on k values. We show how to compute the disagreement power of an adversary and how this notion enables to derive n equivalence classes of adversaries.


Publié dans:
Proceedings of the 23rd International Symposium on Distributed Computing, 8-21
Présenté à:
23rd International Symposium on Distributed Computing, Elce, September 2009
Année
2009
ISBN:
978-3-642-04354-3
Mots-clefs:
Laboratoires:




 Notice créée le 2010-01-20, modifiée le 2019-12-05

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

Évaluer ce document:

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