short-paper

The disagreement power of an adversary: extended abstract

Authors:

Carole Delporte-Gallet,

Hugues Fauconnier,

Rachid Guerraoui,

Andreas TielmannAuthors Info & Claims

PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

Pages 288 - 289

https://doi.org/10.1145/1582716.1582769

Published: 10 August 2009 Publication History

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²ⁿ − 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 classes of adversaries.

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.

References

[1]

A. F. Anta, S. Rajsbaum, and C. Travers. Weakest failure detectors via an egg-laying simulation (preliminary version). Tech Report 2, Systems and Communications, Jan. 2009. Also appears as a brief announcement in PODC 2009.

[2]

E. Borowsky and E. Gafni. Generalized flp impossibility result for t-resilient asynchronous computations. In STOC, pages 91--100, 1993.

Digital Library

[3]

E. Borowsky, E. Gafni, N. A. Lynch, and S. Rajsbaum. The BG distributed simulation algorithm. Distributed Computing, 14(3):127--146, 2001.

Digital Library

[4]

A. B.V, A. Patra, A. Choudhary, K. Srinathan, and C. Pandu Rangan. On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary. In PODC, pages 115--124, 2008.

Digital Library

[5]

T. D. Chandra, V. Hadzilacos, P. Jayanti, and S. Toueg. Generalized irreducibility of consensus and the equivalence of t-resilient and wait-free implementations of consensus. SIAM J. Comput., 34(2):333--357, 2004.

Digital Library

[6]

T. D. Chandra, V. Hadzilacos, and S. Toueg. The weakest failure detector for solving consensus. In PODC, pages 147--158, 1992.

Digital Library

[7]

M. Fitzi and U. M. Maurer. Efficient byzantine agreement secure against general adversaries. In DISC, pages 134--148, 1998.

Digital Library

[8]

E. Gafni and P. Kuznetsov. The weakest failure detector for solving k-set agreement. In PODC, 2009.

Digital Library

[9]

R. Guerraoui, M. Herlihy, P. Kouznetsov, N. A. Lynch, and C. C. Newport. On the weakest failure detector ever. In PODC, pages 235--243, 2007.

Digital Library

[10]

M. Herlihy and S. Rajsbaum. The decidability of distributed decision tasks (extended abstract). In STOC, pages 589--598, 1997.

Digital Library

[11]

M. Herlihy and N. Shavit. The topological structure of asynchronous computability. J. ACM, 46(6):858--923, 1999.

Digital Library

[12]

F. P. Junqueira and K. Marzullo. Designing algorithms for dependent process failures. In Future Directions in Distributed Computing, pages 24--28, 2003.

Digital Library

[13]

W.-K. Lo and V. Hadzilacos. Using failure detectors to solve consensus in asynchronous shared-memory systems (extended abstract). In WDAG, pages 280--295, 1994.

Digital Library

[14]

M. E. Saks and F. Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput., 29(5):1449--1483, 2000.

Digital Library

[15]

P. Zielinski. Anti-Omega: the weakest failure detector for set agreement. In PODC, pages 55--64, 2008.

Digital Library

Cited By

Taubenfeld G(2018)A Closer Look at Fault ToleranceTheory of Computing Systems10.1007/s00224-017-9779-462:5(1085-1108)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s00224-017-9779-4
Taubenfeld GKowalski DPanconesi A(2012)A closer look at fault toleranceProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332484(261-270)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2332432.2332484
Gafni EKuznetsov P(2011)On set consensus numbersDistributed Computing10.1007/s00446-011-0142-824:3-4(149-163)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1007/s00446-011-0142-8
Show More Cited By

Index Terms

The disagreement power of an adversary: extended abstract
1. Hardware
  1. Integrated circuits
    1. Semiconductor memory
      1. Dynamic memory
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

The disagreement power of an adversary
DISC'09: Proceedings of the 23rd international conference on Distributed computing

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 ...
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 ...
On the computability power and the robustness of set agreement-oriented failure detector classes

Solving agreement problems deterministically, such as consensus and k-set agreement, in asynchronous distributed systems prone to an unbounded number of process failures has been shown to be impossible. To circumvent this impossibility, unreliable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

August 2009

356 pages

ISBN:9781605583969

DOI:10.1145/1582716

General Chair:
Srikanta Tirthapura
Iowa State University, USA
,
Program Chair:
Lorenzo Alvisi
The University of Texas at Austin, USA

Copyright © 2009 Copyright is held by the author/owner(s).

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

PODC '09

Sponsor:

PODC '09: ACM Symposium on Principles of Distributed Computing

August 10 - 12, 2009

AB, Calgary, Canada

Acceptance Rates

PODC '09 Paper Acceptance Rate 27 of 110 submissions, 25%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
140
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Taubenfeld G(2018)A Closer Look at Fault ToleranceTheory of Computing Systems10.1007/s00224-017-9779-462:5(1085-1108)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s00224-017-9779-4
Taubenfeld GKowalski DPanconesi A(2012)A closer look at fault toleranceProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332484(261-270)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2332432.2332484
Gafni EKuznetsov P(2011)On set consensus numbersDistributed Computing10.1007/s00446-011-0142-824:3-4(149-163)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1007/s00446-011-0142-8
Bouzid ZTravers C(2010)(anti-Ωx × Σz)-based k-set agreement algorithmsProceedings of the 14th international conference on Principles of distributed systems10.5555/1940234.1940256(189-204)Online publication date: 14-Dec-2010
https://dl.acm.org/doi/10.5555/1940234.1940256
Herlihy MRajsbaum S(2010)Concurrent computing and shellable complexesProceedings of the 24th international conference on Distributed computing10.5555/1888781.1888795(109-123)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.5555/1888781.1888795
Herlihy MRajsbaum SRicha AGuerraoui R(2010)The topology of shared-memory adversariesProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835724(105-113)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835724
Gafni EKuznetsov PRicha AGuerraoui R(2010)Brief announcementProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835719(81-82)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835719
Herlihy MRajsbaum S(2010)Concurrent Computing and Shellable ComplexesDistributed Computing10.1007/978-3-642-15763-9_10(109-123)Online publication date: 2010
https://doi.org/10.1007/978-3-642-15763-9_10
Fernandez Anta ARajsbaum STravers CTirthapura SAlvisi L(2009)Brief announcementProceedings of the 28th ACM symposium on Principles of distributed computing10.1145/1582716.1582770(290-291)Online publication date: 10-Aug-2009
https://dl.acm.org/doi/10.1145/1582716.1582770
Gafni EKuznetsov PTirthapura SAlvisi L(2009)The weakest failure detector for solving k-set agreementProceedings of the 28th ACM symposium on Principles of distributed computing10.1145/1582716.1582735(83-91)Online publication date: 10-Aug-2009
https://dl.acm.org/doi/10.1145/1582716.1582735
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents