The complexity of updating snapshot objects

This paper proves Ω(m)Ω(m) lower bounds on the step complexity of UPDATE operations for space-optimal wait-free implementations of an mm-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 mm-component single-writer snapshot objects from single-writer registers.

▸Ω(m)Ω(m) lower bounds on the step complexity of UPDATE for mm-components binary snapshot implementations. ▸ Applies to implementations using only mm historyless objects. ▸ Applies to implementations where UPDATES to different components modify disjoint sets of objects. ▸ Improves previous lower bounds for snapshots over an infinite domain, implemented using only single-writer registers.