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. – Prof. Haitham Hassanieh
- The following personnel have participated in the
activities of this project from its inception.
Prof. Haitham Hassanieh
Prof. Nitin Vaidya
Graduate students: Lili Su, Zhuolun Xiang, Shripad Gade, Jiaming Wang, Surj Jog, Junfeng Guan.
Undergraduate students: Simon Peter, Vikram Mudaliar,
Suriya Kodeswaran, Joshua Lew, Larry Liu, Zitong Chen, Ruichun Ma
Post-doc: Pooja Vyavahare
- Publications
- Defending non-Bayesian learning against adversarial attacks
Lili Su, Nitin H. Vaidya
Distributed Computing 32(4), August 2019
- Exact Byzantine Consensus on Undirected Graphs under Local Broadcast Model
Muhammad Samir Khan, Syed Shalan Naqvi, Nitin H. Vaidya
ACM Symposium on Principles of Computing (PODC), July-August 2019
- Distributed Learning over Time-Varying Graphs with Adversarial Agents. Pooja Vyavahare, Lili Su, Nitin H. Vaidya. FUSION 2019: 1-8
- Distributed Learning with Adversarial Agents Under Relaxed Network Condition.
Pooja Vyavahare, Lili Su, Nitin H. Vaidya:
CoRR abs/1901.01943 (2019)
- Effects of
Topology Knowledge and Relay Depth on Asynchronous Approximate Consensus,
Dimitris Sakavalas, Lewis Tseng, Nitin H.
Vaidya, OPODIS 2018.
-
Brief Announcement: Effects of Topology Knowledge and Relay Depth on Asynchronous
Consensus, Dimitris Sakavalas, Lewis Tseng, Nitin Vaidya, 32nd
International Symposium on Distributed Computing (DISC), October 2018.
-
Effects of
Topology Knowledge and Relay Depth on Asynchronous Consensus, Dimitris Sakavalas, Lewis Tseng, Nitin H. Vaidya, May 2018, arXiv:1803.04513.
- A framework for
implementing interactive algorithms on distributed systems, Vikram Mudaliar, B.S.
Thesis, 2017.
-
Lili Su. Defending Distributed Systems Against Adversarial Attacks: Consensus, Consensus¬based Learning, and Statistical Learning. (2017). University of Illinois at Urbana-Champaign.
-
Lili Su and Nitin Vaidya (2016). Fault-Tolerant Multi-Agent Optimization: Optimal Distributed Algorithms. ACM Symposium on Principles of Distributed Computing.
- Lili Su and Nitin Vaidya (2016). Robust Multi-agent Optimization: Coping with Byzantine Agents with Input Redundancy. 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems.
- 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.
- Code:
A Framework for Evaluating Iterative Algorithms on Distributed Systems.
- Broader Impact:
-
Provided research opportunities for 1 postdoc, 6 graduate students, and 7 undergraduate students.
-
Code open sourced and made available online.
-
Work disseminated through many paper publications, presentations at conferences and invited talk.
-
Some results incorporated into Distributed Systems Class at UIUC. Course material can be found here.
-
Organized an online Distributed Computing Seminar Series.