Partial updates. (English) Zbl 1080.68020
Summary: 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.
MSC:
| 68P05 | Data structures |
| 68Q60 | Specification and verification (program logics, model checking, etc.) |
Keywords:
Abstract state machines; Applicative algebra; AsmL; Parallel composition; Sequences; Transactions; UpdatesReferences:
| [1] | E. Allman, An Introduction to the Source Code Control System, University of California at Berkeley, Working paper, 1980.; E. Allman, An Introduction to the Source Code Control System, University of California at Berkeley, Working paper, 1980. |
| [2] | The ASM academic web page,; The ASM academic web page, |
| [3] | B. Berliner, CVS II: Parallelizing Software Development, Proc. Winter 1990 USENIX Association Conf., 1990.; B. Berliner, CVS II: Parallelizing Software Development, Proc. Winter 1990 USENIX Association Conf., 1990. |
| [4] | G. Birkhoff, Lattice Theory, Colloquium Publications XXV, 3rd ed., American Mathematical Society, Providence, RI, 1967.; G. Birkhoff, Lattice Theory, Colloquium Publications XXV, 3rd ed., American Mathematical Society, Providence, RI, 1967. · Zbl 0153.02501 |
| [5] | Börger, E.; Stärk, R., Abstract State MachinesA Method for High-Level System Design and Analysis (2003), Springer: Springer Berlin, Heidelberg · Zbl 1040.68042 |
| [6] | C.A. Ellis, S.J. Gibbs, Concurrency control in groupware systems, Proc. ACM SIGMOD Conf. on Management of Data, May 1989, pp. 399-407.; C.A. Ellis, S.J. Gibbs, Concurrency control in groupware systems, Proc. ACM SIGMOD Conf. on Management of Data, May 1989, pp. 399-407. |
| [7] | The web page of the group on Foundations of Software Engineering at Microsoft Research,; The web page of the group on Foundations of Software Engineering at Microsoft Research, |
| [8] | GNU, Comparing and Merging Files, Edition 2.8.1, dated 5 April 2002,; GNU, Comparing and Merging Files, Edition 2.8.1, dated 5 April 2002, |
| [9] | Gurevich, Y., Evolving Algebra 1993Lipari Guide, (Börger, E., Specification and Validation Methods (1995), Oxford University Press: Oxford University Press Oxford), 9-36 · Zbl 0852.68053 |
| [10] | Gurevich, Y.; Tillmann, N., Partial updatesexploration, Springer J. Univ. Comput. Sci., 7, 11, 917-951 (2001) |
| [11] | Microsoft Word, Comparing and Merging Documents,; Microsoft Word, Comparing and Merging Documents, |
| [12] | M. Ressel, D. Nitsche-Ruhland, R. Gunzenhauser, An integrating, transformation-oriented approach to concurrency control and undo in group editors, Proc. ACM Conf. on Computer Supported Cooperative Work, 1996, pp. 288-297.; M. Ressel, D. Nitsche-Ruhland, R. Gunzenhauser, An integrating, transformation-oriented approach to concurrency control and undo in group editors, Proc. ACM Conf. on Computer Supported Cooperative Work, 1996, pp. 288-297. |
| [13] | M. Suleiman, M. Cart, J. Ferrié, Serialization of concurrent operations in distributed collaborative environment, Proc. ACM Internat. Conf. on Supporting Group Work (GROUP’97), Phoenix, November 1997, pp. 435-445.; M. Suleiman, M. Cart, J. Ferrié, Serialization of concurrent operations in distributed collaborative environment, Proc. ACM Internat. Conf. on Supporting Group Work (GROUP’97), Phoenix, November 1997, pp. 435-445. |
| [14] | C. Sun, C. Ellis, Operational transformation in real-time group editors: issues, algorithms, and achievements, Proc. ACM Conf. on Computer-Supported Cooperative Work, The ASM academic web page,; C. Sun, C. Ellis, Operational transformation in real-time group editors: issues, algorithms, and achievements, Proc. ACM Conf. on Computer-Supported Cooperative Work, The ASM academic web page, |
| [15] | Sun, C.; Jia, X.; Zhang, Y.; Yang, Y.; Chen, D., Achieving convergence, causality-preservation, and intention-preservation in real-time cooperative editing systems, ACM Trans. Computer-Human Interaction, 5, 1, 63-108 (1998) |
| [16] | W.F. Tichy, Design, implementation and evaluation of a revision control system, Proc. 6th Internat. Conf. on Software Engineering, IEEE, Tokyo, September 1982.; W.F. Tichy, Design, implementation and evaluation of a revision control system, Proc. 6th Internat. Conf. on Software Engineering, IEEE, Tokyo, September 1982. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
