RIA: The Competitive Analysis of Distributed Algorithms

本研究将竞争分析技术（最初用于研究在线算法）应用于具有不可预测故障的分布式系统的算法设计。竞争分析将算法的性能与最优的“离线”算法设计者的性能进行比较，从而有效地预测未来。使用它，算法设计者可以避免为最坏情况设计的危险（在较温和的条件下产生的算法效率太低而不实用）或为可能与现实很少对应的正常情况设计的危险。(1)该项目的第一项任务是制定适用于竞争分析的分布式算法的性能指标（这项任务的惊人困难可能解释了为什么以前对分布式问题的竞争分析的应用主要集中在这些问题的在线方面）。(2)二是构建在竞争度量下表现良好的分布式算法。通过实现这些算法，可以测试这些度量是否确实预测了良好的实际性能。这项工作将产生对分布式算法理论的见解，并为分布式系统构建者提供更好的实用算法。

This research applies the technique of competitive analysis, originally developed to study on-line algorithms, to the design of algorithms for distributed systems with unpredictable failures. Competitive analysis compares the performance of an algorithm with that of an optimal ``off-line'' algorithm designer in effect to predict the future. Using it, an algorithm designer can avoid the perils of designing for the worst case (yielding algorithms too inefficient under milder conditions to be practical) or for a normal case that may turn out to have little correspondence with reality. (1) The first task of the project is to formulate performance measures for distributed algorithms that are amenable to competitive analysis (the surprising difficulty of this task may explain why previous applications of competitive analysis to distributed problems have largely concentrated on the on-line aspects of those problems). (2) The second is to construct distributed algorithms that perform well by the competitive measures. By implementing these algorithms it is possible to test that the measures do in fact predict good real-world performance. This work will yield both insights into the theory of distributed algorithms and better practical algorithms for the distributed system builder.