A Lazy Snapshot Algorithm with Eager Validation (bibtex)
by Torvald Riegel, Pascal Felber, Christof Fetzer
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 behavior 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.
Reference:
A Lazy Snapshot Algorithm with Eager Validation (Torvald Riegel, Pascal Felber, Christof Fetzer), In 20th International Symposium on Distributed Computing (DISC '06), Springer-Verlag, 2006. (The final publication is available at www.springerlink.com)
Bibtex Entry:
@inproceedings{riegel2006lsa,
	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 behavior 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.},
	Address = {Berlin, Heidelberg},
	Author = {Torvald Riegel and Pascal Felber and Christof Fetzer},
	Booktitle = {20th International Symposium on Distributed Computing (DISC '06)},
	Doi = {10.1007/11864219_20},
	Month = {September},
	Publisher = {Springer-Verlag},
	Title = {A Lazy Snapshot Algorithm with Eager Validation},
	Year = {2006},
        Comment = {The final publication is available at www.springerlink.com}}
Powered by bibtexbrowser