Adaptive and efficient algorithms for lattice agreement and renaming

Citation
H. Attiya et A. Fouren, Adaptive and efficient algorithms for lattice agreement and renaming, SIAM J COMP, 31(2), 2001, pp. 642-664
Citations number
27
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
642 - 664
Database
ISI
SICI code
0097-5397(20011011)31:2<642:AAEAFL>2.0.ZU;2-1
Abstract
In a shared-memory system, n independent asynchronous processes, with disti nct names in the range {0,..., N-1}, communicate by reading and writing to shared registers. An algorithm is wait-free if a process completes its exec ution regardless of the behavior of other processes. This paper considers w ait-free algorithms whose complexity adjusts to the level of contention in the system: A algorithm is adaptive (to total contention) if its step compl exity depends only on the actual umber of active processes, k; this umber i s unknown in advance and may change in different executions of the algorith m. Adaptive algorithms are presented for two important decision problems, latt ice agreement and (6k-1)-renaming; the step complexity of both algorithms i s O (k log k). An interesting component of the (6k-1)-renaming algorithm is an O(N) algorithm for (2k-1)-renaming; this improves on the best previousl y known (2k-1)-renaming algorithm, which has O ( Nnk) step complexity. The efficient renaming algorithm can be modified into an O (N) implementati on of atomic snapshots using dynamic single-writer multi-reader registers. The best known implementations of atomic snapshots have step complexity O ( N log N) using static single-writer multi-reader registers, and O (N) using multi-writer multi-reader registers.