Partial updates

Yuri Gurevich and Nikolai Tillmann

Abstract

A datastructure instance, e.g. a set or file or record, may be modified independently by different parts of a computer system. The modifications may be nested. Such hierarchies of modifications need to be efficiently checked for consistency and integrated. This is the problem of partial updates in a nutshell. In our first paper on the subject, we developed an algebraic framework which allowed us to solve the partial update problem for some useful datastructures including counters, sets and maps. These solutions are used for the efficient implementation of concurrent data modifications in the specification language AsmL. The two main contributions of this paper are (i)~a more general algebraic framework for partial updates and (ii)~a solution of the partial update problem for sequences and labeled ordered trees.

Details

Publication typeArticle
Published inTheor. Comput. Sci.
Pages311-342
Volume336
Number2-3
SeriesLNCS
PublisherSpringer Verlag

Previous versions

Yuri Gurevich and Nikolai Tillmann. Partial Updates Exploration II, Springer Verlag, 2003.

> Publications > Partial updates