Simulating synchronized clocks and common knowledge in distributed systems

ABSTRACT

Time and knowledge are studied in synchronous and asynchronous distributed systems. A large class of problems that can be solved using logical clocks as if they were perfectly synchronized clocks is formally characterized. For the same class of problems, a broadcast primitive that can be used as if it achieves common knowledge is also proposed. Thus, logical clocks and the broadcast primitive simplify the task of designing and verifying distributed algorithms: The designer can assume that processors have access to perfectly synchronized clocks and the ability to achieve common knowledge.

REFERENCES

• 1: K. R. Apt , J.-L. Richier, Real time clocks versus virtual clocks, Control Flow and Data Flow: concepts of distributed programming, Springer-Verlag New York, Inc., New York, NY, 1987
• 2: ~BABAOCJLU, O., AND DRUMMOND, R. (Almost) no cost clock synchronization. In Proceedings ~of the 17th International Svmposmm on Fault-Tolerant Completing. IEEE Computer Society ~Press, New York, 1987, pp. 42 47. Dist. Computing, to appear.
• 3: ~BANATRE, M., AND LAi'ALME, G. Enchere: A distributed auction bidding system. In Proceed- ~ings of tile 3rd bltel~zatzonal Conference on Distributed Computing Systems. IEEE Computer ~Society Press, New York, 1982, pp. 833-837.
• 4: Kenneth P. Birman , Thomas A. Joseph, Reliable communication in the presence of failures, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.47-76, Feb. 1987 [doi>10.1145/7351.7478]
• 5: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 6: K. M. Chandy , Jayadev Misra, How processes learn, Distributed Computing, v.1 n.1, p.40-52, Jan. 1986 [doi>10.1007/BF01843569]
• 7: ~CRISTIAN, F., AGHILI, H., STRONG, H. R., AND DOLEV, D. Atomic broadcast: From simple ~message diffusion to Byzantine agreement. In Proceedings of the 15th International &'mpostttm ~on Fault-Toleratzt Computtng. IEEE Computer Society Press, New York, 1985, 200 206. (A ~revised version appears as IBM Research Laboratory Technical Report RJ5244 (Aprfi 1989).)
• 8: Cynthia Dwork , Yoram Moses, Knowledge and common knowledge in a byzantine environment: crash failures, Information and Computation, v.88 n.2, p.156-186, Oct. 1990 [doi>10.1016/0890-5401(90)90014-9]
• 9: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi, A model-theoretic analysis of knowledge, Journal of the ACM (JACM), v.38 n.2, p.382-428, April 1991 [doi>10.1145/103516.128680]
• 10: R Fagin , M Y Vardi, An internal semantics for modal logic, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.305-315, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22179]
• 11: M Fischer , N Immerman, Foundations of knowledge for distributed systems, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.171-185, March 1986, Monterey, California, United States
• 12: ~HADZI1ACOS, V. Issues of fault tolerance in concurrent computations. Ph.D. dissertation ~Aiken Computation Laboratory. Harvard Univ., Cambridge, Mass., June 1984. Tech. Rep. ~11-84.
• 13: ~HALPERN, J. Y., AND FAGIN, a.Modelling knowledge and action in distributed systems. Dzst. ~Compt~t 3, 4 (1989), 159 177.
• 14: Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Journal of the ACM (JACM), v.37 n.3, p.549-587, July 1990 [doi>10.1145/79147.79161]
• 15: Joseph Y. Halpern , Yoram Moses , Orli Waalrts, A characterization of eventual Byzantine agreement, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.333-346, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93437]
• 16: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 17: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 18: Leslie Lamport , P. M. Melliar-Smith, Synchronizing clocks in the presence of faults, Journal of the ACM (JACM), v.32 n.1, p.52-78, Jan. 1985 [doi>10.1145/2455.2457]
• 19: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 20: ~MORGAN, C. Global and logical time in distributed algorithms. Inf Proc. Lett. 20, 4 (May ~1985), 189-194.
• 21: ~MOSES, Y., DOLEV, D., AND HALPERN, J. Y. Cheating husbands and other stories: A case ~study of knowledge, action, and communication. Dist. Computing 1, 3 (1986), 167-176.
• 22: ~MOSES, Y., AND TUTTLE, M. R. Programming simultaneous actions using common knowl- ~edge, Algorithmzca 3, 1 (1988), 121-169.
• 23: Gil Neiger, Knowledge Consistency: A Useful Suspension of Disbelief, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.295-308, March 01, 1988
• 24: Gil Neiger , Rida Bazzi, Using knowledge to optimally achieve coordination is distributed systems, Proceedings of the fourth conference on Theoretical aspects of reasoning about knowledge, p.43-59, March 1992, Monterey, California, United States
• 25: Gil Neiger , Mark R. Tuttle, Common knowledge and consistent simultaneous coordination, Proceedings of the 4th international workshop on Distributed algorithms, p.334-352, June 1991, Bari, Italy
• 26: ~NGUYEN, V., AND PERRY, K. J. Do we really know what knowledge is? Unpublished ~manuscript, 1986.
• 27: Prakash Panangaden , Kim Taylor, Concurrent common knowledge: defining agreement for asynchronous systems, Distributed Computing, v.6 n.2, p.73-93, September 1992 [doi>10.1007/BF02252679]
• 28: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 29: Rohit Parikh , R. Ramanujam, Distributed Processes and the Logic of Knowledge, Proceedings of the Conference on Logic of Programs, p.256-268, June 17-19, 1985
• 30: K J Perry , S Toueg, Distributed agreement in the presence of processor and communication faults, IEEE Transactions on Software Engineering, v.12 n.3, p.477-482, March 1986
• 31: T. K. Srikanth , Sam Toueg, Optimal clock synchronization, Journal of the ACM (JACM), v.34 n.3, p.626-645, July 1987 [doi>10.1145/28869.28876]
• 32: Jennifer Lundelius Welch, Simulating synchronous processors, Information and Computation, v.74 n.2, p.159-171, Aug. 1987 [doi>10.1016/0890-5401(87)90029-0]
• 33: Jennifer Lindelius Welch , Nancy Lynch, A new fault-tolerant algorithm for clock synchronization, Information and Computation, v.77 n.1, p.1-36, April 1988 [doi>10.1016/0890-5401(88)90043-0]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Asynchronous/synchronous operation

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.4 Performance Analysis and Design Aids**
          Subjects: Formal models**; Verification**

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications; Distributed networks
      C.2.2 Network Protocols
          Subjects: Protocol verification

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management

General Terms:
Algorithms, Theory, Verification

Keywords:
clock synchronization, common knowledge, knowledge-based protocols, logical clocks, synchronized clocks, timestamped common knowledge