Tree Automata for Extracting Consensus from Partial Replicas of a Structured Document
This addresses the challenge of ensuring consistency in collaborative editing workflows where confidentiality restricts access to document parts, though it appears incremental in applying tree automata to this specific domain.
The paper tackles the problem of merging conflicting partial replicas in asynchronous cooperative editing of structured documents by proposing a tree automata-based approach to extract consensus documents, which are the maximum conflict-free prefixes of the merged replicas.
In an asynchronous cooperative editing workflow of a structured document, each of the co-authors receives in the different phases of the editing process, a copy of the document to insert its contribution. For confidentiality reasons, this copy may be only a partial replica containing only parts of the (global) document which are of demonstrated interest for the considered co-author. Note that some parts may be a demonstrated interest over a co-author; they will therefore be accessible concurrently. When it's synchronization time (e.g. at the end of an asynchronous editing phase of the process), we want to merge all contributions of all authors in a single document. Due to the asynchronism of edition and to the potential existence of the document parts offering concurrent access, conflicts may arise and make partial replicas unmergeable in their entirety: they are inconsistent, meaning that they contain conflictual parts. The purpose of this paper is to propose a merging approach said by consensus of such partial replicas using tree automata. Specifically, from the partial replicas updates, we build a tree automaton that accepts exactly the consensus documents. These documents are the maximum prefixes containing no conflict of partial replicas merged.