Reliable Distributed Algorithms for Dynamic Communication in Ad Hoc Networks

Lead Research Organisation: University of Liverpool
Department Name: Computer Science

Abstract

The last several years has seen a substantial increase in the deployment of wireless networks as a result of the growth in popularity of mobile laptops, cell phones, PDAs, and sensor devices. Despite the unquestionable advantages of wireless communication, there are also significant new challenges posed by this development. One of them is to handle the mobility of devices, other is to overcome the impact of various kinds of failures that are common in wireless environment. The examples of typical faults are:(1) unreliable communication: in real-world deployments, electromagnetic interference is ubiquitous and can often prevent communication; (2) fault-prone devices: wireless devices are often small, fragile, and have limited battery life, resulting in frequent devices failures; (3) malicious network disruption: wireless device networks are often deployed in public venues, facilitating easy attacks.Malicious adversaries pose a particularly great threat to wireless networks: the sharednature of the communication medium allows an adversary to disrupt or prevent anyinformation exchange between honest processes by ``jamming'' the channel with noise or by propagating corrupted data instead.In this project we address the problem of reliable and efficient communication in wireless networks prone to failures. Such communication is typically dynamic, which means that communication tasks are generated in ad hoc manner by applications run by the devices. Network topology is also ad hoc, due to the mobility of devices. All these issues, together with various kinds of failures, raise a complex challenge for protocol designers. In this context, we plan to address fundamental communication tasks, such asrouting, information dissemination and aggregation (e.g., broadcast, convergecast), information exchange (e.g., gossip, group communication), as well as related problems such as agreement and leader election. There has been relatively little work done on development and analysis of algorithms for fault-prone wireless environments, especially in the presence of malicious adversaries.Moreover, all these works consider only static communication, i.e., where there is only one task triggered by each device. Such an assumption is a significant simplification of more realistic scenarios, where the tasks may interfere with each other. The main goal of this project is to develop new algorithmic techniques, accompanied by a comprehensive theoretical analysis and simulations, for coping with unreliable dynamic communication, faulty devices, and malicious disruption in ad hoc wireless networks.More specific objectives include:(a) development of a more comprehensive theoretical model for dynamic communication in fault-prone ad hoc wireless networks,(b) design of new algorithms for fundamental communication problems, and(c) evaluation of new algorithmic solutions in the theoretical model and through software simulations, followed by comparison with widely used wireless protocols.This project focuses on development of algorithmic foundations of reliable and dynamic communication in ad hoc wireless networks. A complementary, more engineering-oriented approach, is not addressed in this proposal.The expertise of Dr. Kowalski in the algorithmic aspects of fault-tolerant distributed computing, network communication and mobile computing, as well as the broad network of collaborating research groups and individual researchers, is key to the success of the proposed project. It is expected that new developments within this project will improve reliability and stability of communication protocols forming a part of future wireless distributed systems.

Publications

10 25 50
publication icon
Anantharamu L (2016) Adversarial Multiple Access Channels with Individual Injection Rates in Theory of Computing Systems

publication icon
Bienkowski M (2016) Randomized mutual exclusion on a multiple access channel in Distributed Computing

publication icon
Bienkowski M (2018) Distributed Online and Stochastic Queueing on a Multiple Access Channel in ACM Transactions on Algorithms

publication icon
Chlebus B (2015) Stability of adversarial routing with feedback in Networks

publication icon
Chlebus B (2012) Adversarial Queuing on the Multiple Access Channel in ACM Transactions on Algorithms

publication icon
Cholvi V (2010) Bounds on Stability and Latency in Wireless Communication in IEEE Communications Letters

publication icon
Czyzowicz J (2011) Consensus and Mutual Exclusion in a Multiple Access Channel in IEEE Transactions on Parallel and Distributed Systems

 
Description 1. We introduced alternative models of studying different aspects of dynamic and fault-tolerant wireless communication:
- Unrestricted packet arrivals (extending previously used stochastic and restricted arrivals) [DISC 2012]
- Adversarial jamming [INFOCOM 2009], [DISC 2010]
- Dynamic crash-and-restart [PODC 2010]
- Power-sensitive model [ICDCS 2010]
2. We re-defined classical algorithmic problems and introduced new ones (e.g., continuous gossip), corresponding to novel wireless technologies (e.g., online group communication services). We also proved computational bounds for them in the proposed models, see the work cited in Objective 1.
3. We studied performance of existing fundamental protocols in the proposed models, including backoff protocols [INFOCOM 2010], token-based protocols [Distributed Computing 2009], and protocols based on codes, called selectors [INFOCOM 2009].
4. We developed and analysed several provably efficient protocols and general algorithmic techniques, applicable in dynamic and fault-prone wireless networks, for example:
- Single-hop broadcast protocol SCAT [DISC 2012]
- Multi-hop leader election and multi-broadcast protocols [ICALP 2009], [ICALP 2011]
5. We performed simulations for some dynamic algorithms achieving the best theoretical performance and compared them with currently used protocols. Many new protocols substantially outperformed the old ones, c.f., [INFOCOM 2010].
Exploitation Route To produce better wireless communication protocols, which are stable in large scale dynamic fault-prone systems, even in worst-case scenarios.
Sectors Digital/Communication/Information Technologies (including Software)

URL http://www.csc.liv.ac.uk/~darek/ReDiAl.html
 
Description Congested communication 
Organisation Tel Aviv University
Country Israel 
Sector Academic/University 
PI Contribution Joint collaboration with Prof. Boaz Patt-Shamir. Prof. Kowalski's grant was used for hosting Prof. Patt-Shamir's research visits at U. Liverpool.
Collaborator Contribution Joint collaboration with Prof. Boaz Patt-Shamir.
Impact Submitted manuscript on computing in environment with congested links.
Start Year 2008
 
Description Distributed algorithms 
Organisation Swiss Federal Institute of Technology in Lausanne (EPFL)
Country Switzerland 
Sector Public 
PI Contribution Joint collaboration with Prof. Rachid Guerraoui. Prof. Kowalski's grant was used for research visiting Prof. Guerraoui at EPFL.
Collaborator Contribution Joint collaboration with Prof. Rachid Guerraoui.
Impact Joint papers on distributed algorithms, including consensus, communication and multi-channel distributed allocation.
Start Year 2008
 
Description Radio broadcast 
Organisation University of Colorado Denver
Country United States 
Sector Academic/University 
PI Contribution Joint collaboration with Prof. Bogdan Chlebus, resulted in a number of published papers and follow up papers. Prof. Kowalski's grants were used for hosting Prof. Chlebus' research visits at U. Liverpool.
Collaborator Contribution Joint collaboration with Prof. Bogdan Chlebus, resulted in a number of published papers and follow up papers. Prof. Chlebus' grants were used for hosting Prof. Kowalski's research visits at U. Colorado.
Impact A number of reported papers co-authored by Prof. Kowalski and Prof. Chlebus.