Sharing memory robustly in message-passing systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sharing memory robustly in message-passing systems

Full text

Pdf (1.34 MB)

Source

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

Quebec City, Quebec, Canada

Pages: 363 - 375

Year of Publication: 1990

ISBN:0-89791-404-X

Authors

Hagit Attiya	Laboratory for Computer Science, MIT, Cambridge, MA
Amotz Bar-Noy	IBM T. J. Watson Research Center, P. O. Box 704, Yorktown Heights, NY
Danny Dolev	IBM Almaden Research Center, 650 Harry Road, San Jose, CA

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 18, Citation Count: 15

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/93385.93441 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.

	1	Karl Abrahamson, On achieving consensus using a shared memory, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.291-302, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62594]
	2	Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93394]
	3	Y. Afek, B. Awerbuch and E. Gafni, Applying Static Network Protocols to Dynamic Networks, Proc. 28th IEEE Syrup. on Foundations of Comp. Science, pp. 358-369, 1987.
	4	Y. Afek, D. Dolev, E. Gafni, M. Merritt and N. Shavit, A Bounded First-In First- Enabled-Solution to the t-Exclusion Problem, manuscript.
	5	Eli Gafni , Yehuda Afek, End-to-end communication in unreliable networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.131-148, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62570]
	6	Y. Afek and E. Gafni, Bootstrap Network Re~ynchronization: An Efficient Technique for End-to- End Communication, manuscript.
	7	James Anderson, Composite registers, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.15-29, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93396]
	8	James Aspnes , M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms, v.11 n.3, p.441-461, Sep. 1990 [doi>10.1016/0196-6774(90)90021-6]
	9	J. Aspnes , M. Herlihy, Wait-free data structures in the asynchronous PRAM model, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.340-349, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97701]
	10	H. Attiya, A. B~-Noy, D. Dolev, D. Koller, D. Peleg and R. Reischulc, Achievable Cases in an Asynchronous Environment, Proc. 28th IEEE Syrup. on Foundations of Comp. Science, pp. 337-346, 1987.
	11	H. Attiya , D. Dolev , N. Shavit, Bounded polynomial randomized consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.281-293, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73001]
	12	B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States [doi>10.1145/28395.28421]
	13	B. Awerbuch, Y. Mansour and N. Shavit, Polynomial End-To-End Communication, Proc. 30th IEEE Syrup. on Foundations of Comp. Science, pp. 358-363, 1989.
	14	A. Bas-Noy , D. Dolev, Shared-memory vs. message-passing in an asynchronous distributed environment, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.307-318, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73003]
	15	Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
	16	J. E. Burns , G. L. Peterson, The ambiguity of choosing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.145-157, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72991]
	17	Benny Chor , Amos Israeli , Ming Li, On processor coordination using asynchronous hardware, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.86-97, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41848]
	18	Benny Chor , Michael Merritt , David B. Shmoys, Simple constant-time consensus protocols in realistic failure models (extended abstract), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.152-162, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323610]
	19	B. Chor and L. Moscovici, Solvability in Asynchronous Environments, Proc. 30th IEEE Syrup. on Foundations of Comp. Science, pp. 422-427, 1989.
	20	E. W. Dijkstra and C. S. Scholten, Termination Detection for Diffusing Computations, Information Processing Letters, Vol. 1, No. 1, pp. 1-4, August 1980.
	21	Danny Dolev , Eli Gafni , Nir Shavit, Toward a non-atomic era: l-exclusion as a test case, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.78-92, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62220]
	22	D. Dolev and N. Shavit, unpublished manuscript, July 1987. Appears in {13}.
	23	D. Dolev , N. Shavit, Bounded concurrrent time-stamp systems are constructible, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.454-466, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73051]
	24	C. Dwork, D. Shmoys and L. Stockmeyer, Flipping Persuasively in Constant Expected Time, Proc. 27th IEEE Syrup. on Foundations of Computer Science, pp. 222-232, 1986.
	25	P. Feldman, private communication.
	26	J.A. Feldman and A. Nigam, A Model and Proof Technique for Message-Based Systems, SIAM J. on Computing, Vol. 9, No. 4 (November 1980), pp. 768-784.
	27	S. G. Finn, Resynch Procedures and a Fail-Safe Network Protocol, IEEE Trans. Comm., COM- 27 pp. 840-845, 1979.
	28	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
	29	Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62593]
	30	A. Israeli and M. Li, Bounded Time-stamps, Proc. 28~h IEEE Syrup. on Foundations of Comp. Science, pp. 371-382, 1987.
	31	L. Lamport, On Interproeess Communication, Part I and iI, Distributed Computing, Vol. 1, No. 2, pp. 77-101, 1986.
	32	Ming Li , Paul M. B. Vitányi, How to Share Concurrent Asynchronous Wait-Free Varaibles (Preliminary Version), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.488-505, July 11-15, 1989
	33	G. L. Peterson and James E. Burns, Concurrent Beading While Writing II: The Multi-writer Case, Proc. 28th IEEE Syrup. on Foundations of Comp. Science, pp. 383-392, 1987.
	34	U. Vishkin, A Distributed Orientation Algorithm, IEEE Trans. on Information Theory, June 1983.
	35	P. Vitanyi and B. Awerbuch, Atomic Shared Register Access by Asynchronous Hardware, Proc. 27th IEEE Syrup. on Foundations of Comp. Science, pp. 233-243, 1986.

CITED BY 15

	Maurice Herlihy , Nir Shavit, A simple constructive computability theorem for wait-free computation, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.243-252, May 23-25, 1994, Montreal, Quebec, Canada
	Cynthia Dwork , Joseph Y. Halpern , Orli Waarts, Performing work efficiently in the presence of faults, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.91-102, August 10-12, 1992, Vancouver, British Columbia, Canada
	Kleoni Ioannidou, Transformations of self-stabilizing algorithms, Journal of High Speed Networks, v.14 n.1, p.85-105, January 2005
	Elizabeth Borowsky , Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.91-100, May 16-18, 1993, San Diego, California, United States
	Yehuda Afek , Eli Gafni, Bootstrap network resynchronization (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.295-307, August 19-21, 1991, Montreal, Quebec, Canada
	Benny Chor , Lee-Bath Nelson, Resiliency of interactive distributed tasks (extended abstracts), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.37-49, August 19-21, 1991, Montreal, Quebec, Canada
	Maurice Herlihy , Nir Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.111-120, May 16-18, 1993, San Diego, California, United States
	Benny Chor , Lee-Bath Nelson, Resilience of general interactive tasks, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.173-182, August 14-17, 1994, Los Angeles, California, United States
	Hagit Attiya , Nancy Lynch , Nir Shavit, Are wait-free algorithms fast?, Journal of the ACM (JACM), v.41 n.4, p.725-763, July 1994
	Gunnar Hoest , Nir Shavit, Towards a topological characterization of asynchronous complexity, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.199-208, August 21-24, 1997, Santa Barbara, California, United States
	Hagit Attiya , Ophir Rachman, Atomic snapshots in O(n log n) operations, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.29-40, August 15-18, 1993, Ithaca, New York, United States
	John Turek , Dennis Shasha, The Many Faces of Consensus in Distributed Systems, Computer, v.25 n.6, p.8-17, June 1992
	Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993
	Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada
	Danny Dolev, Century papers at the first quarter-century milestone, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, p.3-4, July 23-26, 2006, Denver, Colorado, USA