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

A theory of timed automata. To appear in TheoreticalComputer Science.4] F.W. Vaandrager and N.A. Lynch. Action transducers and timed automata. In Proceedings of CONCUR '92, 3rd International Conference on Concurrency Theory, Lecture Notes in Computer Science, Stony Brook, NY, August 1992. Springer Verlag. Toappear.5] N. Lynch and H. Attiya. Using mappings to prove timing properties. Distrib.

Comput.,6(2), 1992. To appear.6] Thomas A. Henzinger, Zohar Manna, and Amir Pnueli. Temporal proof methodologiesfor real-time systems, September 1991. Submitted for publication. An abbreviatedversion in HMP91].7] T. A. Henzinger, Z. Manna, and A. Pnueli. Temporal proof methodologies for realtime systems. In Proc. ACM Symp.

on Principles of Programming Languages, pages353{366, January 1991.D.2.8 Algebra1] C.A.R. Hoare. Communicating Sequential Processes. Prentice-Hall, 1984.2] R. Milner. Communication and Concurrency. Prentice-Hall International, EnglewoodClis, 1989.D.3 Synchronous Message-Passing SystemsD.3.1 Computing in a Ring1] 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.4224] 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] G. Frederickson and N. Lynch.

Electing a leader in a synchronous ring. Journal of theACM, 34(1):98{115, January 1987. Also, MIT/LCS/TM-277, July 1985.6] H. Attiya, M. Snir, and M. Warmuth. Computing in an anonymous ring. Journal ofthe ACM, 35(4):845{876, October 1988.D.3.2 Network Protocols1] Baruch Awerbuch. Course notes.2] B. Awerbuch. Reducing complexities of distributed maximum ow and breadth-rstsearch algorithms by means of network synchronization. Networks, 15:425{437, 1985.3] Michael Luby.

A Simple Parallel Algorithm for the Maximal Independent Set Problem.SIAM J. Comput., 15(4):1036{1053, November, 1985.D.3.3 ConsensusBasic Results1] J. Gray. Notes on data base operating systems. Technical Report IBM ReportRJ2183(30001), IBM, February 1978. (Also in Operating Systems: An AdvancedCourse, Springer-Verlag Lecture Notes in Computer Science #60.).2] G. Varghese and N.

Lynch. A Tradeo Between Safety and Liveness for RandomizedCoordinated Attack Protocols. 11th Symposium on Principles of Distributed Systems,Vancouver, B.C., Canada, 241{250, August, 1992.3] L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACMTransactions on Programming Languages and Systems, 4(3):382{401, July 1982.4] M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults.Journal of the ACM, 27(2):228{234, April 1980.5] Amotz Bar-Noy, Danny Dolev, Cynthia Dwork, and Raymond Strong. Shifting gears:Changing algorithms on the y to expedite Byzantine agreement. Information andComputation, 97(2):205{233, 1992.4236] D.

Dolev and H. Strong. Authenticated algorithms for Byzantine agreement. SIAM J.Computing, 12(4):656{666, November 1983.7] T. Srikanth and S. Toueg. Simulating authenticated broadcasts to derive simple faulttolerant algorithms. Distributed Computing, 2:80{94, 1987.8] R. Turpin and B. Coan. Extending binary Byzantine agreement to multivalued Byzantine agreement.

Information Processing Letters, 18(2):73{76, 1984. Also, TechnicalReport MIT/LCS/TR-315, Laboratory for Computer Science, Massachusetts InstituteTechnology, Cambridge, MA, April 1984. Also, revised in B. Coan, Achieving consensusin fault-tolerant distributed computing systems, Ph.D. thesis, Department of ElectricalEngineering and Computer Science, Massachusetts Institute of Technology,1987.Number of Processes1] D. Dolev. The Byzantine generals strike again.

Journal of Algorithms, 3:14{30, 1982.2] M. Fischer, N. Lynch, and M. Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1:26{39, 1986.3] L. Lamport. The weak Byzantine generals problem. Journal of the ACM, 30(3):669{676, 1983.Time Bounds1] M.

Fischer and N. Lynch. A lower bound for the time to assure interactive consistency.Information Processing Letters, 14(4):183{186, June 1982.2] C. Dwork and Y. Moses. Knowledge and common knowledge in a Byzantine environment: Crash failures.

Information and Computation, 88(2):156{186, October, 1990.3] Y. Moses and M. Tuttle. Programming simultaneous actions using common knowledge.Algorithmica, 3:249{259, 1988.Communication1] B.A. Coan. Achieving Consensus in Fault-Tolerant Distributed Computer Systems:Protocols, Lower Bounds, and Simulations. PhD thesis, Massachusetts Institute ofTechnology, June 1987.4242] Yoram Moses and O. Waarts. Coordinated traversal: (t+1)-round Byzantine agreementin polynomial time. In Proceedings of 29th Symposium on Foundations of ComputerScience, pages 246{255, October 1988. To appear in the special issue of the Journal of Algorithms dedicated to selected papers from the 29th IEEE Symposium onFoundations of Computer Science.

Extended version available as Waarts' M.Sc. thesis,Weizmann Institute, August 1988.3] Piotr Berman and Juan Garay. Cloture voting: n/4-resilient distributed consensus int+1 rounds. To appear in Mathematical Systems Theory|An International Journalon Mathematical Computing Theory, special issue dedicated to distributed agreement.Preliminary version appeared in Proc.

30th Symp. on Foundations of Computer Science, pp. 410-415, 1989.Approximate Agreement1] D. Dolev, N. Lynch, S. Pinter, E. Stark, and W. Weihl. Reaching approximate agreement in the presence of faults. Journal of the ACM, 33(3):449{516, 1986.Firing Squad1] J.E. Burns and N.A Lynch. The Byzantine ring squad problem.

