Access Restriction

Author Afek, Yehuda ♦ Attiya, Hagit ♦ Dolev, Danny ♦ Gafni, Eli ♦ Merritt, Michael ♦ Shavit, Nir
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1993
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Atomic ♦ Consistent state ♦ Fault-tolerance ♦ Snapshot
Abstract This paper introduces a general formulation of<?Pub Fmt italic>atomic snapshot memory<?Pub Fmt /italic>, a sharedmemory partitioned into words written(<?Pub Fmt italic>updated<?Pub Fmt /italic>) by individual processes, orinstantaneously read (<?Pub Fmt italic>scanned<?Pub Fmt /italic>) in itsentirety. This paper presents three wait-free implementations of atomicsnapshot memory. The first implementation in this paper uses unbounded(integer) fields in these registers, and is particularly easy tounderstand. The second implementation uses bounded registers. Itscorrectness proof follows the ideas of the unbounded implementation.Both constructions implement a single-writer snapshot memory, in whicheach word may be updated by only one process, from single-writer,<?Pub Fmt italic>n<?Pub Fmt /italic>-reader registers. The thirdalgorithm implements a multi-writer snapshot memory from atomic<?Pub Fmt italic>n<?Pub Fmt /italic>-writer,<?Pub Fmt italic>n<?Pub Fmt /italic>-reader registers, again echoing keyideas from the earlier constructions. All operations require&THgr;(<?Pub Fmt italic>n<?Pub Fmt /italic>2) readsand writes to the component shared registers in the worst case.—<?Pub Fmt italic>Authors' Abstract<?Pub Fmt /italic>
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1993-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 40
Issue Number 4
Page Count 18
Starting Page 873
Ending Page 890

Open content in new tab

   Open content in new tab
Source: ACM Digital Library