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).

Distributed Computing Logical Clocks Parallel and Distributed Computing Synchronization Causal Ordering