The effects of link failures on computations in asynchronous rings

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The effects of link failures on computations in asynchronous rings

Full text

Pdf (638 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the fifth annual ACM symposium on Principles of distributed computing table of contents

Calgary, Alberta, Canada

Pages: 174 - 185

Year of Publication: 1986

ISBN:0-89791-198-9

Authors

Oded Goldreich	Lab. for Computer Sc., MIT, Cambridge and Computer Science Dept., Teehnion, Haifa, Israel
Liuba Shrira	Dept. of Computer Sc., Technion, Haifa, Israel

Sponsor

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 6, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/10590.10605 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ASW	Chagit Attiya , Marc Snir , Manfred Warmuth, Computing on an anonymous ring, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.196-203, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323614]
	AE	Baruch Awerbuch , Shimon Even, Efficient and reliable broadcast is achievable in an eventually connected network(Extended Abstract), Proceedings of the third annual ACM symposium on Principles of distributed computing, p.278-281, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806754]
	B	Burns, J.E., "A Formal Model for Message Passing Systems", TR-91, Indiana University, (1980).
	CR	Ernest Chang , Rosemary Roberts, An improved algorithm for decentralized extrema-finding in circular configurations of processes, Communications of the ACM, v.22 n.5, p.281-283, May 1979 [doi>10.1145/359104.359108]
	DKR	Dolev, D., Klawe, M., and Rodeh, M., "An O(nlogn) Unidirectional Distributed Algorithm for Extremafinding in a Circle", Jour. of Algorithms, Vol. 3, 1982, pp. 245-250.
	Fis	Fischer, M.J., "The Consensus Problem in Unreliable Distributed Systems (a brief survey)", YaleU/DCS/RR-273, (1983).
	F	Randolph Franklin, On an improved algorithm for decentralized extrema finding in circular configurations of processors, Communications of the ACM, v.25 n.5, p.336-337, May 1982 [doi>10.1145/358506.358517]
	FL	Greg N. Frederickson , Nancy A. Lynch, The impact of synchronous communication on the problem of electing a leader in a ring, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.493-503, December 1984 [doi>10.1145/800057.808719]
	GS1	Goldreich, O., and Shrira, L., "Consultation in the Presence of Faults: Two lower Bounds" TR-355, Comp. Sc. Dept., Technion, Israel, (1985).
	GS2	Goldreich, O., and Shrira, L., "Electing a Leader in the Prescirce of Faults: a Ring us a Special Case", TR-354, Comp. Sc. Dept., Technion, Israel, (1985). To appear in ACTA Informatica.
	HS	D. S. Hirschberg , J. B. Sinclair, Decentralized extrema-finding in circular configurations of processors, Communications of the ACM, v.23 n.11, p.627-628, Nov. 1980 [doi>10.1145/359024.359029]
	IR1	Itai, A., and Rodeh, M., "Symmetry Breaking in a Distributed Environment", Proc. of the 22nd IEEE Symp. on Foundation Of Computer Science, 1981, pp. 150-157.
	IR2	Itai, A., and Rodeh, M., "The Multi-Tree Approach to Reliability in Distributed Networks", Proc. of the 25th IEEE Symp. on Foundation Of Computer Science, 1984, pp. 137-147.
	L	LeLann, G., "Distributed Systems Towards a Formal Approach", Information Processing 77, Gilchrist B. Ed., North Holland, Amsterdam, 1977, pp. 155-160.
	LF	Lynch, N.A., and Fischer, M.J., "On Describing the Behavior and Implementation of Distributed Systems", Theoretical Comp. Sc., Vol. 13, 1981, pp. 17-43.
	M	Michael Merritt, Elections in the presence of faults, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.134-142, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806741]
	P	Gary L. Peterson, An O(nlog n) Unidirectional Algorithm for the Circular Extrema Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.758-762, Oct. 1982 [doi>10.1145/69622.357194]
	SR	Shrira, L., and Rodeh, M., "Methodological Construction of Reliable Distributed Algorithms", TR-361, Comp. Sc. Dept., Technion, Israel, 1985.
	V	Paul M.B. Vitányi, Distributed elections in an archimedean ring of processors, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.542-547, December 1984 [doi>10.1145/800057.808725]

CITED BY 9

	Baruch Awerbuch , Alan Baratz , David Peleg, Cost-sensitive analysis of communication protocols, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.177-187, August 22-24, 1990, Quebec City, Quebec, Canada
	N. Lynch, A hundred impossibility proofs for distributed computing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.1-28, June 1989, Edmonton, Alberta, Canada
	Yehuda Afek , Michael Saks, Detecting global termination conditions in the face of uncertainty, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.109-124, August 10-12, 1987, Vancouver, British Columbia, Canada
	Baruch Awerbuch , Oded Goldreich , Ronen Vainish , David Peleg, A trade-off between information and communication in broadcast protocols, Journal of the ACM (JACM), v.37 n.2, p.238-256, April 1990
	H. Abu-Amara , J. Lokre, Election in Asynchronous Complete Networks with Intermittent Link Failures, IEEE Transactions on Computers, v.43 n.7, p.778-788, July 1994
	Gurdip Singh, Leader Election in the Presence of Link Failures, IEEE Transactions on Parallel and Distributed Systems, v.7 n.3, p.231-236, March 1996
	M. Y. Chan , F. Y. L. Chin, Optimal Resilient Distributed Algorithms for Ring Election, IEEE Transactions on Parallel and Distributed Systems, v.4 n.4, p.475-480, April 1993
	Hosame H. Abu-Amara, Fault-Tolerant Distributed Algorithm for Election in Complete Networks, IEEE Transactions on Computers, v.37 n.4, p.449-453, April 1988
	Y. Afek , D. Hendler, On the complexity of global computation in the presence of link failures: the general case, Distributed Computing, v.8 n.3, p.115-120, March 1995