Cited By
View all- 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
On the hardness of the strongly dependent decision problem
Pages 120 - 123
Abstract
We present necessary and sufficient conditions for solving the strongly dependent decision (SDD) problem in various distributed systems. Our main contribution is a novel characterization of the SDD problem based on point-set topology. For partially synchronous systems, we show that any algorithm that solves the SDD problem induces a set of executions that is closed with respect to the point-set topology. We also show that the SDD problem is not solvable in the asynchronous system augmented with any arbitrarily strong failure detectors.
References
[1]
Bowen Alpern and Fred B. Schneider, Defining liveness, Information Processing Letters <b>21</b> (1985), no. 4, 181--185.
[2]
Tushar Deepak Chandra and Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM <b>43</b> (1996), no. 2, 225--267.
[3]
Tushar Deepak Chandra, Vassos Hadzilacos and Sam Toueg, The Weakest Failure Detector for Solving Consensus, Journal of the ACM, <b>43</b> (1996), no 4, 685--722.
[4]
Bernadette Charron-Bost, Rachid Guerraoui, and André Schiper, Synchronous system and perfect failure detector: solvability and efficiency issues, Proceedings of the International Conference on Dependable System and Networks (DSN'00), 2000.
[5]
Danny Dolev, Cynthia Dwork, and Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM <b>34</b> (1987), no. 1, 77--97.
[6]
Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM <b>35</b> (1988), no. 2, 288--323.
[7]
Lisbeth Fajstrup, Eric Goubault, Emmanuel Haucourt, Samuel Mimram, and Martin Raussen, Directed Algebraic Topology and Concurrency, Springer, 2016.
[8]
Michael J. Fischer, Nancy A. Lynch, and M. S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM <b>32</b> (1985), no. 2, 374--382.
[9]
Maurice Herlihy, Dmitry N. Kozlov, Sergio Rajsbaum, Distributed Computing Through Combinatorial Topology, Morgan Kaufmann, 2013.
[10]
Nancy A. Lynch, Distributed algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996.
[11]
James Munkres, Topology (2nd edition), Pearson, 2000.
[12]
Thomas Nowak, Topology in Distributed Computing, Master's thesis, Vienna University of Technology, 2010.
[13]
Peter Robinson, Ulrich Schmid, The Asynchronous Bounded-Cycle model, Theor. Comput. Sci. 412(40): 5580--5601 (2011).
Recommendations
Using nondeterminism to amplify hardness
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computingWe revisit the problem of hardness amplification in NP, as recently studied by O'Donnell (STOC '02). We prove that if NP has a balanced function f such that any circuit of size s(n) fails to compute f on a 1/poly(n) fraction of inputs, then NP has a ...
Average-case hardness of NP from exponential worst-case hardness assumptions
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of ComputingA long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)...
Impossibility results on weakly black-box hardness amplification
FCT'07: Proceedings of the 16th international conference on Fundamentals of Computation TheoryWe study the task of hardness amplification which transforms a hard function into a harder one. It is known that in a high complexity class such as exponential time, one can convert worst-case hardness into average-case hardness. However, in a lower ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2019
535 pages
Copyright © 2019 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 ACM 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]
Sponsors
- SIGOPS: ACM Special Interest Group on Operating Systems
- Indian Institute of Science: Indian Institute of Science
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 January 2019
Check for updates
Qualifiers
- Short-paper
Conference
ICDCN '19
Sponsor:
- SIGOPS
- Indian Institute of Science
ICDCN '19: International Conference on Distributed Computing and Networking
January 4 - 7, 2019
Bangalore, India
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 45Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Dec 2024
Other Metrics
Citations
Cited By
View all- 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
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in