The complexity of updating snapshot objects |
| |
Authors: | Hagit AttiyaAuthor VitaeFaith EllenAuthor Vitae Panagiota FatourouAuthor Vitae |
| |
Affiliation: | a Technion, Israelb University of Toronto, Canadac University of Crete and FORTH ICS, Greece |
| |
Abstract: | This paper proves Ω(m) lower bounds on the step complexity of UPDATE operations for space-optimal wait-free implementations of an m-component snapshot object from historyless objects. These lower bounds follow from lower bounds for a new, more general class of implementations from base objects of any type. This work extends a similar lower bound by Israeli and Shirazi for implementations of m-component single-writer snapshot objects from single-writer registers. |
| |
Keywords: | Snapshots Updates Lower bounds |
本文献已被 ScienceDirect 等数据库收录! |