research-article

An Asynchronous Computability Theorem for Fair Adversaries

Authors:

Petr Kuznetsov,

Thibault Rieutord,

Yuan HeAuthors Info & Claims

PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing

Pages 387 - 396

https://doi.org/10.1145/3212734.3212765

Published: 23 July 2018 Publication History

Abstract

This paper proposes a simple topological characterization of a large class of fair adversarial models via affine tasks: sub-complexes of the second iteration of the standard chromatic subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. Fair adversaries include, but are not restricted to, the models of wait-freedom, t-resilience, and k-concurrency. Our results generalize and improve all previously derived topological characterizations of the ability of a model to solve distributed tasks.

References

[1]

Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit . 1993. Atomic Snapshots of Shared Memory. J. ACM Vol. 40, 4 (1993), 873--890.

Digital Library

[2]

Bowen Alpern and Fred B. Schneider . 1985. Defining Liveness. Inform. Process. Lett. Vol. 21, 4 (Oct. . 1985), 181--185.

[3]

Elizabeth Borowsky and Eli Gafni . 1993 a. Generalized FLP impossibility result for t-resilient asynchronous computations. In STOC. 91--100.

Digital Library

[4]

Elizabeth Borowsky and Eli Gafni . 1993 b. Immediate atomic snapshots and fast renaming. In PODC. 41--51.

Digital Library

[5]

Elizabeth Borowsky and Eli Gafni . 1997. A simple algorithmically reasoned characterization of wait-free computation (extended abstract). In PODC. 189--198.

Digital Library

[6]

Zohir Bouzid, Eli Gafni, and Petr Kuznetsov . 2014. Strong Equivalence Relations for Iterated Models. In OPODIS. 139--154.

[7]

Soma Chaudhuri . 1990. Agreement is Harder than Consensus: Set Consensus Problems in Totally Asynchronous Systems. In PODC. 311--324.

Digital Library

[8]

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov: . 2016. Set-Consensus Collections are Decidable. In OPODIS. 7:1--7:15.

[9]

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Andreas Tielmann . 2011. The disagreement power of an adversary. Distributed Computing Vol. 24, 3--4 (2011), 137--147.

Digital Library

[10]

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson . 1985. Impossibility of Distributed Consensus with one Faulty Process. J. ACM Vol. 32, 2 (April . 1985), 374--382.

Digital Library

[11]

Eli Gafni . 1998. Round-by-Round Fault Detectors (extended abstract): Unifying Synchrony and Asynchrony PODC. 143--152.

Digital Library

[12]

Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord . 2016. Read-Write Memory and k-Set Consensus as an Affine Task OPODIS. 6:1--6:17.

[13]

Eli Gafni and Petr Kuznetsov . 2010. Turning Adversaries into Friends: Simplified, Made Constructive, and Extended OPODIS. 380--394.

Digital Library

[14]

Eli Gafni and Petr Kuznetsov . 2011. Relating L-Resilience and Wait-Freedom via Hitting Sets ICDCN. 191--202.

Digital Library

[15]

Eli Gafni, Petr Kuznetsov, and Ciprian Manolescu . 2014. A generalized asynchronous computability theorem. In PODC. 222--231.

Digital Library

[16]

Eli Gafni and Sergio Rajsbaum . 2010. Distributed Programming with Tasks. In OPODIS. 205--218.

Digital Library

[17]

Maurice Herlihy . 1991. Wait-free synchronization. Transactions on Programming Languages and Systems Vol. 13, 1 (Jan. . 1991), 123--149.

Digital Library

[18]

Maurice Herlihy, Dmitry N. Kozlov, and Sergio Rajsbaum . 2014. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann.

Digital Library

[19]

Maurice Herlihy and Sergio Rajsbaum . 2012. Simulations and reductions for colorless tasks. In PODC. 253--260.

Digital Library

[20]

Maurice Herlihy and Nir Shavit . 1999. The topological structure of asynchronous computability. J. ACM Vol. 46, 2 (1999), 858--923.

Digital Library

[21]

Dmitry N. Kozlov . 2012. Chromatic Subdivision of a Simplicial Complex. Homology, Homotopy and Applications Vol. 14, 1 (2012), 1--13.

[22]

Petr Kuznetsov . 2012. Understanding Non-Uniform Failure Models. Bulletin of the EATCS Vol. 106 (2012), 53--77.

[23]

Petr Kuznetsov and Thibault Rieutord . 2017. Agreement Functions for Distributed Computing Models NETYS. 175--190.

[24]

Petr Kuznetsov and Thibault Rieutord . 2018. Affine Tasks for k-Test-and-Set. Technical Report. https://hal.archives-ouvertes.fr/hal-01810601

[25]

