id: 06003524
dt: j
an: 06003524
au: Delporte-Gallet, Carole; Fauconnier, Hugues; Guerraoui, Rachid; Tielmann,
    Andreas
ti: The disagreement power of an adversary.
so: Distrib. Comput. 24, No. 3-4, 137-147 (2011).
py: 2011
pu: Springer-Verlag, Berlin
la: EN
cc: 
ut: distributed computing; asynchronous shared memory model; adversaries;
    disagreement power
ci: 
li: doi:10.1007/s00446-010-0122-4
ab: Summary: 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 all the other $2^{2^{n} - 1} - (n+1)$ adversaries that are not
    uniform in this sense and might crash certain combination of processes
    and not others? This paper presents a precise way to classify all
    adversaries. We introduce 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 derive $n$ equivalence classes of adversaries.
rv: