Akademik Veri Yönetim Sistemi
30th Signal Processing and Communications Applications Conference, SIU 2022, Safranbolu, Türkiye, 15 - 18 Mayıs 2022
© 2022 IEEE.Causal ordering in distributed systems has received much attention over the past four decades and different schemes for capturing causality have been proposed. Despite the fact that event space-time diagrams can be viewed as directed graphs, the few schemes that make use of graphs are obsolete. This is due to the significant cost of maintaining graphs using the standard representation. In this paper, we revisit the use of graphs for keeping track of causal relationships by leveraging on a succinct representation of graphs that is encodable and decodable in polynomial time while storing them close to the information theoretical lower limit. We propose the SGLC, a logical clock using succinct graph representations. Comparisons performed with the vector clock based on the aggregate size of messages exchanged show a reduction in total bits exchanged. This reduction can range from more than 40% to 85% for 8 to 32 processes and a maximum of 100 events.