NSF Award 1421918
NeTS: Small: Impact of Wireless Network Characteristics on Distributed Computation
Wireless networks have current and future applications in many domains, including emergency
response and rescue, monitoring and surveillance, distributed sensing, swarm robotics, and
smart grids. In such distributed systems, wireless networks are useful to allow the different
agents in the system to communicate and jointly coordinate their activities. This project
investigates design of efficient algorithms for implementing the distributed primitives while
taking into account the properties of the communication network. Coordination primitives of
interest include consensus, fault-tolerant broadcast, and distributed optimization. For instance,
the consensus primitive allows the different agents to agree on a common course of action, as a
function of potentially different actions suggested by different agents.
The scope of this project is at the intersection of communication and computing. The project
investigates the impact of wireless network characteristics such as error-prone links, dynamic
topology, broadcast medium, and capacity constraints, on the design and performance of algorithms
for important distributed computation problems. Two classes of algorithms are of interest, namely,
iterative algorithms and unconstrained algorithms. Iterative algorithms have a simple iterative
structure, and they maintain a small amount of state and require only limited information about
the underlying network topology. Unconstrained algorithms utilize more information about the network,
and can achieve better performance. Thus, iterative and unconstrained algorithms achieve different
trade-offs between complexity and performance. The goals of the project include investigation of
the impact of topology control, resource management, and dynamic adaptation on the performance of
the distributed algorithms. The project will improve the understanding of how robust distributed
algorithms can be designed for practical wireless networks. The project will involve undergraduate
and graduate students. The students will gain valuable experience working on distributed computing
problems that are relevant in a variety of applications.
- P.I. - Nitin Vaidya
Graduate research assistant - Lili Su
Graduate research assistant - Zhuolun Xiang
Undergraduate researchers - Simon Peter, Vikram Mudaliar
- Robust Multi-Agent Optimization: Coping with Packet-Dropping Link Failures, Lili Su and Nitin Vaidya, Technical Report, June 2016
A Framework for Evaluating Iterative Algorithms on Distributed Systems, Simon Peter, B.S. Senior Thesis, December 2015 (github site for the code)
- Reaching Approximate Byzantine Consensus with Multi-hop Communication, Lili Su and Nitin Vaidya, 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems. Edmonton, Canada.
- Fault-Tolerant Multi-Agent Optimization: Part III,
Lili Su, Nitin Vaidya, Arxiv, September 2015.
Byzantine Multi-Agent Optimization: Part II,
Lili Su, Nitin Vaidya, Arxiv, July 2015.
Byzantine Multi-Agent Optimization: Part I,
Lili Su, Nitin Vaidya, Arxiv, June 2015.