SGLC: A LOGICAL CLOCK USING SUCCINCT GRAPHS

Download

Saidu_thesis.pdf

Date

2022-7-1

Author

Sokoto, Saidu Aliyu Isa

Metadata

Show full item record

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

Item Usage Stats

193
views

133
downloads

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 events as graphs that are decoded at the receiving process. We implemented the new protocol in an ad hoc computing framework and conducted an extensive benchmarking campaign comparing it with the vector clock, which is the most well-established type of logical clock. In addition, we evaluated other ways of further reducing the communication overhead and the overall storage complexity of the proposed clock. Finally, we also studied the application of SGLC in two distributed algorithms. Results obtained from experiments performed on the bare implementation of SGLC show that a reduction of up to 85% is attainable for a limit of 100 events and 32 processes in terms of overall bits exchanged compared to the vector clock. Applying further optimizations to SGLC can result in a further reduction of 63% for the same number of events.

Subject Keywords

Logical Clocks, Linear Clocks, Succinct Representation, Succinct Graphs

URI

https://hdl.handle.net/11511/98196

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Convergence performance of the approximate factorization methods with multi-block implicit boundary conditions at hypersonic speeds Koca, Melikşah; Eyi, Sinan; Department of Aerospace Engineering (2022-9) This thesis study presents convergence characteristics of the implicit approximate factorization methods at hypersonic flow conditions and with 2-dimensional and 3-dimensional geometries. The efficiency of the implicit boundary conditions at block interfaces for the multi-block grids is investigated for different approximate factorization methods. Standard Alternating Direction Implicit (ADI) method, Diagonal Dominant Alternating Direction Implicit method (DDADI) with and without Huang’s sub-iteration corre...
Feedback motion planning of a novel fully actuated unmanned surface vehicle via sequential composition of random elliptical funnels Özdemir, Oğuz; Ankaralı, Mustafa Mert; Department of Electrical and Electronics Engineering (2022-12-27) This thesis proposes and analyzes a motion planning and control schema for unmanned surface vehicles that fuses sampling-based approaches’ probabilistic completeness with closed-loop approaches’ robustness. The Proposed schema is based on the sequential composition of elliptical funnels, and it consists of two stages: tree generation and motion control. For validation of the approach, we carried out experiments using both simulation and physical setup besides the mathematical analysis. In order to have a co...
Parallel decodable channel coding implemented on a MIMO testbed Aktaş, Tuğcan; Yılmaz, Ali Özgür; Department of Electrical and Electronics Engineering (2007) This thesis considers the real-time implementation phases of a multiple-input multiple-output (MIMO) wireless communication system. The parts which are related to the implementation detail the blocks realized on a field programmable gate array (FPGA) board and define the connections between these blocks and typical radio frequency front-end modules assisting the wireless communication. Two sides of the implemented communication testbed are discussed separately as the transmitter and the receiver parts. In a...
Temporal logic inference for classification and prediction from data Kong, Zhaodan; Jones, Austin; Medina, Ayala Ana; Aydın Göl, Ebru; Belta, Calin (2014-04-15) This paper presents an inference algorithm that can discover temporal logic properties of a system from data. Our algorithm operates on finite time system trajectories that are labeled according to whether or not they demonstrate some desirable system properties (e.g. "the car successfully stops before hitting an obstruction"). A temporal logic formula that can discriminate between the desirable behaviors and the undesirable ones is constructed. The formulae also indicate possible causes for each set of beh...
Electromagnetic interaction complexity reduction using deep learnin Karaosmanoğlu, Barışcan; Ergül, Özgür Salih; Department of Electrical and Electronics Engineering (2019) In this thesis, we present a novel approach to accelerate electromagnetic simulations by the multilevel fast multipole algorithm (MLFMA). The strategy is based on a progressive elimination of electromagnetic interactions, resulting in trimmed tree structures, during iterative solutions. To systematically perform such eliminations, artificial neural network (ANN) models are constructed and trained to estimate errors in updated surface current coefficients. These column eliminations are supported by straightf...

Citation Formats

S. A. I. Sokoto, “SGLC: A LOGICAL CLOCK USING SUCCINCT GRAPHS,” M.S. - Master of Science, Middle East Technical University, 2022.