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:

A list of team members emailed to your TA by April 8, 2010.
One copy of a design proposal not exceeding 1,200 words, due on Thursday, April 22, 2010.
One copy of a design report not exceeding 5,000 words, due on Thursday, May 6, 2010.
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.

X wishes to insert a "1" before the "n", and at the same time Y wishes to insert a "2" before the "o". X, Y, and Z should all eventually see "m1n2op".
X wishes to insert a "1" before the "n", and at the same time Y wishes to insert a "2" before the "n". X, Y, and Z should all eventually see the same text, which should be either "m12nop" or "m21nop".
X and Y both wish to delete the "o" at the same time. X, Y, and Z should all eventually see "mnp".
X inserts a "1" before the "n", Y sees the "1" and deletes it. X, Y, and Z should all eventually see "mnop".

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.

Your design should make efficient use of the network. For example, a small change to an existing multi-megabyte document should result in only a small amount of network communication.
A user should always be able to modify the document, even if other users are also actively modifying it.
Users should see each others' changes quickly, in only one or two network latencies.
The temporary or permanent failure of any one computer or server, or its network connection, should not prevent other users from continuing to edit the document.

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:

What happens when a user deletes a character?
What happens when a user inserts a character?
What are the different types of messages that hosts exchange?
How does your design deal with the example cases described in Section II?
What line of reasoning shows that your design implements the specification in Section III?
How well does your design provide the properties described in Section IV?
What happens when a new user joins an existing editing session?

Use this organization for your report:

Title page: Give your report a title that reflects the subject and scope of your project. Include your names, email address, recitation instructor, section time(s), and the date on the title page.
No table of contents.
Introduction: Summarize what your design is intended to achieve, outline the design, explain the major trade-offs and design decisions you have made, and justify those trade-offs and decisions.
Design: Explain your design. Identify your design's main components, state, algorithms, and protocols. You should sub-divide the design, with corresponding subsections in the text, so that the reader can focus on and understand one piece at a time. Explain why your design makes sense as well as explaining how it works. Use diagrams, pseudo-code, and worked examples as appropriate.
Analysis: Explain how you expect your design to behave in different scenarios. What scenarios might pose problems for performance or correctness? What do you expect to be the scalability limits of your design?
Conclusion: Briefly summarize your design and provide recommendations for further actions and a list of any problems that must be resolved before the design can be implemented.
Acknowledgments and references: Give credit to individuals whom you consulted in developing your design. Provide a list of references at the end using the IEEE citation-sequence system ("IEEE style") described in the Mayfield Handbook.
Word count. Please indicate the word count of your report at the end of the document.

Here are a few tips:

Use ideas and terms from the course notes when appropriate; this will save you space (you can refer the reader to the relevant section of the notes) and will save the reader some effort.
Before you explain the solution to any given problem, say what the problem is.
Before presenting the details of any given design component, ensure that the purpose and requirements of that component are well described.
It's often valuable to illustrate an idea using an example, but an example is no substitute for a full explanation of the idea.
You may want to separate the explanation of a component's data structures (or packet formats) from its algorithms.
Explain all figures, tables, and pseudo-code; explain what is being presented, and what conclusions the reader should draw.

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:

Clarity. Is the design described well enough to be understood, evaluated, and implemented?
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?
Simplicity. Is the level of complexity in the design justified?