Long-lived adaptive collect with applications

A distributed algorithm is adaptive if the worst case step complexity of its operations is bounded by a function of the number of processes that are concurrently active during the operation (rather than a function of N, the total number of processes, which is usually much larger). We present long-li...

Full description

Saved in:
Bibliographic Details
Main Authors: Afek, Y., Stupp, G., Touitou, D.
Format: Conference Proceeding
Language:English
Subjects:
Adaptive algorithm
Application software
Computer science
Electrical capacitance tomography
Particle measurements
Read-write memory
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A distributed algorithm is adaptive if the worst case step complexity of its operations is bounded by a function of the number of processes that are concurrently active during the operation (rather than a function of N, the total number of processes, which is usually much larger). We present long-lived and adaptive algorithms for collect in the read/write shared-memory model. Replacing the reads and writes in long-lived shared memory algorithms with our adaptive collect results in many cases in a corresponding long-lived algorithm which is adaptive. Examples of such applications, which are discussed are atomic-snapshots, and l-exclusion. Following the long-lived and adaptive collect we present a more pragmatic version of collect, called active set. This algorithm is slightly weaker than the collect but has several advantages. We employ this algorithm to transform algorithms, such as the Bakery algorithm, into their corresponding adaptive long-lived version, which is more efficient than the version that was obtained with the collect. Previously, long-lived and adaptive algorithms in this model were presented only for the renaming problem.
ISSN:0272-5428
DOI:10.1109/SFFCS.1999.814598