Distributed Algorithms. Nancy A. Lynch (1993) (Distributed Algorithms. Nancy A. Lynch (1993).pdf), страница 83

Shavit. Toward a non-atomic era: l-exclusion as a testcase. In Proceedings of 20th ACM Symposium on Theory of Computing, pages 78{92,May 1988.4] E.W. Dijkstra. Hierarchical ordering of sequential processes. Acta Informatica, pages115{138, 1971.D.4.3 Atomic Registers1] G.L. Peterson. Concurrent reading while writing.

ACM Transactions on ProgrammingLanguages and Systems, 5(1):46{55, 1983.2] L. Lamport. On interprocess communication. Distributed Computing, 1(1):77{85, 86{101, 1986. Digital Systems Research TM-8.3] Ambuj K. Singh, James H. Anderson, and Mohamed G. Gouda. The elusive atomicregister, June 1992. Submitted for publication.4] Bard Bloom. Constructing two-writer registers. IEEE Trans. Computers, 37(12):1506{1514, December 1988.5] P. Vitanyi and B. Awerbuch. Atomic shared register access by asynchronous hardware. In Proceedings 27th Annual IEEE Symposium on Theory of Computing, pages233{243, Toronto, Ontario, Canada, May 1986. Also, MIT/LCS/TM-314, Laboratory427for Computer Science, Massachusetts Institute of Technology, Cambridge, MA., 1986.Corrigenda in Proceedings of 28th Annual IEEE Symposium on Theory of Computing,page 487, 1987.6] R.

Schaer. On the correctness of atomic multi-writer registers. Bachelor's Thesis,June 1988, Massachusetts Institute Technology. Also, Technical Memo MIT/LCS/TM364, Lab for Computer Science, MIT, June 1988 and Revised Technical MemoMIT/LCS/TM-364, January 1989.7] Soma Chaudhuri and Jennifer Welch. Bounds on the costs of register implementations.Manuscript, 12/91. Also, Technical Report TR90-025, University of North Carolina atChapel Hill, June 1990.D.4.4 Snapshots1] Y. Afek, H.

Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshotsof shared memory. In Proceedings of the 9th Annual ACM Symposium on Principlesof Distributed Computing, pages 1{13, Quebec, Canada, August 1990. Also, TechnicalMemo MIT/LCS/TM-429, Laboratory for Computer Science, Massachusetts Instituteof Technology, Cambridge, MA, May 1990. To appear in Journal of the ACM.2] Cynthia Dwork, Maurice Herlihy, Serge Plotkin, and Orli Waarts. Time-lapse snapshots. In In Israel Symposium on Theory of Computing and Systems (ISTCS), 1992.Also, Stanford Technical Report STAN-CS-92-1423, April 1992, and Digital EquipmentCorporation Technical Report CRL 92/5.D.4.5 Timestamp Systems1] Amos Israeli and Ming Li. Bounded time-stamps. In Proceedings of the 28th IEEESymposium on Foundations of Computer Science, pages 371{382, October 1987.2] R.

Gawlick, N. Lynch, and N. Shavit. Concurrent time-stamping made simple. InIn Israel Symposium on Theory of Computing and Systems (ISTCS), pages 171{185.Springer-Verlag, May, 1992.3] Cynthia Dwork and Orli Waarts. Simple and ecient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible! In In Proceedingsof the 24th Annual ACM Symposium on Theory of Computing (STOC), pages 655{666, Victoria, B.C., Canada, May 1992.

Preliminary version appears in IBM ResearchReport RJ 8425, October 1991.428D.4.6 Consensus1] M. Loui and H. Abu-Amara. Memory requirements for agreement among unreliableasynchronous processes. Advances in Computing Research, 4:163{183, 1987.2] Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 11(1):124{149, January 1991.3] H. Attiya, N. Lynch, and N. Shavit. Are wait-free algorithms fast? Submitted forpublication. Earlier versions in MIT/LCS/TM-442 and Proceedings of the 31st AnnualIEEE Symposium on Foundations of Computer Science, 1:55-64, October, 1990.4] Karl Abrahamson.

On achieving consensus using a shared memory. In Proceedingsof the 7th Annual ACM Symposium on Principles of Distributed Computing, pages291{302, Toronto, Canada, August 1988.D.4.7 Shared Memory for Multiprocessors1] Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, c-28(9):690{691, September1979.2] Alan Jay Smith. Cache memories.

Computing Surveys, 14(3):473{529, September1982.3] Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness conditionfor concurrent objects. ACM Transactions on Programming Languages and Systems,12(3):463{492, July 1990.4] Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 11(1):124{149, January 1991.5] Yehuda Afek, Georey Brown, and Michael Merritt. Lazy caching. TOPLAS, October1992. To appear.

Also, a preliminary version appeared in SPAA'89.6] Phillip B. Gibbons, Michael Merritt, and Kourosh Gharachorloo. Proving sequentialconsistency of high-performance shared memories. AT&T Bell Laboratories, 11211910509-09TM and 11261-910509-6TM, May 1991.7] Phillip B. Gibbons and Michael Merritt. Specifying nonblocking shared memories.AT&T Bell Laboratories, BL011211-920528-07TM and BL011261-920528-17TM, May1992.4298] Hagit Attiya and Roy Friedman.

A correctness condition for high-performance multiprocessors. Unpublished Manuscript, November 1991.9] Richard J. Lipton and Jonathan S. Sandberg. PRAM: A scalable shared memory.Department of Computer Science, Princeton University, CS-TR-180-88, September1988.10] Mustaque Ahamad, James E.

