Abstract
The Write-All problem for an asynchronous shared-memory system has the objective for the processes to update the contents of a set of shared registers, while minimizing the total number of read and write operations. First abstracted by Kanellakis and Shvartsman [12], Write-All is among the standard problems in distributed computing. The model consists of n asynchronous processes and n registers, where every process can read and write to any register. Processes may fail by crashing. The most efficient previously known deterministic algorithm performs O(n1+ε) reads and writes, for an arbitrary fixed constant ε > 0, and is due to Anderson and Woll [4], This paper presents a new deterministic algorithm that performs O(n polylog n) read/write operations, thus improving the best previously known upper bound from polynomial to polylogarithmic in the average number of read/write operations per process. Using an approach to store and retrieve information about progress made in auxiliary registers, the novelty of the new algorithm is in using a family of multi-partite graphs with expansion properties to structure a set of registers as a graph and then have each asynchronous process explore a part of the graph according to its pattern of traversals. An explicit instantiation of our Write-All algorithm, based on best-known polynomial-time constructions of lossless expanders and a-expanding graphs, performs n · 2O (log3 logn) reads and writes. In this explicit solution to Write-All, the processes perform asymptotically less read/write operations than the most efficient non-explicit solution known before.
Original language | English (US) |
---|---|
Pages (from-to) | 733-739 |
Number of pages | 7 |
Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |
DOIs | |
State | Published - 2005 |
Externally published | Yes |
Event | 13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States Duration: Nov 7 2005 → Nov 11 2005 |
Keywords
- Asynchrony
- Disperser
- Distributed algorithm
- Expander
- Problem Write-All
- Read and write register
- Work efficiency
ASJC Scopus subject areas
- Software