Loading...
Please wait, while we are loading the content...
Similar Documents
The Disagreement Power of an Adversary
| Content Provider | Hyper Articles en Ligne (HAL) |
|---|---|
| Author | Delporte-Gallet, Carole Fauconnier, Hugues Guerraoui, Rachid Tielmann, Andreas |
| 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 the rest ($2^{2^n} -n$) adversaries that might crash certain combination of processes and not others? Given any adversary, what is its disagreement power? i.e., the biggest $k$ for which it can prevent processes from agreeing on $k$ values. This paper answers this question. We present a general characterization of adversaries that enables to directly derive their disagreement power. We use our characterization to also close the question of the weakest failure detector for $k$-set agreement. So far, the result has been obtained for two extreme cases: consensus and $n-1$-set agreement. We answer this question for any $k$ and any adversary. |
| Related Links | https://hal.science/hal-00376981/file/disagreement_power.pdf |
| Language | English |
| Publisher | HAL CCSD |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
