Campus Event Calendar

Event Entry

What and Who

Cooperative Asynchronous Reading

Dariusz Kowalski
Max-Planck-Institut für Informatik - AG 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5  
AG Audience

Date, Time and Location

Monday, 24 May 2004
30 Minutes
46.1 - MPII


The collect problem for an asynchronous shared-memory system

has the objective for the processors to learn all values of
a collection of shared registers, while minimizing
the total number of read and write operations.

First abstracted by Saks, Shavit, and Woll,
collect is among the standard problems in distributed computing.
The model consists of n asynchronous processes,
each with a single-writer multi-reader register of a polynomial capacity.

The best previously known deterministic solution performs
O(n^{3/2}\log n) reads and writes, and
it is due to Ajtai, Aspnes, Dwork, and Waarts.
I will present a new deterministic algorithm that
performs O(n \log^7 n) read/write operations,
thus substantially improving the best previous upper bound.
Using an approach based on epidemic rumor-spreading, the novelty
of the new algorithm is in using a family of expander graphs
and ensuring that each of the successive groups of processes collect
and propagate sufficiently many rumors to the next group.

This algorithm can be adapted to the Repeatable Collect problem,
which is an on-line distributed version.
The competitive latency of the new algorithm is O(\log^7 n)
vs. the much higher competitive latency O(\sqrt{n}\log n)
given previously by Ajtai et al.

A result of independent interest abstracts a gossiping game that is played on a graph and that gives its payoff in terms of expansion.


Dariusz Kowalski
--email hidden
passcode not visible
logged in users only

Dariusz Kowalski, 05/12/2004 14:24 -- Created document.