A Deadlock-free Multi-granular, Hierarchical Locking Scheme for Real-time Collaborative Editing Jon A. Preston Sushil K.

Prasad

Agenda
Motivation Related Work in Collaborative Editing Systems The Tree Data Structure Properties and Algorithms
InsertUser (with demotion) RemoveUser (with promotion)

Conclusions and Future Work

2 of 25

Motivation
Collaborative Editing Systems (CES) concurrency control falls into two approaches
Optimistic Pessimistic

Our scheme is a hybrid of these approaches

Avoid transformation/merge problems of optimistic Provide high level of concurrency/access

Locking is automatic (transparent to user)

3 of 25

Related Work
Increase parallelism in software engineering [10] and avoid bottleneck of traditional CMS [3] Avoids explicit turn-taking or system-specific approach [1], [11], and [12] Transparent to user [4], [5], [6], and [13] Avoids the merge problem [8] Provides multi-granular, hierarchical locking [7] Flexible, open-systems, Web-services based approach [2], [14] and [15]

4 of 25

The Tree Structure

Structure denotes sections and sub-sections Only leaf nodes contain satellite data All access requests from client will reference a specific leaf node (as the client knows only of document content, not tree) Nodes store ownership/lock information
If a section of the document is owned by a user u, then all subsections (i.e. child nodes in the tree) are also owned by the same user u. Similarly, if a section of the document is not owned by any user, then all subsections (i.e. child nodes in the tree) are also not owned by any.

5 of 25

Mappings
It is possible to map a document to a tree and from this tree to a binary tree Without loss of generality, our algorithms work on this binary tree
Title (tartif) Paragraph A (pa) Title A1 (ta1) Paragraph A1 (pa1) Paragraph A11 (pa11) Paragraph A12 (pa12) Paragraph A2 (pa2) Paragraph A3 (pa3) Paragraph B (pb)
6 of 25 tartif tartif pa pb pa ta1 pa1 pa2 pa3 pb

ta1 pa1
pa11

pa2

pa3

pa11

pa12

pa12

Maintaining the Largest Sub-tree

It is desirable to own the largest sub-tree possible
Can keep cached changes local Reduces network messaging

Only give up an owned portion of the tree when another user enters and injects contention (demotion)

7 of 25

Enter/Leave Document
To clarify, we assume
Users can enter and leave the document at any time To move from one section of the document to another, leave current section and enter new section (leave and reenter document) This is seamless/transparent to the user (i.e. the system removes and re-adds the user without informing the user)

Issues of performance and cache optimization are still open for our research

8 of 25

Concurrent Reading/Sharing
As with other CES/CSCW systems, sharing is permissible This paper/presentation addresses exclusive write access Certainly, concurrent read access is permissible
Updating the view of read-only clients upon a change would occur as it does in other systems

9 of 25

Path Finding
Since each node is uniquely identified, it is always possible to know the path to a node in the tree
Left = 0 Right = 1

Node 1011
10 of 25

The Node Structure

The node structure contains
Left and right children Sibling Color (white, black, grey) Owner (if black, what user owns this sub-tree) Original Request (what sub-tree node was requested to cause ownership of this node)

11 of 25

Coloring
White Unowned All sub-tree nodes are white logically Black Owned All sub-tree nodes are black logically Grey Grey-color 2 There must exist 2 black nodes in the sub-trees Possible grey configurations:

12 of 25

Algorithms
Deadlock-free Always traverse top to bottom [9] Handshake lock
Acquire node Acquire nodes child Release node

Insert User Remove User

13 of 25

InsertUser
User ui requests lock on node w All nodes in the path from t to v must be grey
If white, lock higher If black, lock fails

Increase grey-color in path If contention on w

Demote w If w is leaf undo inflated grey color
14 of 25

InsertUser(w) v

InsertUser - Demotion
At times, demotion is necessary
When the top-to-bottom access encounters a black node Push the ownership down (if a leaf, fail)
Requires that we maintain originalRequest (i.e., why is this node black) Paint node grey Recursion if we push along the same path to requested node
15 of 25

InsertUser(w, u1) u2 v

v u2 u1 w

InsertUser
InsertUser(w, ui) if [Link] ui RecurseInsert(root, w, ui) RecurseInsert(n, w, ui) if [Link] = white // ensures we always acquire largest lock then SetOwner(n, ui, w) else if n is a leaf node // a leaf node but not white, so failed insert (i.e. we cant demote a leaf) then RecurseRemove(root, w, ui) // undo the false inserts effect on greyColors return failure else if [Link] = grey // keep looking down then [Link] = [Link] + 1 RecurseInsert(NextInPath(n, w), w, ui) else // color of node in path to w is black, so we must demote it b = NextInPath(n, w) a = NextInPath(n, [Link]) SetOwner (a, [Link], [Link]) // demote n to a [Link] = grey [Link] = 2 if a b then SetOwner (b, ui, w) // the nodes are in separate paths else RecurseInsert(b, w, ui) // the nodes are in the same path SetOwner(w, ui, r) [Link] = black [Link] = ui [Link] = r
16 of 25

RemoveUser
User ui releases lock on node w All nodes in the path from t to v must be grey
If white, lock higher If black, release higher

Decrease grey-color in path Promote if possible when grey-color goes from 2 to 1

17 of 25

RemoveUser Cases
With promotion
2 ui v uj w t RemoveUser(w) ui v w
2

Without promotion
1 t RemoveUser(w)

Promote(v) ui t

18 of 25

