Students: Yuen Lau and Marcin Matynia

Project Adviser: Professor James Elder

Mentor(s): Professor Moren Lévesque

Course Director: Professor Ebrahim Ghafar-Zadeh

Marcin Matynia

Bio: Marcin is a fourth-year computer engineering student with a passion for learning, developing, and experimenting with new engineering ideas.

Role: Marcin's role in this project involves investigating and developing an algorithm that solves the problem of keeping documents in an online, collaborative, real-time code editing environment consistent. He is also responsible for arranging team meetings and ensuring that the team is up-to-date on the latest project requirements.

Yuen “Will” Lau

Bio: Will is a visionary computer engineer based in Toronto. His experience in research labs and hackathons had put a lot of ideas inside his head. He wants to make a difference in people's lives by realizing these idea.

Role: Will's role in this project involves translating the developed algorithm into working code that can be tested for correctness. He is also responsible for developing the project plan and managing the project stakeholders.

The core of operational transformation (OT) is to keep multiple documents consistent. We say two or more documents converge when changes to them are made consistent with each other. This technique is already being used by Apache Wave, Google Docs, and many other collaborative software technologies.

This will be one of the first times someone has attempted to apply OT to programming languages. We will apply what we have learned here at the Lassonde School of Engineering to research and study papers on OT. We will then develop an intricate, lightweight algorithm that best suits our purpose. Finally, we will be implementing the algorithm with test-driven development and study its effect on programming. Our metric of success will be how well the product works, and how well we can market our product. We plan for the Lassonde School of Engineering to be our first client.

Prior to implementing OT, our WebSocket communication method was faster than Google Docs. We will aim to maintain that speed.

Ease of use is also our main goal. The front-end user should not even be aware of OT. We aim for zero-configuration.

Every single byte of the character should be secure, and the connection should be encrypted. We aim to protect our users.

This would be one of the first times OT is applied to source code. We aim for this project to become a part of ZapIDE.

Background

As fourth-year engineering students, both of us have participated in what seems like countless course projects. Throughout our four years, we have taken notice of the most common approaches to large classroom programming projects. Invariably, these large projects involving multiple team members in the classroom environment have been handled in one of three ways:

1) Taking Turns: In this approach, each team member completes a piece of the overall project before handing their work over to the next team member who adds to it. This process continues until the project is complete. Obviously, this approach suffers from very slow development time and relies on each team member writing/commenting their code well enough that the next team member can understand it.

2) Working Independently and Combining: In this approach, the project is broken down into multiple smaller tasks that are then assigned to individual group members. Each mini-task is developed independently and the overall project is completed by combining these pieces together. Although this process may have a faster development time than taking turns, the issue of whether the pieces actually fit together is an unavoidable problem. This can lead to days of wasted development time as team members struggle to patch together the not-so-compatible pieces as the project deadline nears.

3) Git Repositories: This approach is rarely used in the classroom environment and even then only by the most skilled students. We list it here because we have encountered it in the past, nevertheless, it is not a trivial tool for beginner-level programmers especially first-year students. Although this tool can be used to ensure that all team members are working on the most up-to-date document and that none of their changes lead to collisions that break the code, this approach still suffers from the lack of real-time communication.

In reviewing these approaches we thought to ourselves, isn't there a way that we can do this better? Why not have a simple, easy-to-understand approach that allows for online, real-time, collaborative code editing? This technology already exists for text documents (the most famous being Google Docs), but nothing really satisfies the need for online, real-time, collaborative code editing.

This is what got us thinking about potential solutions. For the purposes of this ENG4000 final project, we have decided to work on a major component of that solution, which is operational transformation.

The Problem OT Addresses

If two or more people are collaborating on an online document and each presses a key at approximately the same time then, due to latencies, it is quite possible that each collaborator will see the effects of the key that they pressed first followed by the effects of the keys pressed by the other collaborators. This scenario results in each collaborator having a final document that is inconsistent with what his or her peers have.

The Solution OT Provides

The solution to this problem lies in transforming the operations to achieve consistency. As seen in the example in figure 1, imagine two collaborators begin with a document that has the characters “abc”. The collaborator on the left decides to add the character ‘x’ at index 0 and, at the same time, the collaborator on the right decides to delete the character ‘c’. Without OT, the first collaborator will end up deleting the wrong character because after they prepend ‘x’, the character 'c' is no longer at index 2. What needs to happen instead is that the first collaborator performs a transformed version of the delete operation, which deletes the correct character at index 3. The second collaborator doesn’t need any transformations in this case because after deleting the character at index 2 then prepending ‘x’ leads to both documents being consistent.

(Figure 1: Example of operational transformation at work)

Implementing character-level OT rather than string-level OT

We decided to proceed with character-level OT because of the significant design challenges that string-level OT poses. These challenges include the fact that string deletions may overlap with other string deletions or even insert operations in a collaborative environment.

Not supporting OT compression

Compression of OT operations is useful for reducing the total number of operations that need to be performed, however, compression is only applicable to string-level OT, which we ruled out in the previous design decision. Furthermore, compression is most useful for non-real-time applications, which is not what we are aiming for.

Using the CCI model

After some initial research, we found that the CCI model was best suited for our purposes. This model specifies conceptual principles for implementing OT. Specifically, CCI stands for Causality preservation, Convergence, and Intention preservation.

Causality preservation essentially means queuing events in the order that they occurred. An example situation that we would want to avoid would be one wherein there are three people collaborating and the first one broadcasts a question, the second broadcasts an answer after receiving the question, but the third may receive the answer before having received the question.

Convergence means that after the operations have been performed, all copies of the document are consistent (i.e. the same).

Intention preservation has to do with ensuring that each operation performs the job it was intended to perform. In the example shown in figure 1 from the “Research Motivations” section, the delete operation performed by the collaborator on the right was transformed in order to preserve its original intention, which was to delete the character ‘c’. An important distinction must be made here between the user's intention and the operation's intention. Thus far, there does not seem to be any OT algorithm capable of guaranteeing preservation of the user's intention. What we describe here is intention preservation of the operation itself.

Using WebSockets rather than AJAX

Both WebSockets and AJAX can be used to facilitate communication between the back-end server and the front-end. Having said that, AJAX is a much older technology and is quickly being replaced by WebSockets. Because we wish to take advantage of the latest Web technologies and ensure that we are able to deliver the maximum speed achievable, we have decided to go with WebSockets.

1) Node.js - Back-end server

2) Yeoman - Project scaffolding

3) Bower - Front-end package manager

4) NPM - Back-end package manager

5) Grunt - Test, preview, and build tool

6) WebSockets - Communication Protocol

1) Multiple users collaboratively editing in real-time

2) Insertion, deletion, and selection

3) Cursors showing up for each person

4) Undo-redo history for each person

5) Cut, copy and paste

6) Language-specific tabbing

7) Language-specific syntax highlighting

For the future, we plan to apply our operational transformation library to create more collaborative tools such as collaborative drawing boards, event planners, and shopping lists.