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.”

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.

- Short abstract from PODC 95 proceedings: PDF.
- STOC 96 proceedings version: PDF.
- ArXiv version: arXiv:cs.DS/0306044.
- Full version:
**PDF**.

@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