Design and analysis of algorithms for large-scale distributed systems: A control theoretic approach.

摘要

In classical distributed systems literature, distributed protocols often assume global knowledge of the size and membership of the network and the existence of a global communication mechanism such as broadcast that enables each node to communicate with every other node. In contrast to these assumptions, modern and emerging distributed systems, such as peer-to-peer networks, sensor networks, mobile ad-hoc networks, and even the internet in general, are characterized by massive scale, frequently changing membership, and changing communication structures due to failures and mobility. In addition, the devices that participate in these networks may have limited resources as well as security and privacy constraints. These network and device characteristics necessitate a new approach to how we model distributed systems, how we design distributed algorithms, and how we analyze the correctness and performance of these algorithms.;This thesis centers on the development of novel techniques for the modeling and analysis of algorithms for distributed systems, with a specific focus on techniques that can accommodate the dynamics of these systems. We begin with a theoretical study of distributed consensus algorithms and the closely related problem of load balancing. Drawing upon several tools from the body of cooperative control theory, including stability analysis, spectral graph theory, and perturbative spectral theory, we analyze the correctness and performance of consensus algorithms and the effects of network size, topology, and dynamics such as noise and communication failures. We also give a general framework for the development and analysis of local algorithms for constrained convex optimization, of which the consensus algorithm is a special case. We then turn to the more concrete domain of ubiquitous sensing applications. We present Environmental Tomography, a technique for privacy-preserving, scalable ubiquitous sensing and estimation of environmental phenomena using mobile devices. While this application is more practical in nature, it relies on theoretical underpinnings in optimization and an understanding of natural physical dynamics. Finally, we tie the problems of distributed optimization and ubiquitous sensing together and present and analyze a distributed algorithm for environmental sensing and estimation.