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.
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.
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.
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.
Here are some properties your design should have, though you maybe have to compromise in some of these areas.
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.
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.