research-article

Unbeatable Set Consensus via Topological and Combinatorial Reasoning

Authors:

Armando Castañeda,

Yannai A. Gonczarowski,

Yoram MosesAuthors Info & Claims

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

Pages 107 - 116

https://doi.org/10.1145/2933057.2933120

Published: 25 July 2016 Publication History

Abstract

The set consensus problem has played an important role in the study of distributed systems for over two decades. Indeed, the search for lower bounds and impossibility results for this problem spawned the topological approach to distributed computing, which has given rise to new techniques in the design and analysis of protocols. The design of efficient solutions to set consensus has also proven to be challenging. In the synchronous crash failure model, the literature contains a sequence of solutions to set consensus, each improving upon the previous ones. This paper presents an unbeatable protocol for nonuniform k-set consensus in the synchronous crash failure model. This is an efficient protocol whose decision times cannot be improved upon. Moreover, the description of our protocol is extremely succinct. Proving unbeatability of this protocol is a nontrivial challenge. We provide two proofs for its unbeatability: one is a subtle constructive combinatorial proof, and the other is a topological proof of a new style. These two proofs provide new insight into the connection between topological reasoning and combinatorial reasoning about protocols, which has long been a subject of interest. In particular, our topological proof reasons in a novel way about subcomplexes of the protocol complex, and sheds light on an open question posed by Guerraoui and Pochon (2009). Finally, using the machinery developed in the design of this unbeatable protocol, we propose a protocol for uniform k-set consensus that beats all known solutions by a large margin.

References

[1]

D. Alistarh, S. Gilbert, R. Guerraoui, and C. Travers. Of choices, failures and asynchrony: The many faces of set agreement. Algorithmica, 62(1--2):595--629, 2012.

Digital Library

[2]

E. Borowsky and E. Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In Proc. 25th ACM Symp. on Theory of Computing, pages 91--100, 1993.

Digital Library

[3]

A. Casta neda, Y. A. Gonczarowski, and Y. Moses. Brief announcement: Pareto-optimal solutions to consensus and set consensus. In Proc. 32nd ACM Symp. on Principles of Distributed Computing, pages 113--115, 2013.

Digital Library

[4]

A. Casta neda, Y. A. Gonczarowski, and Y. Moses. Unbeatable consensus. In Proc. 28th International Symp. on Distributed Computing, pages 91{106, 2014. Full version available on arXiv.

[5]

A. Casta neda, Y. A. Gonczarowski, and Y. Moses. Unbeatable set consensus via topological and combinatorial reasoning. Available on arXiv.org, 2016.

[6]

B. Charron-Bost and A. Schiper. Uniform consensus is harder than consensus. Journal of Algorithms, 51(1):15--37, 2004.

Digital Library

[7]

S. Chaudhuri. Agreement is harder than consensus: Set consensus problems in totally asynchronous systems. In Proc. 9th ACM Symp. on Principles of Distributed Computing, pages 311--324, 1990.

Digital Library

[8]

S. Chaudhuri, M. Herlihy, N. A. Lynch, and M. R. Tuttle. Tight bounds for k-set agreement. Journal of the ACM, 47(5):912--943, 2000.

Digital Library

[9]

B. Coan. A communication-efficient canonical form for fault-tolerant distributed protocols. In Proc. 5th ACM Symp. on Principles of Distributed Computing, pages 63--72, 1986.

Digital Library

[10]

D. Dolev, R. Reischuk, and H. R. Strong. Early stopping in Byzantine agreement. Journal of the ACM, 34(7):720--741, 1990.

Digital Library

[11]

P. Dutta, R. Guerraoui, and B. Pochon. Tight bounds on early local decisions in uniform consensus. In Proc. 17th International Symp. on Distributed Computing, pages 264--278, 2003.

[12]

C. Dwork and Y. Moses. Knowledge and common knowledge in a Byzantine environment: crash failures. Information and Computation, 88(2):156--186, 1990.

Digital Library

[13]

M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty processor. Journal of the ACM, 32(2):374--382, 1985.

Digital Library

[14]

E. Gafni, R. Guerraoui, and B. Pochon. The complexity of early deciding set agreement. SIAM Journal on Computing, 40(1):63--78, 2011.

Digital Library

[15]

R. Guerraoui, M. Herlihy, and B. Pochon. A topological treatment of early-deciding set-agreement. Theoretical Computer Science, 410(6--7):570--580, 2009.

Digital Library

[16]

R. Guerraoui and B. Pochon. The complexity of early deciding set agreement: How can topology help? Electr. Notes Theor. Comput. Sci., 230:71--78, 2009.

Digital Library

[17]

V. Hadzilacos. On the relationship between the atomic commitment and consensus problems. In Fault-Tolerant Distributed Computing, pages 201--208, 1986.

Digital Library

[18]

J. Y. Halpern, Y. Moses, and O. Waarts. A characterization of eventual Byzantine agreement. SIAM Journal on Computing, 31(3):838--865, 2001.

Digital Library

[19]

M. Herlihy, D. N. Kozlov, and S. Rajsbaum. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, 2013.

Digital Library

[20]

M. Herlihy, Y. Moses, and M. R. Tuttle. Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions. In Proc. 30th ACM Symp. on Principles of Distributed Computing, pages 231--238, 2011.

Digital Library

[21]

M. Herlihy, S. Rajsbaum, and M. R. Tuttle. Unifying synchronous and asynchronous message-passing models. In Proc. 17th ACM Symp. on Principles of Distributed Computing, pages 133--142, 1998.

Digital Library

[22]

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

Digital Library

[23]

I. Keidar and S. Rajsbaum. A simple proof of the uniform consensus synchronous lower bound. Information Processing Letters, 85(1):47--52, 2003.

Digital Library

[24]

Y. Moses. Relating knowledge and coordinated action: The knowledge of preconditions principle. In Proc. 15th Conference on Theoretical Aspects of Rationality and Knowledge, pages 207--216, 2015.

[25]

Y. Moses and M. R. Tuttle. Programming simultaneous actions using common knowledge. Algorithmica, 3:121--169, 1988.

Digital Library

[26]

P. R. Parv--edy, M. Raynal, and C. Travers. Early-stopping k-set agreement in synchronous systems prone to any number of process crashes. In Proc. 8th International Conference on Parallel Computing Technologies, pages 49--58, 2005.

Digital Library

[27]

M. Raynal. Optimal early stopping uniform consensus in synchronous systems with process omission failures. In Proc. 16th Annual ACM Symp. on Parallelism in Algorithms and Architectures, pages 302{310. ACM Press, 2004.

Digital Library

[28]

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

Digital Library

[29]

X. Wang, Y. M. Teo, and J. Cao. A bivalency proof of the lower bound for uniform consensus. Information Processing Letters, 96(5):167--174, 2005.

Digital Library

Cited By

Castañeda AGonczarowski YMoses Y(2022)Unbeatable consensusDistributed Computing10.1007/s00446-021-00417-3Online publication date: 12-Jan-2022
https://doi.org/10.1007/s00446-021-00417-3
Goubault ÉLedent JRajsbaum S(2020)A simplicial complex model for dynamic epistemic logic to study distributed task computabilityInformation and Computation10.1016/j.ic.2020.104597(104597)Online publication date: Jun-2020
https://doi.org/10.1016/j.ic.2020.104597
Vukotic IRahli VEsteves-Veríssimo P(2019)Asphalion: trustworthy shielding against Byzantine faultsProceedings of the ACM on Programming Languages10.1145/33605643:OOPSLA(1-32)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360564
Show More Cited By

Index Terms

Unbeatable Set Consensus via Topological and Combinatorial Reasoning
1. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

Brief announcement: pareto optimal solutions to consensus and set consensus
PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computing

A protocol P is Pareto-optimal if no protocol Q can decide as fast as P for all adversaries, while allowing at least one process to decide strictly earlier, in at least one instance. Pareto optimal protocols cannot be improved upon. We present the first ...
Unbeatable consensus
Abstract
The unbeatability of a consensus protocol, introduced by Halpern et al. (SIAM J Comput 31:838–865, 2001), is a stronger notion of optimality than the accepted notion of early stopping protocols. Using a novel knowledge-based analysis, this paper ...
Optimal Algorithms for Synchronous Byzantine k-Set Agreement
Stabilization, Safety, and Security of Distributed Systems
Abstract
Considering a system made up of n processes prone to Byzantine failures, k-set agreement allows each process to propose a value and decide a value such that at most k different values are decided by the correct (i.e., non-Byzantine) processes, in ... $\frac{}{}$ $\frac{}{}$

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

July 2016

508 pages

ISBN:9781450339643

DOI:10.1145/2933057

General Chair:
George Giakkoupis
INRIA, France

Copyright © 2016 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].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Universidad Nacional Autónoma de México
European Research Council
United States - Israel Binational Science Foundation
Technion-Israel Institute of Technology
Israel Academy of Sciences and Humanities
Israel Science Foundation

Conference

PODC '16

Sponsor:

PODC '16: ACM Symposium on Principles of Distributed Computing

July 25 - 28, 2016

Illinois, Chicago, USA

Acceptance Rates

PODC '16 Paper Acceptance Rate 40 of 149 submissions, 27%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
155
Total Downloads

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

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Castañeda AGonczarowski YMoses Y(2022)Unbeatable consensusDistributed Computing10.1007/s00446-021-00417-3Online publication date: 12-Jan-2022
https://doi.org/10.1007/s00446-021-00417-3
Goubault ÉLedent JRajsbaum S(2020)A simplicial complex model for dynamic epistemic logic to study distributed task computabilityInformation and Computation10.1016/j.ic.2020.104597(104597)Online publication date: Jun-2020
https://doi.org/10.1016/j.ic.2020.104597
Vukotic IRahli VEsteves-Veríssimo P(2019)Asphalion: trustworthy shielding against Byzantine faultsProceedings of the ACM on Programming Languages10.1145/33605643:OOPSLA(1-32)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360564
Goubault ÉLedent JRajsbaum S(2018)A Simplicial Complex Model for Dynamic Epistemic Logic to study Distributed Task ComputabilityElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.277.6277(73-87)Online publication date: 7-Sep-2018
https://doi.org/10.4204/EPTCS.277.6
Castañeda AMoses YRaynal MRoy M(2017)Early Decision and Stopping in Synchronous Consensus: A Predicate-Based Guided TourNetworked Systems10.1007/978-3-319-59647-1_16(206-221)Online publication date: 14-May-2017
https://doi.org/10.1007/978-3-319-59647-1_16

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