Compositional competitiveness for distributed algorithms

Details Compositional competitiveness for distributed algorithms Compositional competitiveness for distributed algorithms

2003-06-11

arxiv.org/abs/cs/0306044v1

Computer Science

Data Structures and Algorithms

33 pages, 2 figures; full version of STOC 96 paper titled "Modular competitiveness for distributed algorithms."

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Compositional competitiveness for distributed algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Compositional competitiveness for distributed algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compositional competitiveness for distributed algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-458328