INDIGO Home University of Illinois at Urbana-Champaign logo uic building uic pavilion uic student center

Predicate Detection in Large-Scale Locality-Driven Networks

Show simple item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF Shen_Min.pdf (2MB) (no description provided) PDF
Title: Predicate Detection in Large-Scale Locality-Driven Networks
Author(s): Shen, Min
Advisor(s): Kshemkalyani, Ajay D.
Contributor(s): Khokhar, Ashfaq; Buy, Ugo; Zhang, Kunpeng; Venkatakrishnan, Venkat N.
Department / Program: Computer Science
Graduate Major: Computer Science
Degree Granting Institution: University of Illinois at Chicago
Degree: PhD, Doctor of Philosophy
Genre: Doctoral
Subject(s): Distributed computing Predicate detection Physical time monitoring Large-scale system Locality-aware
Abstract: Global predicate detection is an important problem in many distributed systems. It aims at detecting whether a certain distributed property has been satisfied during the system execution. The traditional detection algorithms are based on logical clocks. They explore the causal relationship between events occurring during the system execution. However, this makes these algorithms not suitable to detect global properties in physical time. Furthermore, in arising new types of distributed systems, such as wireless sensor networks and modular robotics, where events are locality driven and the scale of the system is large with individual process having limited computation resources, the traditional algorithms simply cannot handle the complexities. To address these issues, we first propose the concept of locality-aware predicate (LAP) which aims at detecting predicates within a local region. Although a LAP is defined only within a local region, observing the local area consistently requires considering the entire system in a consistent manner. This raises the challenge of making the complexities of the corresponding detection algorithms scale-free. We design algorithms for detecting both stable and unstable LAPs and show that they are scale-free. We also propose the methodology of hierarchical repeated detection. This approach of detecting predicates relies only on neighborhood communication to collaboratively detect global predicates. Compared with the traditional detection algorithms, hierarchical detection incurs a much smaller cost which is distributed across the entire system, and is capable of continuing the detection even when individual node crashes during the detection. The performance evaluation of our proposed algorithm shows its great potential for detecting predicates in networks where individual process only has limited resources and is prone to crash failure. Furthermore, we propose the Instantaneously detection algorithm which is built on top of the hierarchical detection methodology. We combine several approximation techniques with the hierarchical detection method to make the algorithm capable of detecting predicates in physical time even when synchronized physical clock is not available in the system. Since the detection is achieved via neighborhood communication only, this algorithm can detect predicates in physical time with a high accuracy while still relies solely on logical clocks.
Issue Date: 2014-10-28
Genre: thesis
Rights Information: Copyright 2014 Min Shen
Date Available in INDIGO: 2016-11-05
Date Deposited: 2014-08

This item appears in the following Collection(s)

Show simple item record


Country Code Views
China 291
United States of America 145
Russian Federation 19
Ukraine 14
Germany 8


My Account


Access Key