Sun Mon Tue Wed Thu Fri Sat 1 2 3 4 5 6 7 8 |

If two users in isolation move nodes around, such that the tree remains well organized, it is not always possible to merge their changes without the tree falling apart in two or more pieces. Of course, there is already a problem when both users move the same node to a different parent. Combining the moves of two users is similar to one user being allowed to make two moves at the same time. The clasical example is tree, using the prefix with children between brackets notation: A(B(C),D(E)), where one user moves D under C, resulting in the tree A(B(C(D(E)))), and the other user moves B under E, resulting in the tree A(D(E(B(C)))). When both moves are combined (merged), this results in a lonely A node and an cycle consisting of B, C, D, and E.

There is no additional complexity in merging the moves of more than two users. In case there is a problem with merging the results of more than two users, there is always a minimal set of users whoes moves cannot be merged. Minimal in the sense that there is no subset of this set which cannot be merged. Because of this one could divide the users of the minimal set in two (non-empty) groups that can be merged. Merging the combined moves of these two groups is similar to the two user problem. It should be noted that it is possible that a large group of user could be combined without problems. Taking the above example, lets assume that there is a third user who moves E to A resulting in the tree A(B(C),D,E). Combining the moves of these tree users results in the tree A(E(B(C(D)))). There are good reasons to require that the moves of a set of users can only merged if any subset (of at least two users) can be merged into a proper tree. One reason being that if this requirement is stated, the moves of the users can be pairwise merged in any order.

The design of a locking mechanism to enforce that moves being made by a group of users can always be merged in any possible order, is far from trivial, especially if it needs to be efficient in time and space. There is a whole range of fine-grained to coarse-grained locking mechanism. One should take into the likelihood of multiple users applying moves to the same part of the tree. It is useless to implement an expensive fine-grained locking mechanism if the likelihood is low.

- 8: Whitebox: Handheld SDR
- 8: A possible close supermassive black-hole binary in a quasar with optical periodicity
- 21: Mathematicians prove the Umbral Moonshine Conjecture
- 22: Paradoxes of cosmological physics in the beginning of the 21-st century

Home | December 2014 | February 2015