Petr Kuznetsov, Thibault Rieutord, and Yuan He . 2017 a. An Asynchronous Computability Theorem for Fair Adversaries. Technical Report. https://hal.archives-ouvertes.fr/hal-01572257v3

[26]

Petr Kuznetsov, Thibault Rieutord, and Yuan He . 2017 b. Brief Announcement: Compact Topology of Shared-Memory Adversaries DISC. 56:1--56:4.

[27]

Nancy A. Lynch . 1996. Distributed Algorithms. Morgan Kaufmann.

Digital Library

[28]

Michael Saks and Fotios Zaharoglou . 2000. Wait-Free k-Set Agreement Is Impossible: The Topology of Public Knowledge. SIAM J. Comput. Vol. 29 (2000), 1449--1483.

Digital Library

[29]

Vikram Saraph, Maurice Herlihy, and Eli Gafni . 2016. Asynchronous Computability Theorems for t-Resilient Systems DISC. 428--441.

[30]

Edwin H. Spanier . 1966. Algebraic topology. McGraw-Hill Book Co.

[31]

Gadi Taubenfeld . 2010. The computational structure of progress conditions DISC. 221--235.

Digital Library

Cited By

Nowak TSchmid UWinkler K(2024)Topological Characterization of Consensus in Distributed SystemsJournal of the ACM10.1145/368730271:6(1-48)Online publication date: 22-Aug-2024
https://dl.acm.org/doi/10.1145/3687302
Castañeda Avan Ditmarsch HRosenblueth DVelázquez D(2024)Pattern Models: A Dynamic Epistemic Logic For Distributed SystemsThe Computer Journal10.1093/comjnl/bxae01667:7(2421-2440)Online publication date: 17-Feb-2024
https://doi.org/10.1093/comjnl/bxae016
Toyos-Marfurt GKuznetsov P(2024)On the Bit Complexity of Iterated MemoryStructural Information and Communication Complexity10.1007/978-3-031-60603-8_25(456-477)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_25
Show More Cited By

Index Terms

An Asynchronous Computability Theorem for Fair Adversaries
1. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Distributed computing models

Recommendations

A generalized asynchronous computability theorem
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing

We consider the models of distributed computation defined as subsets of the runs of the iterated immediate snapshot model. Given a task T and a model M, we provide topological conditions for T to be solvable in M. When applied to the wait-free model, ...
Topological Characterization of Consensus under General Message Adversaries
PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

In this paper, we provide a rigorous characterization of consensus solvability in synchronous directed dynamic networks controlled by an arbitrary message adversary using point-set topology: We extend the approach introduced by Alpern and Schneider in ...
On Topological Hierarchies of Temporal Properties

The classification of properties of concurrent programs into safety and liveness was first proposed by Lamport [22]. Since then several characterizations of hierarchies of properties have been given, see e.g. [3, 20, 9, 21]; this includes syntactic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing

July 2018

512 pages

ISBN:9781450357951

DOI:10.1145/3212734

General Chairs:
Calvin Newport
Georgetown University, USA
,
Idit Keidar
Technion, Israel

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Best Paper

Author Tags

Qualifiers

Research-article

Funding Sources

ANR-DFG project DISCMAT

Conference

PODC '18

PODC '18: ACM Symposium on Principles of Distributed Computing

July 23 - 27, 2018

Egham, United Kingdom

Acceptance Rates

PODC '18 Paper Acceptance Rate 41 of 163 submissions, 25%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
156
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nowak TSchmid UWinkler K(2024)Topological Characterization of Consensus in Distributed SystemsJournal of the ACM10.1145/368730271:6(1-48)Online publication date: 22-Aug-2024
https://dl.acm.org/doi/10.1145/3687302
Castañeda Avan Ditmarsch HRosenblueth DVelázquez D(2024)Pattern Models: A Dynamic Epistemic Logic For Distributed SystemsThe Computer Journal10.1093/comjnl/bxae01667:7(2421-2440)Online publication date: 17-Feb-2024
https://doi.org/10.1093/comjnl/bxae016
Toyos-Marfurt GKuznetsov P(2024)On the Bit Complexity of Iterated MemoryStructural Information and Communication Complexity10.1007/978-3-031-60603-8_25(456-477)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_25
Fraigniaud PPaz ARajsbaum SMilani AWoelfel P(2022)A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate AgreementProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538422(460-470)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538422
Kuznetsov PRieutord T(2020)Affine Tasks for k-Test-and-SetStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-64348-5_12(151-166)Online publication date: 25-Nov-2020
https://doi.org/10.1007/978-3-030-64348-5_12
Nowak TSchmid UWinkler KRobinson PEllen F(2019)Topological Characterization of Consensus under General Message AdversariesProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331624(218-227)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331624

View Options

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