James Aspnes. Competitive analysis of distributed algorithms. Invited survey paper, Dagstuhl-Seminar on On-line Algorithms, Schloss Dagstuhl, June 23–28, 1996. In Amos Fiat, Gerhard Woeginger, eds., Online Algorithms: The State of the Art, Lecture Notes in Computer Science 1442, Springer-Verlag, 1998, pp. 118–146.
Most applications of competitive analysis have involved on-line problems where a candidate on-line algorithm must compete on some input sequence against an optimal off-line algorithm that can in effect predict future inputs. Efforts to apply competitive analysis to fault-tolerant distributed algorithms require accounting for not only this input nondeterminism but also system nondeterminism that arises in distributed systems prone to asynchrony and failures. This paper surveys recent efforts to adapt competitive analysis to distributed systems, and suggests how these adaptations might in turn be useful in analyzing a wider variety of systems. These include tools for building competitive algorithms by composition, and for obtaining more meaningful competitive ratios by limiting the knowledge of the off-line algorithm.
Full version: PDF.
@incollection(Aspnes1998competitive,
title="Competitive analysis of distributed algorithms",
author="James Aspnes",
booktitle="Online Algorithms: The State of the Art",
editor="Amos Fiat and Gerhard Woeginger",
series={Lecture Notes in Computer Science},
volume=1442,
publisher="Springer-Verlag",
year=1998,
pages={118--146}
)