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.