Dissertation
Stability of aggregate computing
University of Iowa
Doctor of Philosophy (PhD), University of Iowa
Autumn 2019
DOI: 10.17077/etd.005255
Abstract
Open cyber-physical systems like smart cities, tactical information sharing, personal and home area networks, and the Internet of Things (IoT) require seam- less, low latency, peer to peer local interactions between devices. Their potential is curtailed by the fact that devices currently interact either through device and application specific protocols that are not reusable, or centralized infrastructures like clouds. The recent proposed aggregate computing approach offers a solution to this bottleneck through a multi-layered architecture. In this thesis, we focus on the middle layer of Aggregate Computing, which consists of three classes of basis blocks that are G-block, C-block and T-block, whose compositions, sometimes in feedback, can be used to realize a wide class of coordination tasks. However, the formal analysis of individual blocks is limited to self-stabilization which only involves eventual convergence and is not endowed with robustness properties. Further, the stability analysis of these compositions, though conjectured, is largely unexplored. In this thesis, we will first investigate the robust stability of the G-block and its variants from a control perspective, then analyze the dynamics and characterize the stability conditions for compositions of those basis blocks.
Characterizing each individual block’s behavior is necessary in understanding their stable compositions. Thus, we formulate Lyapunov functions for two special G-block distributed algorithms to prove their global uniform asymptotic stability (GUAS) and global uniform exponential stability (GUES) respectively, as well as find ultimate bounds on states and the time to attain them, under persistent structural perturbations. For the generalized G-block, we prove its GUAS and robustness without using a Lyapunov function. With respect to the compositions, we first study a state estimation algorithm using an open-loop G-C combination by analyzing its error bounds and dynamics. We next present a resilient leader election algorithm using a feedback interconnection of those basis blocks, and prove its GUAS and resilience under transient perturbations.
We will show that these basis block distributed algorithms exhibit unusual and subtle state dependencies that are uncommon in standard stability analysis, which changes both the nature of the Lyapunov functions and the analysis. The ultimate boundedness we derive will open up the prospect of establishing small gain type theorems, which in turn helps to demonstrate closed loop stability. Also, the resilient design and stability analysis of the leader election algorithm will assist in improving algorithms based on basis blocks, and providing conditions for stable composability. Ultimately, those analysis works will help us develop constructs and tools that go well beyond existing approaches and thus will fundamentally impact the standard stability analysis.
Details
- Title: Subtitle
- Stability of aggregate computing
- Creators
- Yuanqiu Mo
- Contributors
- Soura Dasgupta (Advisor)Jacob Beal (Advisor)Er-wei Bai (Committee Member)Jon Kuhl (Committee Member)Raghuraman Mudumbai (Committee Member)Muthu Krishnamurthy (Committee Member)
- Resource Type
- Dissertation
- Degree Awarded
- Doctor of Philosophy (PhD), University of Iowa
- Degree in
- Electrical and Computer Engineering
- Date degree season
- Autumn 2019
- DOI
- 10.17077/etd.005255
- Publisher
- University of Iowa
- Number of pages
- xii, 176 pages
- Copyright
- Copyright 2019 Yuanqiu Mo
- Language
- English
- Description illustrations
- color illustrations
- Description bibliographic
- Includes bibliographical references (pages 166-176)
- Public Abstract (ETD)
Open cyber-physical systems have dramatically changed how we relate to computing. These systems allow many computing devices to be involved in provisioning parts of any given service, and each device may simultaneously participate in multiple services. Realization of the full potential of these systems requires that devices interact with others in their locality. Ordinary programming approaches are very device-centric and entangle application design with coordination and communication, leading to lack of modularity and reusability. Aggregate computing provides an alternate approach, which simplifies the design, creation, and maintenance of complex distributed systems by using a layered approach. This thesis focuses on the middle layer of aggregate computing, which comprises three classes of basis blocks, G-block, C-block and T-block, that facilitate resilient device interactions. Previous work only proved those individual blocks to be self-stabilizing without any implication for robustness, which is an important property in system design. Further, the stability analysis of their compositions remains largely unexplored.
Our work first addresses the robust stability of G-block and its variants, proving their global uniform asymptotic stability (GUAS) or global uniform exponential stability (GUES) and robustness under persistent structural perturbations. Then we analyze the error bounds and dynamics of a commonly used G-C combination. Finally, we design a leader election algorithm via a feedback interconnection of basis blocks, and prove its GUAS and resilience.
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9983779899602771
Metrics
9 File views/ downloads
81 Record Views