Achieving Causality with Physical Clocks
Pages 97 - 106
Abstract
Physical clocks provide more precision than applications can use. For example, a 64 bit NTP clock allows a precision of 233 picoseconds. In this paper, we focus on whether the least significant bits that are not useful to the applications could be used to track (one way) causality among events.
We present PWC (Physical clock With Causality) that uses the extraneous bits in the physical clock. We show that PWC is very robust to errors in clock skew and transient errors. We show that PWC can be used as both a physical and logical clock for a typical distributed application even if just 6-9 extraneous bits (corresponding to precision of 15-120 nanoseconds) are available. Another important characteristic of PWC is that the standard integer < operation can be used to compare timestamps to deduce (one-way) causality among events. Thus, PWC is significantly more versatile than previous approaches for using the physical clock to provide causality information.
References
[1]
2008. IEEE Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems. IEEE Std 1588-2008 (Revision of IEEE Std 1588-2002) (2008), 1–300. https://doi.org/10.1109/IEEESTD.2008.4579760
[2]
2021. Experimental data and source code for the paper ”Achieving Causality with Physical Clocks”. https://gist.github.com/AnonymousPaperPWC/39001b43cda3b5aa3a99783b0b418c74.
[3]
Paulo Sérgio Almeida, Carlos Baquero, and Victor Fonte. 2008. Interval Tree Clocks. In Principles of Distributed Systems, 12th International Conference, OPODIS 2008, Luxor, Egypt, December 15-18, 2008. Proceedings(Lecture Notes in Computer Science, Vol. 5401), Theodore P. Baker, Alain Bui, and Sébastien Tixeuil (Eds.). Springer, 259–274.
[4]
Anish Arora and Mohamed G. Gouda. 1994. Distributed Reset. IEEE Trans. Computers 43, 9 (1994), 1026–1038.
[5]
Aleksey Charapko, Ailidani Ailijiang, Murat Demirbas, and Sandeep Kulkarni. 2017. Retrospective Lightweight Distributed Snapshots Using Loosely Synchronized Clocks. In Distributed Computing Systems (ICDCS), 2017 IEEE 37th International Conference on. IEEE, 2061–2066.
[6]
James C Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, Jeffrey John Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, 2013. Spanner: Google’s globally distributed database. ACM Transactions on Computer Systems (TOCS) 31, 3 (2013), 8.
[7]
Murat Demirbas and Sandeep Kulkarni. 2013. Beyond truetime: Using augmentedtime for improving google spanner. In Workshop on Large-Scale Distributed Systems and Middleware (LADIS).
[8]
Jiaqing Du, Călin Iorgulescu, Amitabha Roy, and Willy Zwaenepoel. 2014. GentleRain: Cheap and Scalable Causal Consistency with Physical Clocks. In Proceedings of the ACM Symposium on Cloud Computing (Seattle, WA, USA) (SOCC ’14). ACM, New York, NY, USA, Article 4, 13 pages.
[9]
Christof Fetzer and Michel Raynal. 2003. Elastic Vector Time. In 23rd International Conference on Distributed Computing Systems (ICDCS 2003), 19-22 May 2003, Providence, RI, USA. IEEE Computer Society, 284.
[10]
Colin J Fidge. 1988. Timestamps in message-passing systems that preserve the partial ordering. In Proceedings of the 11th Australian Computer Science Conference (ACSC), Kerry Raymond (Ed.). 56–66.
[11]
Sukumar Ghosh. 2014. Distributed systems: an algorithmic approach. CRC press.
[12]
Sandeep S. Kulkarni, Gabe Appleton, and Duong N. Nguyen. 2021. Achieving Causality with Physical Clocks. CoRR abs/2104.15099(2021). arXiv:2104.15099
[13]
Sandeep S Kulkarni, Murat Demirbas, Deepak Madappa, Bharadwaj Avva, and Marcelo Leone. 2014. Logical physical clocks. In International Conference on Principles of Distributed Systems. Springer, 17–32.
[14]
Leslie Lamport. 1974. A new solution of Dijkstra’s concurrent programming problem. Commun. ACM 17, 8 (1974), 453–455.
[15]
Leslie Lamport. 1978. Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21, 7 (July 1978), 558–565.
[16]
Friedemann Mattern. 1989. Virtual time and global states of distributed systems. Parallel and Distributed Algorithms 1, 23 (1989), 215–226.
[17]
D. Mills, J. Martin, J. Burbank, and W. Kasch. 2010. Network Time Protocol Version 4: Protocol and Algorithms Specification. RFC 5905. RFC Editor.
[18]
D. L. Mills. 1985. Network Time Protocol (NTP). RFC 958. RFC Editor.
[19]
Lum Ramabaja. 2019. The bloom clock. arXiv preprint arXiv:1905.13064(2019).
[20]
Mohammad Roohitavaf, Murat Demirbas, and Sandeep S. Kulkarni. 2017. CausalSpartan: Causal Consistency for Distributed Data Stores using Hybrid Logical Clocks. In 36th IEEE Symposium on Reliable Distributed Systems, SRDS 2017, Hongkong, China, September 26 - 29, 2017. 184–193.
[21]
Ulrich Schmid and Alfred Pusterhofer. 1995. SSCMP: The Sequenced Synchronized Clock Message Protocol. Comput. Networks ISDN Syst. 27, 12 (1995), 1615–1632.
[22]
Reinhard Schwarz and Friedemann Mattern. 1994. Detecting causal relationships in distributed computations: In search of the holy grail. Distributed computing 7, 3 (1994), 149–174.
[23]
Vidhya Tekken Valapil and Sandeep S. Kulkarni. 2018. Biased Clocks: A Novel Approach to Improve the Ability To Perform Predicate Detection with O(1) Clocks. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma’ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers. 345–360.
Index Terms
- Achieving Causality with Physical Clocks
Index terms have been assigned to the content through auto-classification.
Recommendations
Reduction of Messages Unnecessarily Ordered in Scalable Group Communication
CISIS '10: Proceedings of the 2010 International Conference on Complex, Intelligent and Software Intensive SystemsIn distributed peer-to-peer (P2P) applications, a group of multiple peer processes (peers) are required to cooperate with each other. Messages sent by peers have to be causally delivered. In this paper, we discuss a scalable group communication protocol ...
A Hybrid Approach for Synchronizing Clocks in Distributed Systems
Cloud Computing – CLOUD 2019AbstractThe 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 ...
A Scalable Peer-to-Peer Group Communication Protocol
AINA '10: Proceedings of the 2010 24th IEEE International Conference on Advanced Information Networking and ApplicationsIn peer-to-peer (P2P) applications, a group of multiple peer processes (peers) are required to cooperate with each other in a distributed manner. Messages sent by peers have to be causally delivered to every peer in a group. Due to the message overhead ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2022
298 pages
ISBN:9781450395601
DOI:10.1145/3491003
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 January 2022
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
Conference
ICDCN '22
ICDCN '22: 23rd International Conference on Distributed Computing and Networking
January 4 - 7, 2022
AA, Delhi, India
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 250Total Downloads
- Downloads (Last 12 months)133
- Downloads (Last 6 weeks)14
Reflects downloads up to 26 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in