Abstract

Logical clock synchronization is a crucial aspect of distributed systems, enabling the correct ordering of events and maintaining causal relationships. The matrix clock algorithm, while effective, suffers from quadratic communication overhead as the number of processes increases due to its n × n matrix size representation. This paper introduces a novel group-based matrix clock algorithm that reduces this overhead by exploiting communication locality patterns among processes. The key idea is to partition processes into multiple groups based on the frequency of communication. Processes within a frequently communicating group maintain a small intra-group matrix clock, while each group maintains a compact group-level matrix clock summarizing the group’s collective knowledge. Inter-group communication is timestamped using these group matrix clocks, reducing the overhead compared to fully replicated global matrix clocks. This approach minimizes the timestamp size for frequent intragroup communication while preserving sufficient causal information for accurate event ordering via the group-level clocks. Theoretical analysis demonstrates significant reductions in space and communication overhead compared to the original matrix clock algorithm. The proposed group matrix clock algorithm retains the powerful causality tracking capabilities of matrix clocks while relaxing the lower bound for the space complexity to Ω(N2).

References

• Chandeepa Dissanayake and Chanuka Algama. A review on message complexity of the algorithms for clock synchronization in distributed systems, 2024.
• C.J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. Australian Computer Science Communications, 10(1):56–66, 1988.
• Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558– 565, 1978.
• Yuliang Li, Gautam Kumar, Hema Hariharan, Hassan Wassel, Peter Hochschild, Dave Platt, Simon Sabato, Minlan Yu, Nandita Dukkipati, Prashant Chandra, and Amin Vahdat. Sundial: Fault-tolerant clock synchronization for datacenters. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 1171–1186. USENIX Association, November 2020.
• Friedemann Mattern. Virtual time and global states of distributed systems. Parallel and Distributed Algorithms, 1(23):215–226, 1989.
• Friedemann Mattern. Efficient algorithms for distributed snapshots and global virtual time approximation. Journal of Parallel and Distributed Computing, 18(4):423–434, 1993.
• Jan Ruh, Wilfried Steiner, and Gerhard Fohler. Clock synchronization in virtualized distributed real-time systems using ieee 802.1as and acrn. IEEE Access, 9:126075–126094, 2021.
• A. Singh and N. Badal. An overview of matrix clock synchronization in distributed computing environments. International Journal of Computer Applications, 125(3):24–30, 2015.
• Khizer Tariq and Hasib Aslam. Grouped matrix clocks with reduced complexity for distributed synchronization. EasyChair Preprint 14509, EasyChair, 2024.