"Collective Reading from Shared Memory"

                Bogdan S. Chlebus
        University of Colorado at Denver

Abstract:

The n-process Collect problem requires each asynchronous process
to learn all values stored in n registers,
where the capacity of each register is large enough
to store the contents of the initial values in all n registers.
Collect was first abstracted by Saks, Shavit, and Woll in 1991,
and it is among the standard problems in distributed computing.
This work presents a new deterministic algorithm
that solves instances of the Collect problem
with the total of O(n log^8 n) read and write operations
on single-writer multi-reader registers.
The best previously known deterministic solution
performed O(n^{3/2} log n) reads and writes,
and it is due to Ajtai, Aspnes, Dwork, and Waarts.

These results are obtained by taking a novel approach
to structuring algorithms solving Collect.
Its essential part is a communication scheme based on expander graphs.
The presentation starts by giving a randomized algorithm and its analysis
against a strong adversary that knows all the random bits prior
to the start of an execution.
This analysis is sufficiently strong to obtain a deterministic algorithm
by applying the probabilistic method.
The new Collect solution can be interpreted as a rumor-spreading computation.
The result described in this talk measures the flow of information
in an execution by abstracting a gossiping game played on a graph,
and analyzing its payoff in terms of the expansion of the graph.

This is a joint work with:
Dariusz R. Kowalski (Warsaw University) and
Alex A. Shvartsman (University of Connecticut).