Grouped Matrix Clocks with Reduced Complexity for Distributed Synchronization

EasyChair Preprint 14509

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 x 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 their communication frequencies. 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 reduces the timestamp size for frequent intra-group communication while preserving sufficient causal information for accurate event ordering via the group-level clocks. Theoretical analysis demonstrates asymptotic space and communication overhead reductions compared to the original matrix clock algorithm. Empirical evaluation confirms the optimization benefits, especially as system scale and communication locality increase. The proposed group matrix clock algorithm retains the powerful causality tracking capabilities of matrix clocks while improving efficiency for real-world distributed systems with heterogeneous communication patterns.

Keyphrases: Algorithms, Matrix Clocks, clock synchronization, distributed algorithms, distributed computing

@booklet{EasyChair:14509,
  author    = {Khizer Tariq and Hasib Aslam},
  title     = {Grouped Matrix Clocks with Reduced Complexity for Distributed Synchronization},
  howpublished = {EasyChair Preprint 14509},
  year      = {EasyChair, 2024}}