article

Free access

Simulating synchronized clocks and common knowledge in distributed systems

Authors:

Sam TouegAuthors Info & Claims

Journal of the ACM (JACM), Volume 40, Issue 2

Pages 334 - 367

https://doi.org/10.1145/151261.151267

Published: 01 April 1993 Publication History

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]

~APT, K. R., AND RICH1ER, J.-L. Real time clocks versus virtual clocks. In M. Broy, ed. Control ~Flow and Data Flow: Concepts of Distributed Programming. NATO Advanced Study Institute ~Series, vol. FI4, Sprmger-Verlag, New York, 1985, pp. 475 503.

[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]

~BiP, MAN, K. P., AND JOSEPH, T.A. Rehable communication in the presence of failures. ACM ~Troth3. Compttt. S),M. 5, 1 (Feb. 1987), 47-76.

[5]

~CHANDY, K. M., AND LAMPORT, L Distributed snapshots: Determining global states of ~distributed systems. A('M Trans. Cornpttt. Syst. 3, 1 (Feb. 1985), 63-75.

[6]

~CIlANDY, K. M., AND MISRA, J. How processes learn. Dzst Compt~t. 1, 1 (1986) 40-52.

[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]

~DWORK, C., AND MOSES, Y. Knowledge and common knowledge m a Byzantine environ- ~ment: Crash failures, hzf Comptttatton 88, 2 (Oct. 1990), 156 186.

[9]

~FAGIN, R., HALPERN, J. Y., AND VARDI, M.Y. A model-theoretic analysis of knowledge. J ~ACM 38, 2 (Apr. 1991), 382-428.

[10]

~FAGiN, R., .AND VARDi, M.Y. An internal semantics for modal logic: Prelinnnary report. In ~Proceedings' o/the 17th AC3I &'mpostum on Theoly of Computing (Providence, R.I., May 6 8). ~ACM, New York, 1985, pp. 305-315.

[11]

~FISCHER, M. J. AND IMMERIVlAN, N. Foundations of knowledge for d~stnbuted systems. In ~Joseph Y. Halpern, ed. Proceedings oj the 1st Colzference o~l Theoretical Aspects of Reasotting ~about kSlowledge. Morgan-Kaufmann, San Mateo, Calif., 1986, pp. 171 185.

[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]

~HALPERN, J. Y., AND MOSES, Y. Knowledge and common knowledge in a distributed ~environment. Z ACM 37, 3 (July 1990), 549-587.

[15]

~HALPERN, J. Y., MOSES, Y., AND WAARTS, O. A characterization of eventual Byzantine ~agreement. In Proceedings of tile 9th Annual ACM Symposium on Princzples of Distributed ~Computing, (Quebec City, Que., Canada, Aug. 22-24). ACM, New York, 1990, pp. 333-346.

[16]

~JEFFERSON, D.R. Virtual time. ACM Trans. Prog. Lang. Syst. 7, 3 (July 1985), 404-425.

[17]

~LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Commun. ~ACM 21, 7 (July 1978), 558 565.

[18]

~LAMPORT, L, AND MELLIAR-SMITH, P.M. Synchronizing clocks in the presence of faults. J. ~ACM 32, 1 (Jan. 1985), 52-78.

[19]

~LAMPORT. L., SHOSTAK, g., AND PEASE, M. The Byzantine generals problem. ACM Trans. ~Prog. Lang. Syst. 4, 3 (July 1982), 382 401.

[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]

~NEIGER, G. Knowledge consistency: A useful suspension of disbelief (preliminary report). In ~Moshe Y. Vardi, ed. Proceedings of the 2nd Conference on Theorettcal Aspects of Reasoning ~about Knowledge (March). Morgan-Kaufmann, San Mateo, Calif., 1988, pp. 295-308.

[24]

~NEIGER, G., AND BAZZI, R. Using knowledge to opnmally achieve coordination in dis- ~tributed systems. In Y. Moses, ed. Proceedings of the 4th Conference on Theoretical Aspects of ~Reasoning about I~)qowledge (March). Morgan-Kaufmann, San Mateo, Calif., 1992, pp. 43-59.

[25]

~NEIGER, a., AND TUTTLE, M.R. Common knowledge and consistent simultaneous coordina- ~tion. In J. van Leeuwen and N. Santoro, eds., Proceedings of the 4th hlternational Workshop on ~DlstributedAlgorithms (Sept.). Lecture Notes on Computer Science, vol. 486. Springer-Verlag, ~New York, 1990, pp. 334-352. Dist. Comput., to appear.

[26]

~NGUYEN, V., AND PERRY, K. J. Do we really know what knowledge is? Unpublished ~manuscript, 1986.

[27]

~PANANGADEN, P., AND TAYLOR, K. Concurrent common knowledge: Defining agreement for ~asynchronous systems. Dist. Comput. 6, 2 (1992), 73 94.

[28]

~PAPADIMITRIOU, C.H. The serializability of concurrent database updates. J. ACM 26, 4 (Oct. ~1979), 631-653.

[29]

