A Lazy Snapshot Algorithm with Eager Validation
Research output: Contribution to conferences › Paper › Contributed › peer-review
Contributors
Abstract
Most high-performance software transactional memories
(STM) use optimistic invisible reads. Consequently, a transaction might
have an inconsistent view of the objects it accesses unless the consistency
of the view is validated whenever the view changes. Although all STMs
usually detect inconsistencies at commit time, a transaction might never
reach this point because an inconsistent view can provoke arbitrary be-
havior in the application (e.g., enter an infinite loop). In this paper, we
formally introduce a lazy snapshot algorithm that verifies at each object
access that the view observed by a transaction is consistent. Validating
previously accessed objects is not necessary for that, however, it can be
used on-demand to prolong the view’s validity. We demonstrate both
formally and by measurements that the performance of our approach is
quite competitive by comparing other STMs with an STM that uses our
algorithm.
(STM) use optimistic invisible reads. Consequently, a transaction might
have an inconsistent view of the objects it accesses unless the consistency
of the view is validated whenever the view changes. Although all STMs
usually detect inconsistencies at commit time, a transaction might never
reach this point because an inconsistent view can provoke arbitrary be-
havior in the application (e.g., enter an infinite loop). In this paper, we
formally introduce a lazy snapshot algorithm that verifies at each object
access that the view observed by a transaction is consistent. Validating
previously accessed objects is not necessary for that, however, it can be
used on-demand to prolong the view’s validity. We demonstrate both
formally and by measurements that the performance of our approach is
quite competitive by comparing other STMs with an STM that uses our
algorithm.
Details
Original language | English |
---|---|
Number of pages | 15 |
Publication status | Published - 2006 |
Peer-reviewed | Yes |
Conference
Title | 20th International Symposium on Distributed Computing (DISC '06), Springer-Verlag, 2006. |
---|---|
Abbreviated title | DISC '06 |
Conference number | |
Duration | 18 September 2006 |
Degree of recognition | International event |
Location | |
City | Stockholm |
Country | Sweden |