Project Topics
Get Complete Project Material File(s) Now! »
Real Time Collaborative Editors
Real-time Collaborative Editors (RCE) are special class of distributed applications that allow users to collaboratively edit a shared document. These applications allow for a human-computer-human interaction which necessitates a careful design.
Although being distributed applications, RCE are specific in the sense that they must consider human factors [48]. So, they are characterized by the following requirements:
1. High local responsiveness: the system has to be as responsive as its single-user editors [32,99,100].
The response to the local user’s actions must be quick, even though collaborating users may reside
on different machines connected via the Internet with a long and non-deterministic communication latency. High responsiveness is very important because it presents a main indicator of the good quality of a collaborative system. Moreover, poor responsiveness decreases the system’s effectiveness in supporting collaborative work.
2. High concurrency: the users must be able to concurrently and freely modify any part of the shared document at any time [32, 99] in order to facilitate the flow of information among collaborating users.
3. Consistency: the users must eventually be able to see a converged view of all copies [32, 99]. Maintaining consistency is the major challenge since it is hard to manage the multiple streams of concurrent activities performed by multiple users which may lead to conflicting scenarios [48].
4. Decentralized coordination: all concurrent updates must be synchronized in a decentralized fashion in order to avoid a single point of failure.
5. Scalability: a group must be dynamic in the sense that users may join or leave the group at any time [48].
It is very difficult to meet these requirements when deploying RCE in networks with high communication latencies (e.g. Internet). Due to replication and arbitrary exchange of updates, consistency maintenance in a scalable and decentralized manner is a challenging problem. Traditional concurrency control techniques, such as (pessimistic/optimistic) locking and serialization, turned out to be ineffective because they may ensure consistency at the expense of responsiveness and loss of updates [32,48,58,99].
Since collaborative editors allow multiple users to concurrently edit the same shared document, divergence cases may be encountered. Consistency maintenance in the face of concurrent accesses and updates to shared document is one of the main issues in the design of collaborative editing systems.
Operational transformation (OT) is a technique originally invented to ensure consistency and avoid divergence occurring when many users edit concurrently the same document.
Overview on the Operational Transformation (OT) Approach
OT is an optimistic replication technique originally invented to allow many users (or sites) to concurrently modify the shared data and next to synchronize their divergent replicas in order to obtain the same data.
This approach is considered as the efficient and safe method for consistency maintenance in the literature of collaborative editors. Indeed, it is aimed at ensuring copies convergence even though the users’s updates are executed in any order on different copies.
After two decades of research, this technique has extended its capabilities and expanded its applications to include group undo, locking, conflict resolution, operation notification and compression, group-awareness, HTML/XML and tree-structured document editing, collaborative office productivity tools, application-sharing, and collaborative computer-aided media design tools. Recently, OT has been adopted as a core technique behind the collaboration features in Google Wave and Google Docs, which are taking OT to a new range of web-based applications7.
OT approach requires that every site stores all executed operations in a buffer also called a log. It is known that collaborative editors manipulate shared objects that own a linear data-structure [32, 98, 100] (e.g. a list). This list is a sequence of elements from some data type, such as a character, a paragraph, a page, an XML node, etc. In [100], it has been shown that this linear structure can be easily extended to a range of multimedia documents, such as MicroSoft Word and PowerPoint documents [48].
Two primitive operations are generally used to modify the shared document:
Ins(p; e; s) to insert the element e at position p.
Del(p; s) to delete the element at position p.
Access Control for Collaborative Editors
Protecting data and resources is one of the most important requirements of any information management system. Indeed, it ensures (i) confidentiality: protecting data from unauthorized disclosure and (ii) integrity: protecting data from unauthorized or improper modifications.
To enforce protection, every access to the data must be controlled. Moreover, only authorized accesses can be allowed. To develop an access control system, we need to define the regulation of the access to the data as well as the functions to be executed in order to implement these regulations in a computer machine. In general, the development process of access control systems relies on the concepts cited below [81]:
1. Security policy defines the rules of the access control, for instance saying that a site s has the right to modify the shared document is a rule.
2. Security mechanism defines the functions that will be executed on the computer machine. These functions illustrate the access control policy defined by the security policy and formalized by the security model. It should be pointed out that defining a security policy model is not a trivial task [81]. It is a subtle and challenging task. Indeed, designing a security model relies on interpreting real world security policies which are often ambiguous and complex in a unambiguous and simple way in order to be executed on a computer machine [81]. Moreover, a security policy depends on the nature of the application in which it will be enforced and must take into consideration malicious behaviour.
Controlling access is more and more complex in collaborative applications since they have special requirements. In the following, we detail these requirements and show how they complicate the access control task.
Access Control Issues and Requirements in Collaborative Applications
There are many issues faced when trying to apply an access control model for a collaborative application.
First of all, it is difficult to balance the competing goals of collaboration and security [107]. In fact, collaboration aims at allowing many users to access to shared resources by building useful connection among users, tools and information. However, security aims at ensuring confidentiality and integrity of shared information. Several requirements must be addressed in order to ensure security for such systems where the behavior of users is unpredictable and interactions between users and resources are unexpected. Consequently, protecting resources in a collaborative application needs to address many requirements not raised by normal single-user applications. Moreover, collaborative systems contain resources with different degree of sensitivity. For instance, some resources could be top secret such as military documents or information of a patient in a healthcare application while other resources are just confidential such as academic emails. Thus, it is difficult to manage access control for different resources at the same time.
Furthermore, some policies require real time updates which means that the policy is changed while it is in effect. However updating the policy while it is deployed may inevitably lead to security holes. To further illustrate this issue, suppose that in a financial company, the user Bob has the right to update a given resource but concurrently the policy is updated to revoke this right. Since the policy update is not enforced immediately, Bob may perform updates while policy is changing which obviously lead to policy violation and may introduce financial loss to the company.
Discretionary Access Control (DAC)
Discretionary policies define access control on the basis of access right requestor identity. Access rules are specified to assign access rights to requestors. Then, accesses are granted or denied based on these access rules. In this security model, users can have the right to delegate their access control capabilities where from the name discretionary.
DAC policy is characterized by its flexibility and is widely used in many sectors. The most famous discretionary model that was proposed in the literature is the access matrix model. This model is based on the subject-object distinction which represents the key concept in this model [82]. It was first proposed in [57] and allows for describing discretionary access control in operating system context. Then, the model was refined by Graham [38]. The formalization of the access matrix model called HRU model was proposed by Harisson, Ruzo and Ullman [42].
Three kinds of entities are defined: (i) Objects: which represent the resources to be protected such as files in file systems or shared documents in collaborative editors; (ii) Subjects: are the users of the objects to be protected; (iii) Access rights: are the operations to be executed by subjects on the protected objects.
An access matrix is a matrix containing subjects in rows and objects in column. Each entry of the matrix denotes the rights a subject has on a given object. To check an access rule, an action is granted to a user if and only if his access matrix entry contains the appropriate rights allowing action performance. Figure 2.3, represents an example of the access control model with a small set of subjects ({Alice, Bob, Carl}) having the possibility to own, read, write and execute rights on four files. This matrix specifies for example, that Alice has the right to read and write the file number 2.
Table of contents :
Chapter 1 General Introduction
1.1 Motivations
1.2 General Context
1.3 Access Control Issues and Requirements in Distributed Collaborative Editors
1.4 Undoability in Distributed Collaborative Editors
1.5 Contributions
1.6 Thesis organization
Chapter 2 State of the Art
2.1 Collaborative Editors
2.1.1 Real Time Collaborative Editors
2.1.2 Overview on the Operational Transformation (OT) Approach
2.2 Access Control for Collaborative Editors
2.2.1 Access Control Issues and Requirements in Collaborative Applications
2.2.2 Classes of Access Control Policies
2.2.3 Access Control in Database Area
2.2.4 Access Control for P2P Systems
2.2.5 Comparing Existing Solutions
2.3 Conclusion
Chapter 3 Our Generic Access Control Model
3.1 Coordination Model
3.1.1 Shared Data Object
3.1.2 Shared Policy Object
3.1.3 Single and Multi-Administrator Approaches
3.2 Concurrency and Security Issues
3.2.1 Out-of-order Execution of Cooperative and Administrative Operations
3.2.2 Joint Issue
3.2.3 Remote Check and Unnecessary Undo
3.3 A Generic Security Model
3.4 Distributed Garbage Collection for Administrative Logs
3.4.1 Garbage Collection Issues
3.5 Conclusion
Chapter 4 Concurrency Control Algorithms and Correctness Proof
4.1 Concurrency Control Algorithms
4.1.1 Cooperative Requests
4.1.2 Administrative Requests
4.1.3 Causality Between Cooperative and Administrative Requests
4.1.4 Control Procedures
4.1.5 Check Procedures
4.1.6 Administrative Procedures
4.1.7 Asymptotic Time Complexities
4.1.8 Illustrative Example
4.2 Correctness Proof
4.2.1 General Principles
4.2.2 The Correctness Criteria
4.3 Conclusion
Chapter 5 On the Undoability Problem in Distributed Collaborative Editors
5.1 Notations
5.2 Undo Approach
5.2.1 Principle
5.2.2 Undo Effect
5.2.3 Undo Properties
5.2.4 Illustrative Examples
5.3 Related Work
5.3.1 Proposed Undo Solutions for Single-user Editors
5.3.2 Undo Solutions for Collaborative Editors
5.4 Conclusion
Chapter 6 A Necessary and Sufficient Condition for Undoability
6.1 Formal Problem Statement
6.2 Necessary and Sufficient Condition for Undoability
6.2.1 CCO Properties
6.2.2 CSP Model
6.2.3 Necessary and Sufficient Condition for Undoability
6.2.4 Discussion
6.3 Our Generic Undo Framework
6.3.1 The Hide Relation
6.3.2 Transformation Rules
6.3.3 Illustrative Example
6.3.4 Asymptotic Time Complexity of the Undo Command
6.4 Conclusion
Chapter 7 Experimental Study and Performance Measurements
7.1 Coordination Framework
7.1.1 OPTIC Characteristics
7.1.2 Garbage Collector for Cooperative Logs
7.2 Developement Frameworks
7.2.1 JXTA
7.2.2 NetBeans
7.2.3 Grid’5000
7.3 Experimental Results for the Coordination Layer
7.3.1 Metrics
7.3.2 Performances of the Desktop Application
7.3.3 Performances of the Mobile Devices Application
7.4 Experimental Results for the Security Layer
7.4.1 P2PAgenda Prototype
7.4.2 Processing Time for Checking Local and Remote Requests
7.4.3 Response Time Variation with Peers Number
7.4.4 Access Control Overhead
7.5 Conclusion
Chapter 8 General Conclusion
8.1 Summary
8.1.1 Why RCE Require Access Control?
8.1.2 Access Control Requirements and Issues
8.1.3 Undoing Operations in RCE
8.2 Summary of the Contributions
8.3 Directions for Future Work
Appendix A Correctness Proof of the Undo Approach
A.1 Hide Relation Properties
A.2 Inverse properties Preservation
A.3 Transformation Properties Preservation
A.3.1 TP1 Preservation
A.3.2 TP2 Preservation
Appendix B
A Distributed Garbage Collector for Cooperative Logs
B.1 The Coordination Framework OPTIC
B.2 Garbage Collection Issues
B.3 Garbage Collection Algorithm
B.4 Illustrative Examples
Bibliography
