The disagreement power of an adversary |
| |
Authors: | Carole Delporte-Gallet Hugues Fauconnier Rachid Guerraoui Andreas Tielmann |
| |
Affiliation: | 1. LIAFA, Universit?? Paris Diderot, Paris, France 2. School of Computer and Communication Sciences, EPFL, Lausanne, Switzerland
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|