SGLC: A LOGICAL CLOCK USING SUCCINCT GRAPHS

Download
2022-7-1
Sokoto, Saidu Aliyu Isa
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.

Suggestions

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...
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...
Almost periodic solutions of recurrently structured impulsive neural networks
Top, Gülbahar; Akhmet, Marat; Department of Mathematics (2022-3-28)
This thesis aims to conduct detailed and precise neural networks research with impulses at nonprescribed moments in terms of periodic and almost periodic solutions. Most of the actions in nature modeled by neural networks involve repetitions. Hence periodic and almost periodic motions become crucial. So in this thesis, the existence, uniqueness, and stability of the periodic and almost periodic motion are served for the neural networks with prescribed and nonprescribed impacts. This impulsive system is a n...
Citation Formats
S. A. I. Sokoto, “SGLC: A LOGICAL CLOCK USING SUCCINCT GRAPHS,” M.S. - Master of Science, Middle East Technical University, 2022.