RemoveUser Promotion
When grey-color reduces from 2 to 1, promote
4 v 2 2 RemoveUser(w, u1) 2 w u2 u1 2 2 3 v u2

19 of 25

RemoveUser
RemoveUser(w, ui) if [Link] = ui then RecurseRemove(root, w, ui) RecurseRemove(n, w, ui) if [Link] = black and [Link] = ui then ReleaseOwner(n) else if [Link] = grey // keep looking down then [Link] = [Link] 1 if [Link] = 1 and [Link] = black // sibling promotion priority then SetOwner(n, [Link], [Link]) else if [Link] = 1 and [Link] = black // w must be all that remains then SetOwner(n, [Link], w) else if [Link] = 0 and // paint n white as w and [Link] are white then ReleaseOwner(n) else RecurseRemove(NextInPath(n,w), w, ui) ReleaseOwner(w) [Link] = white [Link] = NIL [Link] = NIL
20 of 25

RemoveUser Special Cases

If an insertion failed, then we invoke a RemoveUser to reduce the artificially-inflated grey-count along the path from root to desired node It is possible that legitimate removals occurred between the time of the failed insertion and the concomitant removal (to compensate for the failed insertion) Consequently, the grey-count of a node can fall to 1 Promote sibling or the node associated with the failed insert Additionally, the grey-count of a node could fall to 0 Promote nothing (everything is now removed below this node) Paint this node white

21 of 25

Analysis
RemoveUser makes a single pass of the tree from top to bottom
O(h) where h is equal to the height of the tree.

InsertUser can fail and require an undo of the artificially-inflated grey-colors (via a call to RemoveUser)
Thus at most two passes of the tree from top to bottom Also O(h) where h is equal to the height of the tree

Promotion occurs in O(1) because we know the sibling is to be promoted (or in the special cases, the failed insert node is promoted or nothing is promoted)
22 of 25

Conclusion
Contributes hybrid concurrency policy to the field of CSCW/CES
Deadlock-free Multi-granular, hierarchical locking Maximizes sub-tree owned Minimizes messaging/communication Insert and remove algorithms efficient O(h) Promotion is efficient O(1)

23 of 25

Future Work
Address tree modification
Insert obtain lock on parent, then insert below Delete obtain lock on node and remove Split obtain lock on node and create children Join obtain lock on both nodes and combine Move this is a delete + insert

Simulation in progress Further define cache policies for concurrent readers Place into larger framework of open-system, Web services based architecture and simulate editing
24 of 25

References
1. 2. 3. 4. 5. 6.

7. 8. 9. 10. 11. 12. 13.

14. 15. 16.

Netbeans Collaboration Project. [Link] Sun Microsystems. Viewed August, 2005. V. Bharadwaj and Y.V. R. Reddy. A Framework to Support Collaboration in Heterogeneous Environments. SIGGROUP Bulletin. Vol 24, No 3. December 2003. pp. 103-116. M. Chu-Carroll, J. Wright, and D. Shields. Supporting Aggregation in Fine Grained Software Configuration Management. SIGSOFT 2002/FSE-10. Charleston, SC. November 2002. M. Chu-Carroll and S. Sprenkle. Coven: Brewing Better Collaboration through Software Configuration Management. SIGSOFT 2000. San Diego, CA. November 2000. C. Ellis and S. Gibbs. Concurrency Control in Groupware Systems. In Proceedings of ACM SIGMOD Conference on Management of Data, pages 399-407. ACM Press, May 1989. S. Greenberg and D. Marwood. Real Time Groupware as a Distributed System: Concurrency Control and its Effect on the Interface. In Proceedings ACM Conferences on Computer Supported Cooperative Work, pages 207-217. ACM Press, Nov. 1994. B. Magnusson, U. Asklund, S. Minr. Fine-Grain Revision Control for Collaborative Development. Proceedings of ACM SIGSOFT93. Los Angeles, CA. December 1993. J. Munson and P. Dewan. A Concurrency Control Framework for Collaborative Systems. Proceedings Computer Supported Cooperative Work, pages 278-287. ACM Press, Nov. 1996. V. N. Rao and V. Kumar. Concurrent Access of Priority Queues. IEEE Transactions on Computers. Vol 37, No 12. pp. 1657-1665. 1988. C. OReilly. A Weakly Constrained Approach to Software Change Coordination. In Proceedings of the 26th International Conference on Software Engineering. 2004. H. Shen, C. T. Cheong, and C. Sun. CoStarOffice: Toward a Flexible Platform-independent Collaborative Office System. IWCES04. D. Sun, S. Xia, C. Sun, and D. Chen. Operational Transformation for Collaborative Word Processing. CSCW04. Chicago, IL. November 2004. CHI Letters. Vol 6, Issue 3. pp. 437-446. [Link] der Hoek, D. Redmiles, P. Dourish, A. Sarma, R. S. Filho, and C. de Souza. Continuous Coordination: A New Paradigm for Collaborative Software Engineering Tools. Workshop on Directions in Software Engineering Environments. ICSE04. 2004. Y. Yang and D. Li. Separating Data and Control: Support for Adaptable Consistency Protocols in Collaborative Systems. Proceedings of CSCW04. Chicago, IL. November 2004. CHI Letters. Vol 6, Issue 3. pp. 11-20. M. Younas and R. Iqbal. Developing Collaborative Editing Applications using Web Services. IWCES03. 2003. B. P. Zeigler and H.S. Sarjoughian. Introduction to DEVS Modeling & Simulation with JAVA: Developing Component-based Simulation Models. Technical Document, University of Arizona. 2003.

25 of 25