SGLC: A Logical Clock Using Succinct Graphs Öz Çizge Gösterimleri ile Bir Mantiksal Saat

Sokoto S., ONUR E.

30th Signal Processing and Communications Applications Conference, SIU 2022, Safranbolu, Turkey, 15 - 18 May 2022 identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/siu55565.2022.9864718
  • City: Safranbolu
  • Country: Turkey
  • Keywords: Lamport Clocks, Logical Clocks, Succinct Representation
  • Middle East Technical University Affiliated: Yes


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