Reliable Distributed Algorithms for Dynamic Communication in Ad Hoc Networks

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.