Article

Free access

Detecting global termination conditions in the face of uncertainty

Authors:

Yehuda Afek,

Michael SaksAuthors Info & Claims

PODC '87: Proceedings of the sixth annual ACM Symposium on Principles of distributed computing

Pages 109 - 124

https://doi.org/10.1145/41840.41850

Published: 01 December 1987 Publication History

PDF eReader

References

[1]

Y. Afek. B. Awerbucb, S. Plotkin and M. Saks, Efficient Fault Tolerant Election Algorithms with Different Termination Conditions, Work in progress, 1987.

Google Scholar

[2]

B. Awerbuch and S. Plotkin, Leader Election in faulty networks, Work in progress. 1987.

Google Scholar

[3]

R. Bar-Yehuda and S. Kutten, Fault Tolerant Leader Election with Termination Detection. in General Undirected Networks, in Tech . Rep. CS-1986-12 Duke University, Durham. January 1986.

Digital Library

Google Scholar

[4]

G. Bracha and S. Toueg, A Distributed Algorithm for Generalized Deadlock detection, Proceedings of the third Annual ACM Symposium on Principles of Distributed Computitzg, Vancouver, BC, Canada. August 1984. 285.301.

Digital Library

Google Scholar

[5]

K.M. Chandy and L. Lamport, Dis tri but ed S napshots" Determining Global States of Distributed Systems, ACM TOCS 3(i), (January I985), 63-75.

Digital Library

Google Scholar

[6]

S. Cohen and D. Lehmann, Dynamic systems and their distributed termination, PODC I, (1982), 29-33, ACM.

Digital Library

Google Scholar

[7]

W. Dijkstra and C. S. Scholten, Termination Detection for Diffusing Computations, Information Processing Letters 11-1. (August 1980), 1-4.

Crossref

Google Scholar

[8]

D. Dolev, C. Dwork and k. Stockmeyer, On the Minimal Synchronism Needed for Distributed Consensus, Proc. 24th Syrup. on Foundation of Computer Science, 1983, 393-402.

Google Scholar

[9]

C. Dwork, N. Lynch and L. Stockmeyer, Consensus in the Presence of Partial Svnchronv, Proc. 3rd ACM Syrup. on Principles of Distributed Computing. 1984. 103-118.

Google Scholar

[10]

M. Fischer. N, Lynch and ~I. Paterson. Impossibility of Distributed Consensus with One Faulty Process, Journal of the ACM 32. (April 1985), 374-382.

Digital Library

Google Scholar

[11]

N. Francez. Distributed Termination, ACM Trans. Prog. Lang. and Systems 2,1, (January 1980), 42-55, ACM.

Digital Library

Google Scholar

[12]

N. Francez and M. Rodeh, Achieving Distributed Termination without Freezing, IEEE Trans. Soft. Eng. SE-8. (1982), 287-292.

Google Scholar

[13]

R.G. Gallager, P. A. Humbler and P. M. Spira, A Distributed Algorithm for Minimum Weight Spanning Trees, ACM Trans. Program. Lang. Syst. 5, (Jan 1983). 66-77.

Digital Library

Google Scholar

[14]

O. Goldreich and L. Shrira. The Effect of Link Failures on Computations in Asynchronous Rings, in Proceedings of the ACM Symp. on Principles of Distributed Computing, Calgarey C anada. August 1986. also Tech. Rep.-355. Computer Science Dept Technion 1985.

Digital Library

Google Scholar

[15]

J. Green. Private Communication. 1986,

Google Scholar

[16]

C, W. Lermen and F. B. Schneider, Detecting Distributed Termination When Processors Cat~ Fail. Tech. Rep. 80-4~9. Dep. of Computer Science, Cornell University. Ithaca, Dee. 1980.

Google Scholar

[17]

J. Misra, Detecting Termination of Distributed Computations Using Markers. in Proceedipzgs of the 2nd ACM Symp. PODC. Montreal. August 1983 ~'90-295

Digital Library

Google Scholar

[18]

A. Segall, Distributed Network Protocols. IEEE Transactions on IJlf ormation Theory IT-29. 1 (January 1983), .

Google Scholar

[19]

