Stability of aggregate computing

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.