Space-Efficient Atomic Snapshots in Synchronous Systems

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/6777

Title: Space-Efficient Atomic Snapshots in Synchronous Systems
Author: Neiger, Gil ; Singh, Ranu
Abstract: We consider the problem of implementing an atomic snapshot memory in synchronous distributed systems. An atomic snapshot memory is an array of memory locations, one per processor. Each processor may update its own location or scan all locations atomically. We are interested in implementations that are space-efficient in the sense that they are honest. This means that the implementation may use no more shared memory than that of the array being implemented and that the memory truly reflect the contents of that array. If n is the number of processors involved, then the worst-case scanning time must be at least n. We show that the sum of the worst-case update and scanning times must be greater than floor(3n/2). We exhibit two honest implementations. One has scans and updates with worst-case times of n+1 for both operations; for scans, this is near the lower bound. The other requires longer scans (with worst-case time ceiling(3n/2)+1) but shorter updates (with worst-case time ceiling(n/2)+1). Thus, both implementations have the sum of the worst-case times at 2n + O(1), which is within n/2 of the lower bound. Closing the gap between these algorithms and the combined lower bound remains an open problem.
Type: Technical Report
URI: http://hdl.handle.net/1853/6777
Date: 1993
Relation: CC Technical Report; GIT-CC-93-46
Publisher: Georgia Institute of Technology
Subject: Algorithms
Array of memory locations
Atomic snapshot memory
Concurrency
Lower bounds
Scanning time
Shared memory
Synchronous distributed systems
Distributed systems

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
GIT-CC-93-46.pdf 181.4Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record