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.
|Advisor:||Abbadi, Amr El|
|Commitee:||Bamieh, Bassam, Gilbert, John, Suri, Subhash|
|School:||University of California, Santa Barbara|
|School Location:||United States -- California|
|Source:||DAI-B 70/09, Dissertation Abstracts International|
|Keywords:||Consensus, Distributed systems, Gossip, Load balancing, Sensor networks|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be