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

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...
Domain-Structured Chaos in a Hopfield Neural Network
Akhmet, Marat (World Scientific Pub Co Pte Lt, 2019-12-30)
In this paper, we provide a new method for constructing chaotic Hopfield neural networks. Our approach is based on structuring the domain to form a special set through the discrete evolution of the network state variables. In the chaotic regime, the formed set is invariant under the system governing the dynamics of the neural network. The approach can be viewed as an extension of the unimodality technique for one-dimensional map, thereby generating chaos from higher-dimensional systems. We show that the dis...
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...
Citation Formats
S. A. I. Sokoto, “SGLC: A LOGICAL CLOCK USING SUCCINCT GRAPHS,” M.S. - Master of Science, Middle East Technical University, 2022.