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.