~ PARIKH, R., AND RAMANUJAM, R. Distributed processes and the logic of knowledge. In R. ~Parikh, ed., Proceedings of' the Conference on Logics of Programs. Lecture Notes on Computer ~Science, vol. 193. Springer-Verlag, New York, 1985, pp. 256-268.

[30]

~PERRY, K. J., AND TOUEG, S. Distributed agreement in the presence of processor and ~communication faults. IEEE Trans. Sofiw. Eng. 12, 3 (Mar. 1986), 477-482,

[31]

~SRIKANTH, T. K., AND TOUEG, S. Optimal clock synchronization. J. ACM 34, 3 (July 1987), ~626-645.

[32]

~WELCH, J. L. Simulating synchronous processors. Inf Computation 74, 2 (Aug. 1987), ~159-171.

[33]

~WELCH, J. L., AND Lh:NCH, N.A. A new fault-tolerant algorithm for clock synchronization. ~lnf Computation 77, 1 (Apr. 1988), 1-36.

Cited By

Halpern JMoses Y(2014)A procedural characterization of solution concepts in gamesJournal of Artificial Intelligence Research10.5555/2655713.265571849:1(143-170)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.5555/2655713.2655718
Moser HSchmid U(2014)Reconciling fault-tolerant distributed algorithms and real-time computingDistributed Computing10.1007/s00446-013-0204-127:3(203-230)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1007/s00446-013-0204-1
Sietsma FApt K(2013)Common Knowledge in Email ExchangesACM Transactions on Computational Logic10.1145/2499937.249994414:3(1-23)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1145/2499937.2499944
Show More Cited By

Index Terms

Simulating synchronized clocks and common knowledge in distributed systems

Recommendations

A Hybrid Approach for Synchronizing Clocks in Distributed Systems
Cloud Computing – CLOUD 2019
Abstract
The art of synchronizing clocks across a wide area network has got a new dimension when it comes to the reality of achieving the demand for high-accuracy synchronization; even for local or small computing systems. Before implementing any clock ...
Practical uses of synchronized clocks in distributed systems

Synchronized clocks are interesting because they can be used to improve performance of a distributed system by reducing communication. Since they have only recently become a reality in distributed systems, their use in distributed algorithms has ...
Using integer clocks to verify clock-synchronization protocols

We use the Uppaal model checker for timed automata to verify the Timing-Sync time-synchronization protocol for sensor networks (TPSN), the clock-synchronization algorithm of Lenzen, Locher and Wattenhofer (LLW) for general distributed systems, and the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 40, Issue 2

April 1993

207 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/151261

Issue’s Table of Contents

Copyright © 1993 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1993

Published in JACM Volume 40, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
984
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)11

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Halpern JMoses Y(2014)A procedural characterization of solution concepts in gamesJournal of Artificial Intelligence Research10.5555/2655713.265571849:1(143-170)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.5555/2655713.2655718
Moser HSchmid U(2014)Reconciling fault-tolerant distributed algorithms and real-time computingDistributed Computing10.1007/s00446-013-0204-127:3(203-230)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1007/s00446-013-0204-1
Sietsma FApt K(2013)Common Knowledge in Email ExchangesACM Transactions on Computational Logic10.1145/2499937.249994414:3(1-23)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1145/2499937.2499944
Moser H(2009)Towards a real-time distributed computing modelTheoretical Computer Science10.1016/j.tcs.2008.10.012410:6-7(629-659)Online publication date: 20-Feb-2009
https://dl.acm.org/doi/10.1016/j.tcs.2008.10.012
Cranefield S(2006)Reliable Group Communication and Institutional Action in a Multi-agent Trading ScenarioAgent Communication II10.1007/978-3-540-68143-4_18(258-272)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1007/978-3-540-68143-4_18
Lynch N(2005)Simulation techniques for proving properties of real-time systemsA Decade of Concurrency Reflections and Perspectives10.1007/3-540-58043-3_24(375-424)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-58043-3_24
Halpern JMoses Y(2004)Using counterfactuals in knowledge-based programmingDistributed Computing10.1007/s00446-004-0108-117:2(91-106)Online publication date: 1-Aug-2004
https://dl.acm.org/doi/10.1007/s00446-004-0108-1
Fagin RHalpern JMoses YVardi M(2003)Common Knowledge RevisitedKnowledge Contributors10.1007/978-94-007-1001-6_5(87-104)Online publication date: 2003
https://doi.org/10.1007/978-94-007-1001-6_5
Delporte-Gallet CFauconnier HGuerraoui R(2002)Failure Detection Lower Bounds on Registers and ConsensusDistributed Computing10.1007/3-540-36108-1_16(237-251)Online publication date: 24-Oct-2002
https://doi.org/10.1007/3-540-36108-1_16
Charron-Bost BGuerraoui RSchiper A(2000)Synchronous system and perfect failure detector: Solvability and efficiency issuesProceeding International Conference on Dependable Systems and Networks. DSN 200010.1109/ICDSN.2000.857585(523-532)Online publication date: 2000
https://doi.org/10.1109/ICDSN.2000.857585
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents