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

在大规模分散系统中，对意外或恶意中断的健壮性是一个关键问题。资源竞争分析是一种很有前途的算法方法，可以在具有挑战性的故障模型下提供这种健壮性。这里，成本是根据计算能力、带宽或能量等网络资源来衡量的。资源竞争算法根据系统中故障部件所产生的成本，对正确设备的成本提供保证。通过设计量化这种成本关系的算法，从业者可以为网络提供足够的资源，以容忍其他灾难性的故障。此外，在许多情况下，甚至可以保证故障设备耗尽各自资源的速度比正常设备快得多；因此，对系统的任何中断都将是短暂的。基于这些原因，在各种实际网络环境中，资源竞争算法可以在增强容错能力方面发挥重要作用。首先，用于移动系统的健壮的多址(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.