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

Date

2022-01-01

Author

Sokoto, Saidu
Onur, Ertan

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

78
views

0
downloads

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.

Subject Keywords

Lamport Clocks, Logical Clocks, Succinct Representation

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85138685885&origin=inward
https://hdl.handle.net/11511/101492

DOI

https://doi.org/10.1109/siu55565.2022.9864718

Conference Name

30th Signal Processing and Communications Applications Conference, SIU 2022

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

SGLC: A LOGICAL CLOCK USING SUCCINCT GRAPHS Sokoto, Saidu Aliyu Isa; Onur, Ertan; Department of Computer Engineering (2022-7-1) This thesis presents a new logical clock, SGLC, capable of capturing causality relationships in distributed systems. SGLC relies on a succinct graph representation codable and decodable in polynomial time while storing the graphs as integers. What makes SGLC feasible is that directed graphs can be used to implement logical clocks. Consequently, the main goal of introducing SGLC is to reduce the communication overhead of transporting causal history graphs by encapsulating the causality relationships of event...
Investigation of the effect of turbulence on entropy generation in turbomachinery Orhan, Ömer Emre; Uzol, Oğuz; Department of Aerospace Engineering (2014) The aim of this thesis is to apply a newly developed methodology to calculate entropy production. Entropy production calculations have always attracted attention due to its extreme importance in efficiency improvement. Efficiency improvement can be achieved via several optimization techniques and Entropy Generation Minimization (EGM) is one of the most acknowledged ones. When it comes to the design and analysis of turbomachinery components, the performance deterioration due to various real flow effects such...
Single and multi agent real-time path search in dynamic and partially observable environments Ündeğer, Çağatay; Polat, Faruk; Department of Computer Engineering (2007) In this thesis, we address the problem of real-time path search in partially observable grid worlds, and propose two single agent and one multi-agent search algorithm. The first algorithm, Real-Time Edge Follow (RTEF), is capable of detecting the closed directions around the agent by analyzing the nearby obstacles, thus avoiding dead-ends in order to reach a static target more effectively. We compared RTEF with a well-known algorithm, Real-Time A* (RTA*) proposed by Korf, and observed significant improvemen...
Palmprint recognition based on 2-d gabor filters Konuk, Barış; Akar, Gözde; Department of Electrical and Electronics Engineering (2007) In this thesis work, a detailed analysis of biometric technologies has been done and a new palmprint recognition algorithm has been implemented. The proposed algorithm is based on 2-D Gabor filters. The developed algorithm is first tested on The Hong Kong Polytechnic University Palmprint Database in terms of accuracy, speed and template size. Then a scanner is integrated into the developed algorithm in order to acquire palm images; in this way an online palmprint recognition system has been developed. Then ...
New change detection method using double segmentation and its application on remotely sensed images Gedik, Ekin; Yarman Vural, Fatoş Tunay; Department of Computer Engineering (2013) Change detection research, a branch of statistical data analysis, focuses on detecting changed samples between di erent observations of the same dataset. The proposed study presents a novel change detection procedure and its application as a complete framework which is designed to work on remotely sensed images. The scope of the study is defined as detecting man-made change objects between satellite images of the same region, acquired at di erent times. Proposed framework has three main steps as preprocessi...

Citation Formats

S. Sokoto and E. Onur, “SGLC: A Logical Clock Using Succinct Graphs Öz Çizge Gösterimleri ile Bir Mantiksal Saat,” presented at the 30th Signal Processing and Communications Applications Conference, SIU 2022, Safranbolu, Türkiye, 2022, Accessed: 00, 2023. [Online]. Available: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85138685885&origin=inward.