Notice: this Wiki will be going read only early in 2024 and edits will no longer be possible. Please see: https://gitlab.eclipse.org/eclipsefdn/helpdesk/-/wikis/Wiki-shutdown-plan for the plan.
RT Shared Editing
Project Lead: Mustafa Isik
Mentor(s): Scott Lewis, Ken Gilmer
Contents
Motivation
The RT Shared Editor, which I'll dub Cola (collaborate) for now, is supposed to be a tool enabling developers to reap the benefits of pair programming within the Eclipse IDE.
The term pair programming describes an activity in which two developers simultaneously work on a single development machine.
Even though not new to the development community, pair programming has witnessed a significant rise in adoption over the last years. One of the main reasons being the inclusion to the set of eXtreme programming (aka XP) practices. Thus pair programming is especially, but certainly not only, popular among developers utilizing the values, principles and practices propagated by the XP methodology.
The reasoning behind pair programming, as articulated by software developer, author and XP figurehead Kent Beck (2005 p.42) is manifold and pair programmer's activities are described as
- keep each other focused and on task
- brainstorm refinements to the system
- clarify ideas
- take initiative when their partner is stuck, lowering frustration
- hold each other accountable to the team's practices
From my own experience I can add, that programming in pairs has proved to beneficial in
- widening developers' horizon and perspectives on perceiving and tackling problems
- increasing trust in one's own skills and generating awareness for areas requiring improvement
- learning from more advanced developers
- improving through working with less experienced devs, motivating to reflect on the essence of one's own practices
- refining one's own communication skills
Current Situation
Tool-support for pair programming in Eclipse is pretty much non-existent. Pair programming sessions, as spontaneous as they might be arranged in some teams, usually are set up for longer periods of time, ranging anywhere from an hour to some four or five. Pairs consist of locally available developers.
Limitations & Problems
Geographical limitations do not permit for simple pair programming. Since individuals are required to sit in front of the same machine, they apparently have to be located at offices close to each other. Thus software development, not being a regionally bound activity, as proven by the sustained success and advances of open-source software and the nature of many open-source teams, has to be carried out without utilizing effective pair programming in many cases.
Even when developers are located at the same work site, the effort to get two people set up together in front of a computer (drinks, resources, etc.) proves not to be worth for short programming or reviewing tasks, which sometimes are all that is required. This does not mean that coders do not occasionally sit down for such quick tasks, but from personal experience not as often as it might be beneficial for oneself and/or the code.
Traditional instant messaging software does not lend itself for code communication among developers. Such software generally proves to be fairly feature-limited and catering to different target audiences. Theoretically it would lend itself for sending back and forth short code snippets at best, practically large-scale adoption of such behaviour has yet to be seen.
Open-plan offices or group cube farm layouts do not support developers in utilizing pair programming benefits either, quickly degrading the workspace noise-level to that of an airport lobby (by the way, the true problem here would be of course the office layout, but the scope of changing that is unfortunately usually beyond the individual developer).
Furthermore developers, who usually keep book resources in their personal work environment, end up being stripped of those for half of the time they are pair programming.
Resolution
Cola is supposed to support collaborative work on code from disparate locations, minimizing organizational impact and improving on flexibility issues concerning pair programming.
Developers are intended to be able to work simultaneously on a single source file, viewing changes made by other contributors in real-time and editing the most up-to-date version of the file at all times.
The initial incarnation of Cola is to materialize in the form of an Eclipse IDE plug-in.
Consistency Maintenance
Maintaining consistency among shared data in a distributed real-time editing environment is of prime importance.
Over the last decade a lot of thought has been dedicated to the research of domain-specific issues in real-time collaborative groupware systems. Chengzheng Sun and Clarence Ellis have authored a paper (Sun & Ellis 1998) providing a thorough overview of such. The subsequent discussion of challenges specific to real-time collaborative editing is based on the referenced paper and intended to be self-sustaining in that you will not have to dig into academic research material to understand the challenges at hand. Figure 1 shows a somewhat idealistic scenario where communication lag between several editing sites remains without undesired consequences because operations are generated and executed at all sites in an orderly fashion. In a realistic distributed editing scenario, as depicted in Figure 2, the need for consistency maintenance becomes apparent.
Challenges
Divergence
Due to dependencies between operations originating from different editors on a shared document and suffering from propagation lag in a distributed environment, shared data state at different sites can divert from each other. This holds especially true for operations that are not commutative in execution order.
| site 1 | state | site 2 | state | site 3 | state |
|---|---|---|---|---|---|
| A:insert('a') | a | A:insert('a') | a | A:insert('a') | a |
| C:insert('c') | ac | B:insert('b') | ab | B:insert('b') | ab |
| B:insert('b') | acb | C:insert('c') | abc | C:insert('c') | abc |
Causality-violation
Each editing user's changes need to be communicated to the other editing sites. Independent from message generation times, notification of changes may arrive out-of-order. The resulting artifact is referred to as causality-violation. The order in which operations A and B in Figure 2 arrive at site 3 visualizes a typical case of causality-violation. Operation B is generated at site 2 after the arrival and execution of operation A. The reversed arrival order of both operations at site 3 may result in an undefined operation B at site 3 (e.g. B is supposed to delete an insertion commited by A). Depending on the underlying communications protocol even the in-order arrival of editing operations originating from the same site might not be guaranteed.
Intention-violation
Intention-violation is different from causality-violation in that it refers to the problems that arise when executing an operation on a document state altered by operations not having been executed at the operation's generation site.
Operation C in Figure 2 is defined/generated at site 3 on a document state neither affected by operation A nor B. Upon arrival and execution at sites 2 and 3 the respective document states have already been changed by operations A and B and can cause operation C to commit an unintended and undesired change.
In contrast to the divergence-problem, intention-violation cannot be resolved by a simple serialization protocol.
Resolution Approach
Look at the Sky & Spot JUPITER
A closer inspection of a paper titled "High-Latency, Low-Bandwidth Windowing in the Jupiter Collaboration System" (Nichols et al 1995) reveals a very interesting approach to solving distributed-state synchronization problems in systems with more than two participating sites.
Even though functionality-wise the more advanced approaches described in (Sun & Ellis 1998) also represent solutions to the challenges in realizing Cola, (Nichols et al 1995) makes assumptions perfectly feasible for Cola's case that (in relative terms) greatly simplify the required concurrency-control algorithm.
Client-Server Communications
Much of the complexity of for instance the GROVE and REDUCE collaboration models stem from the fact, that they are designed for handling arbitrary communication-paths between each editing site. The JUPITER collaboration system on the other hand is designed around a central server. Utilizing the resulting communications topology, conflicting messages are resolved on the level of 2-way messaging between specific client - central server as opposed to n-way communications.
Since every participating client synchronizes with the central server, which serves as a serialization instance as visualized in Figure 4, consistency among clients upon execution of all operations is guaranteed, prohibiting divergence among states.
Optimistic Change Application
Since responsiveness and immediate user feedback are important and expected features in an editor, user operations are applied immediately to the local document state without awaiting server approval or undergoing any modifications.
Conflict Resolution via Operational Transformations
Central to ensuring consistency among document states is the operational transformation function used to resolve issues with conflicting operations. The messaging structure with a central server permits for narrowing the scope of conflict resolution to client-server communications. Different document states among client sites are inherently handled by client-server synchronization.
Regarding communication between a specific client and the central server, document states at both sites can divert due to the immediate application of changes at the generating site and the server site incorporating changes originating from other client sites in addition to server-local changes.
Causality-violation can be prohibited by using a network protocol that does not permit for out-of-order messaging of operations to the other site in client-server communication. Cola's network protocol will be chosen with respect to satisfaction of this property. Since communications are effectively limited to 2-way / routed through the server document state, out-of-order arrival of operations originating from different sites, not conflicting in document state (as for example operations A & B from sites 1 & 2 reaching site 3 in reversed order in Fig.2) is not an issue and does not require any consideration from the operational transformation mechanism.
Intention-violation issues, which arise from operations generated and executed on different document states, need to be handled by the operational transformation-function.
basic 2-way communication is of the form
- client generates operation
- client executes operation locally
- client notifies server of operation
- server receives operation
- in case of conflict: server transforms operation
- server executes operation locally
- server notifies all other clients of operation
for every receiving client
- client receives operation
- in case of conflict: client transforms operation
- client executes operation locally
State-Space Model
INCLUDE SAMPLES HERE ...
Protocol Review
Integration into Eclipse Communication Framework
Resources
Meeting Notes
Papers & Books
- Beck, K 2005, Extreme Programming Explained - Embrace Change, 2nd Ed., Addison-Wesley, Boston MA (USA), p. 42
- Sun, C & Ellis, C 1998, Operational Transformation in Real-Time Group Editors: Issues, Algorithms, and Achievements, Proceedings of the ACM Conference on Computer-Supported Cooperative Work, Seattle WA (USA), pp. 59-68
- Nichols, D, Curtis, P, Dixon, M & Lamping, J 1995, High-Latency, low-bandwidth windowing in the Jupiter collaboration system, Proceedings of the 8th annual ACM symposium on User interface and software technology, Pittsburgh PA (USA), pp. 111-120