N. Shavit and N. Francez. A New Approach to Detection of Locally Indica{ive Stability. Proc. 13th ICALP. July 1986, 344-358.

Digital Library

Google Scholar

[20]

I_. Shrira and ~{. Rodeh. Methodologica! Construction of Reliable Distributed Algorithms, in Tech. Rep.-361. Computer Science Dept Technion . Technion. Haifa Israel, March 1985.

Google Scholar

[21]

L. Shrira and O. Goldreich, Electing a Leader in the Presence of Faults" A Ring as a Special Case, in Tech. Rep.-354, Colnputer Science Dept Technion, February 1985.

Google Scholar

Cited By

View all

Korman AKutten S(2013)Controller and estimator for dynamic networksInformation and Computation10.1016/j.ic.2012.10.018223(43-66)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.ic.2012.10.018
Emek YKorman A(2011)New bounds for the controller problemDistributed Computing10.1007/s00446-010-0119-z24:3-4(177-186)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1007/s00446-010-0119-z
Emek YKorman ARicha AGuerraoui R(2010)Efficient threshold detection in a distributed environmentProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835742(183-191)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835742
Show More Cited By

Recommendations

Face recognition based on global and local features
SAC '14: Proceedings of the 29th Annual ACM Symposium on Applied Computing

This paper presents an evaluation of different methods considering the usually problems in face recognition. We consider variations in illumination, facial expression and facial details to propose a new method combining global and local face image ...
Termination of non-simple rewrite systems
Decidability of Innermost Termination and Context-Sensitive Termination for Semi-Constructor Term Rewriting Systems

Yi and Sakai [Y. Wang and M. Sakai. Decidability of termination for semi-constructor trss, left-linear shallow trss and related systems. In the 17th International Conference on Rewriting Techniques and Applications, volume 4098 of Lecture Notes in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '87: Proceedings of the sixth annual ACM Symposium on Principles of distributed computing

December 1987

304 pages

ISBN:089791239X

DOI:10.1145/41840

Editor:
Fred B. Schneider

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC87

Sponsor:

PODC87: Sixth Annual ACM Symposium on Principles of Distributed Computing

August 10 - 12, 1987

British Columbia, Vancouver, Canada

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
325
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)8

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Korman AKutten S(2013)Controller and estimator for dynamic networksInformation and Computation10.1016/j.ic.2012.10.018223(43-66)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.ic.2012.10.018
Emek YKorman A(2011)New bounds for the controller problemDistributed Computing10.1007/s00446-010-0119-z24:3-4(177-186)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1007/s00446-010-0119-z
Emek YKorman ARicha AGuerraoui R(2010)Efficient threshold detection in a distributed environmentProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835742(183-191)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835742
Emek YKorman A(2009)New Bounds for the Controller ProblemDistributed Computing10.1007/978-3-642-04355-0_7(22-34)Online publication date: 2009
https://doi.org/10.1007/978-3-642-04355-0_7
Korman ABazzi RPatt-Shamir B(2008)Improved compact routing schemes for dynamic treesProceedings of the twenty-seventh ACM symposium on Principles of distributed computing10.1145/1400751.1400777(185-194)Online publication date: 18-Aug-2008
https://dl.acm.org/doi/10.1145/1400751.1400777
Korman AKutten SGupta IWattenhofer R(2007)Controller and estimator for dynamic networksProceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing10.1145/1281100.1281127(175-184)Online publication date: 12-Aug-2007
https://dl.acm.org/doi/10.1145/1281100.1281127
Lavallée ILavault C(2005)Spanning tree construction for nameless networksDistributed Algorithms10.1007/3-540-54099-7_4(41-56)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-54099-7_4
Yamashita MKameda T(2005)Electing a leader when processor identity numbers are not distinct (extended abstract)Distributed Algorithms10.1007/3-540-51687-5_52(303-314)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-51687-5_52
Xinli Wang Mayo J(2004)A general model for detecting distributed termination in dynamic systems18th International Parallel and Distributed Processing Symposium, 2004. Proceedings.10.1109/IPDPS.2004.1303025(84-90)Online publication date: 2004
https://doi.org/10.1109/IPDPS.2004.1303025
Perumalla KFujimoto RBagrodia RDeelman EWilsey P(2001)Virtual time synchronization over unreliable network transportProceedings of the fifteenth workshop on Parallel and distributed simulation10.5555/375658.375713(129-136)Online publication date: 15-May-2001
https://dl.acm.org/doi/10.5555/375658.375713
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Face recognition based on global and local features

Termination of non-simple rewrite systems

Decidability of Innermost Termination and Context-Sensitive Termination for Semi-Constructor Term Rewriting Systems