More Web Proxy on the site http://driver.im/

research-article

Asynchronous Approximate Agreement

Author:

A.D. FeketeAuthors Info & Claims

Information and Computation, Volume 115, Issue 1

Pages 95 - 124

https://doi.org/10.1006/inco.1994.1094

Published: 15 November 1994 Publication History

Abstract

This paper examines the Approximate Agreement Problem in an asynchronous failure-by-omission system with deterministic protocols. We give a simple algorithm, and prove that the algorithm is optimal by considering the power of the "adversary" scheduler to disrupt processors views. We show that the adversary need not cause any omissions to achieve its purpose, and therefore no algorithm can do better than simply to operate round-by-round, as our does. We extend these results to asynchronous crash-failure systems. The resulting understanding of the adversary should be applicable to other problems in asynchronous failure-by-omission or crash-failure-systems.

References

[1]

CHANDY, K., AND MISRA, J. (1986), How processes learn, Distrib. Comput. 1 , 40-52.

Digital Library

[2]

COAN, B. (1988), A compiler that increases the fault tolerance of asynchronous protocols, IEEE Trans. Comput. 37 , No. 12, 1541-1553.

Digital Library

[3]

DOLEV, D., DWORK, C., AND STOCKMEYER, L. (1987), On the minimal synchronism needed for distributed consensus, J. Assoc. Comput. Mach. 34 , No. 1, 77-97.

Digital Library

[4]

DOLEV, D., LYNCH, N., PINTER, S., STARK, E., AND WEIHL, W. (1986), Reaching approximate agreement in the presence of faults, J. Assoc. Comput. Mach. 33 , No. 3, 499-516.

Digital Library

[5]

FEKETE, A. (1990), Asymptotically optimal algorithms for approximate agreement, Distrib. Comput. 4 , 9-29.

[6]

FISCHER, M. (1983), "The Consensus Problem in Unreliable Distributed Systems (A Brief Survey)," Yale University Technical Report YALEU/DCS/RR-273.

[7]

FISCHER, M., LYNCH, N., AND PATTERSON, M. (1985), Impossibility of distributed consensus with one faulty process, J. Assoc. Comput. Mach. 32 , No. 2, 374-382.

Digital Library

[8]

HALPERN, J., AND MOSES, Y. (1990), Knowledge and common knowledge in a distributed environment, J. Assoc. Comput. Mach. 37 , No. 3, 549-587.

Digital Library

[9]

HALPERN, J., SIMONS, B., STRONG, R., AND DOLEV, D. (1984), Fault-tolerant clock synchronization, in "Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing," pp. 89-102.

[10]

LUNDELIUS, J., AND LYNCH, N. (1984), A new fault-tolerant algorithm for clock synchronization, Inform and Control 62 , 190-204.

[11]

LAMPORT, L., AND MELLIAR-SMITH, P. Synchronizing clocks in the presence of faults, J. Assoc. Comput. Mach. 32 , No. 1, 52-78.

[12]

MAHANEY, S., AND SCHNEIDER, F. (1985), Inexact Agreement: Accuracy, precision and graceful degradation, in "Proceedings of the 4th ACM Symposium on Principles of Distributed Computing," pp. 237-249.

[13]

MOSES, Y., AND TUTTLE, M. (1988), Programming Simultaneous actions using common knowledge, Algorithmica 3 , 249-259.

Digital Library

[14]

PEASE, M., SHOSTAK, R., AND LAMPORT, L. (1980), Reaching Agreement in the presence of faults, J. Assoc. Comput. Mach. 27 , No. 2, 228-234.

Digital Library

[15]

WELCH, J. L., (1987), Simulating synchronous processors, Inform and Comput. 74 , 159-171.

Digital Library

Cited By

Függer MNowak TSchwarz M(2021)Tight Bounds for Asymptotic and Approximate ConsensusJournal of the ACM10.1145/348524268:6(1-35)Online publication date: 28-Oct-2021
https://dl.acm.org/doi/10.1145/3485242
Alistarh DEllen FRybicki J(2021)Wait-Free Approximate Agreement on GraphsStructural Information and Communication Complexity10.1007/978-3-030-79527-6_6(87-105)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-79527-6_6
Függer MNowak TSchwarz MNewport CKeidar I(2018)Tight Bounds for Asymptotic and Approximate ConsensusProceedings of the 2018 ACM Symposium on Principles of Distributed Computing10.1145/3212734.3212762(325-334)Online publication date: 23-Jul-2018
https://dl.acm.org/doi/10.1145/3212734.3212762
Show More Cited By

Index Terms

Asynchronous Approximate Agreement

Recommendations

Asynchronous Byzantine Agreement with optimal resilience

We present an efficient, optimally-resilient Asynchronous Byzantine Agreement (ABA) protocol involving $$n = 3t+1$$n=3t+1 parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, capable of corrupting ...
Multidimensional Approximate Agreement with Asynchronous Fallback
SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures

Multidimensional Approximate Agreement considers a setting of n parties, where each party holds a vector in ℝD as input. The honest parties are required to obtain very close outputs in ℝD that lie inside the convex hull of their inputs.

Existing ...
Simple and efficient asynchronous byzantine agreement with optimal resilience
PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

Consider a completely asynchronous network consisting of n parties where every two parties are connected by a private channel. An adversary A_t with unbounded computing power actively controls at most t = ([n/3] − 1) out of n parties in Byzantine ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 115, Issue 1

Nov. 15, 1994

178 pages

ISSN:0890-5401

Editor:
Albert R. Meyer
Massachusetts Institute of Technology, Cambridge

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 15 November 1994

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Függer MNowak TSchwarz M(2021)Tight Bounds for Asymptotic and Approximate ConsensusJournal of the ACM10.1145/348524268:6(1-35)Online publication date: 28-Oct-2021
Alistarh DEllen FRybicki J(2021)Wait-Free Approximate Agreement on GraphsStructural Information and Communication Complexity10.1007/978-3-030-79527-6_6(87-105)Online publication date: 28-Jun-2021
Függer MNowak TSchwarz MNewport CKeidar I(2018)Tight Bounds for Asymptotic and Approximate ConsensusProceedings of the 2018 ACM Symposium on Principles of Distributed Computing10.1145/3212734.3212762(325-334)Online publication date: 23-Jul-2018
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
Okun M(2010)Strong order-preserving renaming in the synchronous message passing modelTheoretical Computer Science10.1016/j.tcs.2010.06.001411:40-42(3787-3794)Online publication date: 1-Sep-2010
Jelasity MMontresor ABabaoglu O(2005)Gossip-based aggregation in large dynamic networksACM Transactions on Computer Systems10.1145/1082469.108247023:3(219-252)Online publication date: 1-Aug-2005
Fich FRuppert E(2003)Hundreds of impossibility results for distributed computingDistributed Computing10.1007/s00446-003-0091-y16:2-3(121-163)Online publication date: 1-Sep-2003
Lynch N(1996)Distributed AlgorithmsundefinedOnline publication date: 16-Apr-1996

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents