Compositional competitiveness for distributed algorithms

James Aspnes and Orli Waarts. Compositional competitiveness for distributed algorithms. Journal of Algorithms 54(2):127–151, February 2005. Available as arXiv:cs.DS/0306044. An earlier version appeared in Twenty-Eighth Annual ACM Symposium on Theory of Computing, May 1996, pp. 237–246, under the title “Modular competitiveness for distributed algorithms.” A brief announcement of this work appeared in Fourteenth Annual ACM Symposium on Principles of Distributed Computing, August 1995, p. 252, under the title “A modular measure of competitive performance for distributed algorithms.”

Abstract

We define a measure of competitive performance for distributed algorithms based on throughput, the number of tasks that an algorithm can carry out in a fixed amount of work. This new measure complements the latency measure of Ajtai et al., which measures how quickly an algorithm can finish tasks that start at specified times. The novel feature of the throughput measure, which distinguishes it from the latency measure, is that it is compositional: it supports a notion of algorithms that are competitive relative to a class of subroutines, with the property that an algorithm that is k-competitive relative to a class of subroutines, combined with an l-competitive member of that class, gives a combined algorithm that is kl-competitive.

In particular, we prove the throughput-competitiveness of a class of algorithms for collect operations, in which each of a group of n processes obtains all values stored in an array of n registers. Collects are a fundamental building block of a wide variety of shared-memory distributed algorithms, and we show that several such algorithms are competitive relative to collects. Inserting a competitive collect in these algorithms gives the first examples of competitive distributed algorithms obtained by composition using a general construction.

BibTeX

Download
@article(AspnesW2005compositional,
title="Compositional competitiveness for distributed algorithms",
author="James Aspnes and Orli Waarts",
journal={Journal of Algorithms},
volume=54,
number=2,
pages={127--151},
month=feb,
year=2005
)

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page