NSF Award 1421918
NeTS: Small: Impact of Wireless Network Characteristics on Distributed Computation

• Abstract: 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
  
  
• Publications
  • A framework for implementing interactive algorithms on distributed systems, Vikram Mudaliar, B.S. Thesis, 2017
  • 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.