Simulating synchronized clocks and common knowledge in distributed systems
- 1 April 1993
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 40 (2) , 334-367
- https://doi.org/10.1145/151261.151267
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.Keywords
This publication has 21 references indexed in Scilit:
- A model-theoretic analysis of knowledgeJournal of the ACM, 1991
- Editor's foreword special issue on parallel and distributed computing, Part IAlgorithmica, 1988
- Optimal clock synchronizationJournal of the ACM, 1987
- Reliable communication in the presence of failuresACM Transactions on Computer Systems, 1987
- How processes learnDistributed Computing, 1986
- A new journal is bornDistributed Computing, 1986
- Virtual timeACM Transactions on Programming Languages and Systems, 1985
- Distributed snapshotsACM Transactions on Computer Systems, 1985
- Synchronizing clocks in the presence of faultsJournal of the ACM, 1985
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978