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

Shavit. A new approach to detection of locally indicative stability. In Proceedings of the 13th International Colloquium on Automata Languages andProgramming (ICALP), pages 344{358, Rennes, France, July 1986. Springer-Verlag.Global Snapshots1] K. Chandy and L. Lamport. Distributed snapshots: determining global states ofdistributed systems. ACM Transactions on Computer Systems, 3(1):63{75, February1985.2] M. Fischer, N.

Grieth, and N. Lynch. Global states of a distributed system. IEEETransactions on Software Engineering, SE-8(3):198{202, May 1982. Also, in Proceedings of IEEE Symposium on Reliability in Distributed Software and Database Systems,Pittsburgh, PA, July 1981, 33-38.D.5.6 Deadlock Detection1] D. Menasce and R. Muntz. Locking and deadlock detection in distributed databases.IEEE Transactions on Software Engineering, SE-5(3):195{202, May 1979.2] V. Gligor and S.

Shattuck. On deadlock detection in distributed systems. IEEETransactions on Software Engineering, SE-6(5):435{439, September 1980.3] R. Obermarck. Distributed deadlock detection algorithm. ACM Transactions onDatabase Systems, 7(2):187{208, June 1982.4] G. Ho and C. Ramamoorthy. Protocols for deadlock detection in distributed databasesystems. IEEE Transactions on Software Engineering, SE-8(6):554{557, November1982.5] K. Chandy, J. Misra, and L. Haas. Distributed deadlock detection. ACM Transactionson Programming Languages and Systems, 1(2):144{156, May 1983.6] G. Bracha and S.

Toueg. A distributed algorithm for generalized deadlock detection.Distributed Computing, 2:127{138, 1987.4337] D. Mitchell and M. Merritt. A distributed algorithm for deadlock detection and resolution. In Proceedings of 3rd ACM Symposium on Principles of Distributed Computing,pages 282{284, Vancouver, B.C., Canada, August 1984.D.5.7 Consensus1] M.

Fischer, N. Lynch, and M. Paterson. Impossibility of distributed consensus withone family faulty process. Journal of the ACM, 32(2):374{382, April 1985.2] S. Moran and Y Wolfstahl. Extended impossibility results for asynchronous completenetworks. Information Processing Letters, 26:145{151, 1987.3] M.

Bridgland and R. Watro. Fault-tolerant decision making in totally asynchronousdistributed systems. In Proceedings of 6th ACM Symposium on Principles of Distributed Computing, pages 52{63, August 1987. Revision in progress.4] Ofer Biran, Shlomo Moran, and Shmuel Zaks. A combinatorial characterization of thedistributed 1-solvable tasks. Journal of Algorithms, 11(3):420{440, September 1990.Earlier version in Proceedings of 7th ACM Symposium on Principles of DistributedComputing, pages 263-275, August 1988.5] Gadi Taubenfeld, Shmuel Katz, and Shlomo Moran. Impossibility results in the presence of multiple faulty processes. In C.E.

Veni Madhavan, editor, Proc. of the 9th FCTTCS Conference, volume 405 of Lecture Notes in Computer Science, pages 109{120,Bangalore, India, 1989. Springer Verlag. To appear in Information and Computation.6] Gadi Taubenfeld. On the nonexistence of resilient consensus protocols. InformationProcessing Letters, 37:285{289, March 1991.7] H. Attiya, A. Bar-Noy, D. Dolev, D. Peleg, and R.

Reischuk. Renaming in an asynchronous environment. J. ACM, 37(3), July 1990.8] D. Dolev, C. Dwork, and L. Stockmeyer. On the minimal synchronism needed fordistributed consensus. Journal of the ACM, 34(1):77{97, 1987.9] Tushar D. Chandra and Sam Toueg. Unreliable failure detectors for asynchronoussystems. In Proceedings 10th ACM Symposium on Principles of Distributed Computing,pages 257{272, Montreal, Canada, August 1991. Also, Cornell University, Departmentof Computer Science, Ithaca, New York TR 91-1225.43410] Tushar D. Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detectorfor solving consensus.

In Proceedings 11th ACM Symposium on Principles of Distributed Computing, pages 147{158, Vancouver, Canada, August 1992. Also, CornellUniversity, Department of Computer Science, Ithaca, New York TR 92-1293.D.5.8 Datalink1] A. Aho, J. Ullman, A. Wyner, and M. Yannakakis. Bounds on the size and transmission rate of communication protocols. Computers and Mathematics with Applications,8(3):205{214, 1982.2] J.

Y. Halpern and L. D. Zuck. A little knowledge goes a long way: Simple knowledgebased derivations and correctness proofs for a family of protocols. J. ACM, 39(3):449{478, July 1992. Earlier version exists in Proceedings of the 6th Annual ACM Symposiumon Principles of Distributed Computing, August, 1987.3] N. Lynch, Y. Mansour, and A. Fekete.

The data link layer: Two impossibility results. InProceedings of 7th ACM Symposium on Principles of Distributed Computation, pages149{170, Toronto, Canada, August 1988. Also, Technical Memo MIT/LCS/TM-355,May 1988.4] Y. Afek, H. Attiya, A. Fekete, M. Fischer, N. Lynch, Y. Mansour, D. Wang,and L.

Zuck. Reliable communication over unreliable channels. Technical MemoMIT/LCS/TM-447, Laboratory for Computer Science, Massachusetts Institute Technology, Cambridge, MA, 02139, October 1992.5] A. Fekete, N. Lynch, Y. Mansour, and J Spinelli. The data link layer: The impossibility of implementation in face of crashes.

Technical Memo MIT/LCS/TM-355.b,Massachusetts Institute of Technology, Laboratory for Computer Science, August 1989.Submitted for publication.6] A. Fekete and N. Lynch. The need for headers: an impossibility result for communication over unreliable channels. In G. Goos and J. Hartmanis, editors, CONCUR'90, Theories of Concurrency: Unication and Extension, volume 458 of Lecture Notesin Computer Science, pages 199{216. Springer-Verlag, August 1990. Also, TechnicalMemo MIT/LCS/TM-428, May, 1990.7] Y. Afek, H.

Attiya, A. Fekete, M. Fischer, N. Lynch, Y. Mansour, D. Wang, andL. Zuck. Reliable communication over an unreliable channel, 1991. Submitted forpublication.4358] Da-Wei Wang and Lenore Zuck. Tight bounds for the sequence transmission problem. In Proceedings of the 8th Annual ACM Symposium on Principles of DistributedComputing, pages 73{83, August 1989.9] Ewan Tempero and Richard Ladner. Tight bounds for weakly bounded protocols. InProceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing, pages 205{212, Quebec, Canada, August 1990.10] Ewan Tempero and Richard Ladner. Recoverable sequence transmission protocols,June 1991. Manuscript.D.5.9 Special-Purpose Network Building Blocks1] J.

M. H%elary and M. Raynal. Synchronization and Control of Distributed Systems andPrograms. John Wiley & Sons, 1990.2] B. Awerbuch, O. Goldreich, D. Peleg, and R. Vainish. A tradeo between informationand communication in broadcast protocols. J. ACM, 37(2):238{256, April 1990.3] Yehuda Afek, Eli Gafni, and Adi Ros(en. The slide mechanism with applications indynamic networks. In Proceedings of the Eleventh Annual Symp.

on Principles ofDistributed Computing, pages 35{46, Vancouver, British Columbia, Canada, August1992.D.5.10 Self-Stabilization1] Edsger W. Dijkstra. Self-stabilizing systems in spite of distributed control. Communication of the ACM, 17(11):643{644, November 1974.2] Edsger W. Dijksra. A Belated Proof of Self-Stabilization.

Distributed Computing,1(1):5-6, January, 1986.3] Geoery M. Brown and Mohamed G. Gouda and Chuan-Lin Wu. Token Systems thatSelf-Stabilize. IEEE Trans. Computers, 38(6):845-852, June, 1989.4] James E. Burns and Jan Pachl. Uniform Self-Stabilizing Ring. ACM Trans. Prog.Lang. and Syst., 11(2):330-344, April, 1989.5] Shmuel Katz and Kenneth J. Perry. Self-stabilizing extensions for message-passingsystems, March 1992.

To appear in Distrib. Comput. Also, earlier version in Proceedings436of the 9th Annual ACM Symposium on Principles of Distributed Computing, August,1990.6] Yehuda Afek and Georey Brown. Self-stabilization of the alternating bit protocol. InProceedings of the 8th IEEE Symposium on Reliable Distributed Systems, pages 80{83,1989.7] Shlomi Dolev, Amos Israeli, and Shlomo Moran. Resource bounds for self stabilizingmessage driven protocols. In Proceedings of the 10th Annual ACM Symposium onPrinciples of Distributed Computing, August 1991.8] Baruch Awerbuch and Boaz Patt-Shamir and George Varghese Self-Stabilization byLocal Checking and Correction.

Proceedings of the 32nd Annual IEEE Symposium onFoundations of Computer Science, 268-277, October, 1991.9] Varghese G. Dealing with Failure in Distributed Systems. PhD thesis, MIT Dept. ofElectrical Engineering and Computer Science, 1992. In progress.D.5.11 Knowledge1] K. Chandy and J. Misra. How processes learn. Distributed Computing, 1(1):40{52,1986.D.6 Timing-Based SystemsD.6.1 Resource Allocation1] H. Attiya and N.

Lynch. Time bounds for real-time process control in the presence oftiming uncertainty. Inf. Comput., 1993. To appear.2] N. Lynch and N. Shavit. Timing-based mutual exclusion. In Proceedings of the 13thIEEE Real-Time Systems Symposium, Phoenix, Arizona, December 1992. To appear.3] Rajeev Alur and Gadi Taubenfeld. Results about fast mutual exclusion. In Proceedingsof the 13th IEEE Real-Time Systems Symposium, Phoenix, Arizona, December 1992.To appear.D.6.2 Shared Memory for Multiprocessors1] M. Mavronicolas. Timing-based distributed computation: Algorithms and impossibility results. Harvard University, Cambridge, MA, TR-13-92.437D.6.3 Consensus1] C.

Dwork, N. Lynch, and L. Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288{323, 1988.2] Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds on thetime to reach agreement in the presence of timing uncertainty. J.ACM, 1992. Toappear. Also, a preliminary version appeared in 23rd STOC, 1991.3] S. Ponzio.

The real-time cost of timing uncertainty: Consensus and failure detection.Master's thesis, MIT Dept. of Electrical Engineering and Computer Science, June 1991.Also, MIT/LCS/TR 518.4] Stephen Ponzio. Consensus in the presence of timing uncertainty: Omission and byzantine failures. In 10th ACM Symposium on Principles of Distributed Computing, pages125{138, Montreal, Canada, August 1991.D.6.4 Communication1] Da-Wei Wang and Lenore D. Zuck.

Real-time STP. In Proceedings of Tenth ACMSymp. on Principles of Distributed Computing, August 1991. This is also TechnicalReport YALE/DCS/TR{856.2] S. Ponzio. Bounds on the time to detect failures using bounded-capacity message links.In Proceedings of the 13th Real-time Systems Symposium, Phoenix, Arizona, December1992. To appear.3] S. Ponzio. The real-time cost of timing uncertainty: Consensus and failure detection.Master's thesis, MIT Dept. of Electrical Engineering and Computer Science, June 1991.Also, MIT/LCS/TR 518.4] Amir Herzberg and Shay Kutten. Fast isolation of arbitrary forwarding-faults.