AF: Small: Distributed Algorithmic Foundations of Dynamic Networks

University Of Houston, Houston TX

Investigators

Abstract

The overarching goal of this project is to significantly advance the state of the art in the algorithmic foundations of distributed computing for dynamic networks. In a dynamic network, the topology of the network---both nodes (representing processors/endhosts) and communication links---changes continuously over time. Modern networking technologies such as peer-to-peer networks, overlay networks, and ad hoc wireless and mobile networks, are inherently very dynamic; furthermore, they are resource-constrained, unreliable, and vulnerable to attacks. Distributed/decentralized algorithms are critical to the efficient operation of large-scale communication networks, e.g., distributed shortest paths algorithms are used for routing in the Internet. Till recently, much of the distributed algorithmic theory developed over the last three decades has focused mainly on static networks; as such its results do not apply to dynamic networks. This necessitates the development of a solid theoretical foundation for robust, secure, and scalable distributed computing for dynamic networks. Such a foundation is critical to realize the full potential of these large-scale networks that have a wide variety of applications including communication, data storage and retrieval, environment monitoring, electronic commerce, resource distribution and sharing, and search. The project will develop a rigorous theoretical foundation for distributed computing in highly dynamic networks. In particular, it will develop and analyze distributed algorithms that scale well to very large-sized networks, are highly robust to dynamic changes and large-scale failures, and are secure against malicious participants in the network. The project will result in an algorithmic toolkit which will provide the building blocks for performing distributed computation in dynamic networks, besides providing algorithms with performance guarantees and theoretical benchmarks for practitioners. The project has the potential to impact the design and engineering of topologically-aware and self-regulating networks, i.e., networks that can measure, monitor, and regulate themselves in a decentralized fashion. The PI plans to develop a new course and a textbook on distributed network algorithms that is closely related to the research undertaken. This research will actively involve postdoctoral researchers, graduate students, and undergraduate students. The project has two key research goals. First, it will design and analyze scalable and robust distributed algorithms for fundamental distributed computing problems including agreement, leader election, storage and search, and routing. These problems are basic building blocks in distributed computing and are widely used. Motivated by fault-tolerance and security considerations, the project will study the above problems in an adversarial dynamic setting, that can also include the presence of Byzantine (malicious) nodes which may try to foil the distributed algorithm. The project will also study lower bounds on the performance of distributed algorithms including the amount of dynamism that can be tolerated. Second, it will develop fully-distributed algorithms for computing key global metrics of a network and to maintain dynamic networks with desirable properties. This addresses an important issue that is complementary and also critical to the first goal, i.e., how to measure basic parameters of a dynamic network such as its size, connectivity properties, conductance, average degree and other node-related statistics. A related goal is to construct and maintain dynamic networks with good topological properties such as low diameter, high connectivity, and high conductance. In both the above research goals, the key challenge is to design scalable distributed algorithms that are robust and fault-tolerant even under a high amount of dynamism and the presence of a large amount of Byzantine nodes. The project will build on and significantly extend the distributed algorithmic framework for dynamic networks that was recently developed by the PI and his collaborators.