AF:Small:Resource-Competitive Algorithms for Building Robust Distributed Systems

对破坏的稳健性，无论是无意的还是恶意的，都是大规模分散系统的关键问题。资源竞争分析是一种很有前途的算法方法，可以在具有挑战性的故障模型下提供这种鲁棒性。在这里，成本是根据计算能力、带宽或能源等网络资源来衡量的。资源竞争算法以系统中故障部件所产生的成本为函数，保证正确设备的成本。通过设计量化这种成本关系的算法，从业者可以为网络提供足够的资源来容忍灾难性的故障。此外，在许多情况下，甚至可以保证故障设备将比正确设备更快地耗尽各自的资源；因此，对系统的任何破坏都将是短暂的。由于这些原因，资源竞争算法可以在各种实际网络设置中发挥重要作用，以增强容错能力。该项目解决了以下研究挑战。首先，用于移动系统的健壮的多址（MA）协议通常很难设计，而无线干扰会使这进一步复杂化。对于许多移动设备来说，能源是一种稀缺的商品，在这种情况下，资源竞争的MA协议至关重要。其次，无线领域的交互计算是脆弱的，因为在不可靠的通信信道上出现了比特错误。在带宽受限的情况下，在随机和对抗性误码情况下，资源竞争的交互通信非常重要。第三，内部攻击对许多开放、分散和动态有线网络的正确性构成威胁。在这种情况下，可以利用计算能力以资源竞争的方式击败恶意用户。最后，共识是许多分布式协议的关键构建块。然而，在无线传感器网络中，由于电池电量有限，并且由于故障设备可能会产生干扰，因此很难达成共识。在这种情况下，需要一个鲁棒的、资源竞争的共识算法。本课题对鲁棒网络的设计具有实际意义，无论是有线网络还是无线网络。其他更广泛的影响包括课程开发和本科生的研究培训。

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.