kernel.core.movic
The MOVIC algorithm introduced by Sun and Chen, 2002 for handling conflicting operations.
The MOVIC algorithm judges all received operations for conflict potential and groups compatible operations into a MCGS (maximum compatible group set). The constructed MCGS is guaranteed to converge across all sites.
The algorithm is copied verbatim from Sun and Chen, 2002, with one major exception: A different conflict/compatible relation is used (kernel.core.conflict-relation) which has been designed specifically for detecting feature modeling conflicts.
Also, we do not distinguish different objects in a document as Sun and Chen, but consider only one global object, the feature model (instead of, say, single features). This is because features may have arbitrary complex relationships which can not simply be divided in unrelated objects.
MCG-ID
(MCG-ID MCG)Returns a string that uniquely identifies an MCG (up to hash collisions). In deviation to Sun and Chen’s original paper, we do not use the COID scheme for identification. This is easier to implement, but has the disadvantage that MCGs can not be identified as they evolve - when an operation arrives that is inserted into MCG to produce MCG’, the identifiers of MCG and MCG’ are in no obvious relation to each other. Consequently, versions may “jump” in the user interface until synchronization. We may come back to COID if this turns out to be a problem.
MCGs
(MCGs MCGS)Returns all MCGs contained in an MCGS. This is, in the trivial implementation, just the MCGS.
MCGS-initialize
(MCGS-initialize)Creates an empty MCGS. Serves as a starting point for the MOVIC algorithm.
MCGS-remove
(MCGS-remove MCGS CO-ID)Removes an operation from every MCG in the MCGS in O(n) for n MCGs.
MOVIC
(MOVIC MCGSi-1 Oi CDAG HB base-FM CC&)Incrementally constructs an MCGS independent of operation ordering.
The constructed MCGS has the following properties:
- Every CG consists of mutually compatible operations.
- Every operation used for construction occurs in at least one CG.
- Any group of compatible operations occurs together in at least one CG.
- Any two CGs contain at least one pair of conflicting operations.
The algorithm makes use of atoms, @ and swap! to mutate local variables. No arguments are mutated (except for the conflict cache).
Operations are identified by their IDs, so two different operations with the same parameters will still compare as different due to their IDs. Here, operations are identified by equality, this is okay as long as no transformation of operations is used (because then operations may be classified as different).
An MCGS only contains operation IDs. Operation metadata is looked up in the history buffer.
The CDAG, HB, base-FM and CC& arguments are passed down as context for the conflict detection. The history buffer is used to obtain operation metadata for conflict detection.