Robustness to disruption, either unintentional or malicious, is a critical issue in large-scale, decentralized systems. Resource-competitive analysis is a promising algorithmic approach to providing this robustness under challenging fault models. Here, costs are measured in terms of network resources such as computational power, bandwidth, or energy. A resource-competitive algorithm provides guarantees on the cost to a correct device as a function of the cost incurred by the faulty components in the system. Â By designing algorithms that quantify this cost relationship, practitioners can provision networks with sufficient resources to tolerate otherwise catastrophic failures. Furthermore, in many cases, it is even possible to guarantee that faulty devices will deplete their respective resources much faster than correct devices; therefore, any disruption to the system will be short lived. For these reasons, resource-competitive algorithms can play an important role in bolstering fault tolerance in a variety of practical network settings.
This project addresses the following research challenges. First, robust multiple access (MA) protocols for mobile systems are often difficult to design, and this can be further complicated by wireless interference. Energy is a scarce commodity for many mobile devices, and resource-competitive MA protocols are critical in this setting. Second, interactive computation in the wireless domain is fragile given bit errors that arise over unreliable communication channels. Given that bandwidth is constrained, resource-competitive interactive communication is important under random and adversarial bit errors. Third, insider attacks pose a threat to the correctness of many open, decentralized, and dynamic wired networks. In such settings, computational power may be utilized for outvoting malicious users in a resource-competitive fashion. Finally, consensus is a critical building block for many distributed protocols. However, achieving consensus is difficult in wireless sensor networks where battery power is limited and interference can arise due to faulty devices. A robust and resource-competitive consensus algorithm is needed for this setting.
The project has practical impact on the design of robust network, both wired and wireless. Additional broader impacts include curriculum development and research training for undergraduates.
