Miklos Ajtai, James Aspnes, Cynthia Dwork, and Orli Waarts. A theory of competitive analysis for distributed algorithms. Thirty-Fifth IEEE Symposium on Foundations of Computer Science, November 1994, pp. 401–411. A brief announcement of this work appeared in Thirteenth ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 1994, under the title “Competitive analysis for distributed algorithms.”
We introduce a theory of competitive analysis for distributed algorithms. The first steps in this direction were made in the seminal papers of Bartal, Fiat, and Rabani, and of Awerbuch, Kutten, and Peleg, in the context of data management and job scheduling. In these papers, as well as in other subsequent work, the cost of a distributed algorithm is compared to the cost of an optimal global-control algorithm. Here we introduce a more refined notion of competitiveness for distributed algorithms, one that reflects the performance of distributed algorithms more accurately. In particular, our theory allows one to compare the cost of a distributed on-line algorithm to the cost of an optimal distributed algorithm.
We demonstrate our method by studying the cooperative collect primitive, first abstracted by Saks, Shavit, and Woll. We present two algorithms (with different strengths) for this primitive, and provide a competitive analysis for each one.
@inproceedings(AjtaiADW1994,
title="A theory of competitive analysis for distributed algorithms",
author="Miklos Ajtai and James Aspnes and Cynthia Dwork and Orli Waarts",
booktitle="Thirty-Fifth IEEE Symposium on Foundations of Computer Science",
month=nov,
year=1994,
pages={401--411}
)