6.033 2010 Design Project Two

I. Due dates

You will do Design Project Two in teams of three students who share the same recitation instructor. There are four deliverables:
  1. A list of team members emailed to your TA by April 8, 2010.
  2. One copy of a design proposal not exceeding 1,200 words, due on Thursday, April 22, 2010.
  3. One copy of a design report not exceeding 5,000 words, due on Thursday, May 6, 2010.
  4. A five-minute in-recitation presentation on May 11, 2010. In consultation with the chair of the faculty we have determined that the assignment follows the spirit of the end-of-term rules.

This assignment is under-specified, and part of your job is to complete the specification sensibly. Start early to give yourself time to think about your design and revise it. A good design will likely take more than a few days.

II. The Goal

Your job is to design a collaborative text editor. The idea is that multiple users should be able to edit the same document at the same time. Each user has his or her own computer running the editor software. Let's call the editor software running on behalf of a particular user a "host". The hosts can send and receive messages on the Internet. Each host should display to its user the contents of the document being edited. A user can perform three operations on the document: click the mouse between two characters (or at the start or end of the document) to set the position of a per-user cursor, insert a character at the user's current cursor point, and delete a character before the current cursor point. When a user inserts or deletes, the hosts of other users should display the change quickly, so that collaboration is as smooth as possible.

Your design should handle situations where multiple users want to insert or delete at the same time. In particular, you will want to think carefully about what happens when multiple users want to insert or delete at the same or nearby positions at the same time.

Here are some example cases. In all cases the starting state is that users X, Y, and Z are collaboratively editing the same document, and all see contents "mnop". Your design may affect exactly what user actions are required to perform editing operations, so these cases are stated in terms of user intent rather than user actions, with the assumption that the users perform whatever actions are natural in your design to carry out their intent.

The hosts should communicate over the Internet using TCP or UDP. You can assume there are no firewalls or NATs, and that hosts have permanent IP addresses. Remember that the network may delay packets, and that packets may arrive out of order: if host H1 sends a packet to H2, and then sends a packet to H3, the packet to H3 may arrive first.

You are allowed to modify the user interface outlined above (e.g., to display more information to the user, to require the user to take more actions, or to restrict what the user can do), but your report should justify the need for any such modifications.

You can read more about collaborative editors here. Feel free to borrow ideas from existing systems, but be sure to explain any such ideas and to give their originators credit in your report.

III. Specification

Here's an incomplete specification. It is a description of how to think about whether your design is correct. You don't need to directly implement the model described here; you only need to design a system whose externally-visible behavior fits this specification. There are probably many ways to do that.

First, we'll think of the content of the document at any given time at a particular host as consisting of a sequence of characters. Each character in the content has a unique identifier (hereafter called an Id), a tuple <u,i>. u indicates which user originally inserted the character into the document. i indicates that the character was the i'th character the user typed. Ids let us name characters unambiguously. Each character is either visible or invisible. The host should display the visible characters in the content to the user.

Second, your design should ensure that if all users are idle for long enough, and there are no computer or network failures, then all the hosts should have the same document content, and display the same text to the users. Let's call this an "eventually consistent state." It is OK for users to temporarily see different text.

Third, inserts and deletes should affect a document's subsequent eventually consistent states in the following way. A delete(Id) operation should cause character Id to be marked invisible in all subsequent eventually consistent states. An insert(c, Id1, Id2) operation should cause ASCII character c with new identifier Id1 to exist at some point after existing character Id2 in all subsequent eventually consistent states.

IV. Performance and Reliability Goals

Here are some properties your design should have, though you maybe have to compromise in some of these areas.

V. Your design proposal

The design proposal should summarize your design in 1200 words or fewer. It should outline the protocol and algorithms the hosts use to carry out user insert and delete operations.

You do not have to present a detailed rationale or analysis in your proposal. However, if any of your design decisions are unusual (particularly creative, experimental, or risky) or if you deviate from the requirements, you should explain and justify those decisions in your proposal.

You will receive feedback from your TA in time to adjust your final report.

VI. Your design report

Your report should explain your collaborative editor design. It should discuss the major design decisions and tradeoffs you made, and justify your choices. It should discuss any limitations of which you are aware. You should assume that your report is being read by someone who has read this assignment and has taken 6.033 but has not thought carefully about this particular problem. Give enough detail that your project can be turned over successfully to an implementation team.

Your report should focus on the protocol by which the hosts carry out user editing operations, and on the algorithms the hosts use to generate and process protocol messages in order to ensure that all user operations are carried out and that all users eventually see the same content. Your report should be sure to answer the following questions:

Use this organization for your report:

Here are a few tips:

While the Writing Program will not be grading DP2, you should feel free to ask them for help.

VII. Your presentation

You will have only about five minutes for your presentation. The audience will be very familiar with the problem, so you can get right to the guts of your solution. A good approach would be to first describe the types of messages that hosts exchange, and then talk about how hosts generate and process messages. You might want to use one of the examples in Section II to illustrate.

VIII. How we evaluate your work

Your recitation instructor will assign your report a grade that reflects both the design itself and how well your report presents the design. These are the main high-level grading criteria:
  1. Clarity. Is the design described well enough to be understood, evaluated, and implemented?
  2. Correctness. Does the design achieve the goals laid out in Section II? Does it fulfil the specification in Section III? Does it provide the properties mentioned in Section IV?
  3. Simplicity. Is the level of complexity in the design justified?