Advances in Computing Research, 4:147{161, 1987.2] B. Coan, D. Dolev, C. Dwork, and L. Stockmeyer. The distributed ring squad problem. In Proceedings of the 17th ACM Symposium on Theory of Computing, pages335{345, May 1985.Commit1] C.

Dwork and D. Skeen. The inherent cost of nonblocking commitment. In Proceedingsof the 2nd Annual ACM Symposium on Principles of Distributed Computing, pages 1{11, August 1983.2] P. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery inDatabase Systems. Addison-Wesley, 1986.3] B. A. Coan and J. L. Welch. Transaction commit in a realistic timing model. DistributedComputing, 4:87{103, 1990.425The Knowledge Approach1] J.Y. Halpern and Y.

Moses. Knowledge and common knowledge in a distributedenvironment. In Proceedings of 3rd ACM Symposium on Principles of DistributedComputing, pages 50{61, 1984. Revised as IBM Research Report, IBM-RJ-4421.2] C. Dwork and Y. Moses. Knowledge and common knowledge in a Byzantine environment: Crash failures. Information and Computation, 88(2):156{186, October, 1990.D.4 Asynchronous Shared Memory SystemsD.4.1 Mutual Exclusion1] M. Raynal.

Algorithms for Mutual Exclusion. M.I.T. Press, 1986.2] E.W. Dijkstra. Solution of a problem in concurrent programming control. Communications of the ACM, 8(9):569, September 1965.3] D.E. Knuth. Additional comments on a problem in concurrent programming control.Communications of the ACM, 9(5):321{322, 1966.4] J.G. DeBruijn. Additional comments on a problem in concurrent programming control.Communications of the ACM, 10(3):137{138, 1967.5] M. Eisenberg and M. McGuire. Further comments on Dijkstra's concurrent programming control.

Communications of the ACM, 15(11):999, 1972.6] James E. Burns and Nancy A. Lynch. Bounds on shared memory for mutual exclusion.To appear in Info. Comput.7] L. Lamport. A new solution of Dijkstra's concurrent programming problem. Communications of the ACM, 17(8):453{455, 1974.8] L. Lamport. The mutual exclusion problem. Journal of the ACM, 33(2):313{326,327{348, 1986.9] G. Peterson and M. Fischer. Economical solutions for the critical section problem in adistributed system. In Proceedings of 9th ACM Symposium on Theory of Computing,pages 91{97, May 1977.42610] J.

Burns, M. Fischer, P. Jackson, N. Lynch, and G. Peterson. Data requirements forimplementation of n-process mutual exclusion using a single shared variable. Journalof the ACM, 29(1):183{205, 1982.11] M. Merritt and G. Taubenfeld. Speeding Lamport's fast mutual exclusion algorithm.AT&T Technical Memorandum, May 1991. Also, submitted for publication.D.4.2 Resource Allocation1] M. Fischer, N. Lynch, J. Burns, and A.

Borodin. Resource allocation with immunityto limited process failure. In Proceedings of 20th IEEE Symosium on Foundations ofComputer Science, pages 234{254, October 1979.2] M. Fischer, N. Lynch, J. Burns, and A. Borodin. Distributed FIFO allocation ofidentical resources using small shared space. ACM Trans. Prog. Lang. and Syst.,11(1):90{114, January 1989.3] D. Dolev, E. Gafni, and N.