Burns, Phillip W. Hutto, and Gil Neiger. Causal memory.College of Computing, Georgia Institute of Technology, GIT-CC-91/42, September1991.11] Hagit Attiya and Jennifer Welch. Sequential consistency versus linearizability. InProceedings of the 3rd ACM Symp. on Parallel Algorithms and Architectures (SPAA3),1991. Also, Technion- Israel Institute Technology, Dept.

of C.S., TR 694.D.5 Asynchronous Message-Passage SystemsD.5.1 Computing in Static NetworksRings1] G. LeLann. Distributed systems, towards a formal approach. In IFIP Congress, pages155{160, Toronto, 1977.2] E. Chang and R. Roberts. An improved algorithm for decentralized extrema-ndingin circular congurations of processes. Communications of the ACM, 22:281{283, May1979.3] D.

Hirschberg and J. Sinclair. Decentralized extrema-nding in circular conguarationsof processes. Communications of the ACM, 23:627{628, November 1980.4] G.L. Peterson. An O(n log n) unidirectional distributed algorithm for the circularextrema problem. ACM Transactions on Programming Languages and Systems, 4:758{762, October 1982.5] D. Dolev, M. Klawe, and M. Rodeh.

An O(n log n) unidirectional distributed algorithmfor extrema nding in a circle. Research Report RJ3185, IBM, July 1981. J. Algorithms,3:245{260, 1982.6] J. Burns. A formal model for message passing systems. Technical Report TR-91,Computer Science Dept., Indiana University, May 1980.4307] K. Abrahamson, A. Adler, L. Higham, and D. Kirkpatrick. Tight lower bounds forprobabilistic solitude verication on anonymous rings. Submitted for publication.Complete Graphs1] E. Korach, S.

Moran, and S. Zaks. Tight lower and upper bounds for some distributedalgorithms for a complete network of processors. In In Proceedings of 3rd ACM Symposium on Principles of Distributed Computing, pages 199{207, 1984.2] Y. Afek and E. Gafni. Time and message bounds for election in synchronous andasynchronous complete networks. In Proceedings of 4th ACM Symposium on Principlesof Distributed Computing, pages 186{195, Minaki, Ontario, August 1985.General Networks1] D.

Angluin. Local and global properties in networks of processors. In Proceedings of12th ACM Symposium on Theory of Computing, pages 82{93, 1980.2] R. Gallager, P. Humblet, and P. Spira. A distributed algorithm for minimum-weightspanning trees. ACM Transactions on Programming Languages and Systems, 5(1):66{77, January 1983.3] P. Humblet. A distributed algorithm for minimum weight directed spanning trees.IEEE Transactions on Computers, COM-31(6):756{762, 1983.

MIT-LIDS-P-1149.4] Baruch Awerbuch and David Peleg. Sparse partitions. In Proceedings of the 31st IEEESymposium on Foundations of Computer Science, pages 503{513, St. Louis, Missouri,October 1990.D.5.2 Network Synchronization1] L.

Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 27(1):558{565, July 1978.2] J. M. H%elary and M. Raynal. Synchronization and Control of Distributed Systems andPrograms. John Wiley & Sons, 1990.3] B. Awerbuch. Complexity of network synchronization. J. ACM, 32(4):804{823, October 1985. Also, Technical Memo MIT/LCS/TM-268, Laboratory for Computer Science,Massachusetts Institute Technology, Cambridge, MA, January 1985.4314] B. Awerbuch and M. Sipser.

Dynamic networks are as fast as static networks. InProceedings of the 29th IEEE Symposium on Foundations of Computer Science. IEEE,October 1988.5] E. Arjomandi, M. Fischer, and N. Lynch. Eciency of synchronous versus asynchronous distributed systems. Journal of the ACM, 30(3):449{456, July 1983.6] Leslie Lamport. Using time instead of timeout for fault-tolerant distributed systems.toplas, 6(2):254{280, apr 1984.7] Leslie Lamport.

The part-time parliament. Technical Memo 49, Digital Systems Research Center, September 1989.8] J.L. Welch. Simulating synchronous processors. Information and Computation,74(2):159{171, August 1987.D.5.3 Simulating Asynchronous Shared Memory1] Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in messagepassing systems. In Proceedings of the 9th Annual ACM Symposium on Principles ofDistributed Computing, pages 363{376, 1990. Revised version to appear in J. ACM.D.5.4 Resource Allocation1] M.

Raynal. Algorithms for Mutual Exclusion. M.I.T. Press, 1986.2] K. Chandy and J. Misra. The drinking philosophers problem. ACM Transactions onProgramming Languages and Systems, 6(4):632{646, October 1984.3] N. Lynch. Upper bounds for static resource allocation in a distributed system. JournalOf Computer And Systems Sciences, 23(2):254{278, October 1981.4] M. Rabin and D. Lehmann. On the advantages of free choice: a symmetric and fullydistributed solution to the dining philosophers problem. In Proceedings of 8th ACMSymposium on Principles of Programming Languages, pages 133{138, 1981.5] Baruch Awerbuch and Michael Saks.

A dining philosophers algorithm with polynomialresponse time. In Proceedings of the 31st IEEE Symp. on Foundations of ComputerScience, pages 65{75, St. Louis, Missouri, October 1990.6] Jennifer Welch and Nancy Lynch. A modular drinking philosophers algorithm, July1992. Earlier version appeared as MIT/LCS/TM-417.432D.5.5 Delecting Stable PropertiesTermination Detection1] E. Dijkstra and C. Scholten. Termination detection for diusing computations. Information Processing Letters, 11(1), August 1980.2] N. Francez and N.