OGI CSE 515 HW4: Project

CSE515 Distributed Computing Systems

Winter 2004

Homework 4: Design a Shared Whiteboard

Problem Summary

For this Homework you are required to design a shared whiteboard service. The requirements are described later in this web page. No implementation of your design is required at this stage; that comes next!
The purpose of the assignment is to help you gain a better understanding of the issues involved in designing a distributed application.

Please do your design in teams of four or five students (that is, four groups for the whole class). Working in a group is a requirement, not a suggestion. There are several reasons for this:

You will be able to take advantage of the expertise of the whole team.

By discussing the design amongst the team, you will remove the most obviously broken ideas before you have to share them with the rest of the class!

You will learn from your colleagues.

The next step in the project will be to synthesize the best ideas from the outputs of these team designs to create a common class design. It will be hard enough to do this if you start with 4 designs as inputs; it would be am impossible task if you stared with 13 to 16.

The output of this step in the project is a design document that you will share with the other teams in the class.

User Requirements

Professor Otto Ortenburger at OGI and Professor Paula Petrovska at PSU collaborate on research. When talking by telephone, they often feel the need to walk up to the whiteboard and show their colleague what they mean with a picture. But of course, they can't.
Petrovska got the idea of asking you to implement a virtual whiteboard in hyperspace, because she does not like taking the MAX out to OGI in the rain. Ortenburger said that there was no way that a group of students could produce a whiteboard with all of the functions that he required as a class project, but Petrovska thought that OGI students were up to the challenge. In any case, Petrovska believes that many of the functions that Ortenburger wants are unnecessary, and that a "bare bones" design will be a lot better than nothing, even if it is not perfect.

When I met with Professors Ortenburger and Petrovska to collect the requirements, in the form of user stories, the conversation went something like this.

Petrovska:
This first thing that I need to do is connect my computer to Ortenburger's computer. We will already be talking on the phone when we do this, so it's OK for us both to have to run the application.
Ortenburger:
Well, it would be nice if Petrovska could just "call me" on the computer, in the same way that she calls me on the 'phone. The computer could "ring", and I could choose to answer it, and that would open the whiteboard.
P:
Then I pick up a pen and draw some shapes on the whiteboard. Circles, rectangles, hexagons, irregular polygons, and so on. And I might also draw some lines connecting them.
O:
You'll want to be able to draw in different colors, of course.
P:
Ortenburger, you're colorblind! Why would you care what color I use!
O:
Well, although you might draw in, say, red and green, which I can't distinguish, I might choose to display the red as black and the green as light gray, which I can differentiate just fine.
P:
I'm happy with telephone black and blanched white. But I will need an eraser; I often change my mind.
O:
And I'll need to be able to draw over what you are drawing, and add my own ideas.
P:
Yes! And sometimes you will need to erase what I've drawn and put something else in the space.
O:
And you will need to type labels on some of the arrows and in some of the shapes.
P:
Yes, that would be useful. It would also be good to be able to point to things—to be able to say "this box here is a reactor", rather than having to type labels.
O:
One of the great things about a virtual whiteboard is that we won't have to worry about running out of space. We can just scroll down to some empty space and keep going.
P:
And when one of us goes off to teach a class, we can save the whiteboard so that we can carry on later.
O:
So of course we would need to be able to restore a whiteboard from a file. And to print it out ...
P:
We don't really have to print it—we could just take a screen dump, and print that.
O:
Once I have a whiteboard saved in a file, it would be really handy to be able to edit it even when Petrovska isn't online. Then, when we next connect, I can have a nice diagram ready and waiting.
P:
Yes, for once you've hit on something that would be really useful. I get tired of waiting for you to draw one of your fussily perfect diagrams. And I could do the same with one of my "big picture" diagrams while you are preparing your lecture. So long as I draw on the left of the screen and you draw on the right, everything should work out fine.
Prof Black:
What about latency?
O:
What's latency?
P:
What do you mean?
Black:
Well, Paula, when Otto picks up the pen and draws a box on the whiteboard, and says to you over the phone "think about this reactor", how long are you prepared to wait until you see the the reactor on your computer screen?
P:
What do you mean, "wait"? I don't want to wait at all! I'll need to see what he's drawing right away, or else the interaction won't work.
O:
Petrovska's right. And when she points to something, I have to see the pointer right at that time, not 5 seconds later.

As you can see, the users were not always in agreement over what they wanted, and the relative importance of the various items. I pointed out to them that my students might be really confused by this, and not know how to choose what to implement first. Otto and Paula saw that this could be a problem, so they appointed me to be their representative, and to answer questions from my students about requirements.

Here is the question and answer dialog from a previous discussion with a group of implementors.

Architectural Alternatives

There are two basic architectures for a shared whiteboard system.

In the first, the state of the whiteboard is kept on a single common server. Each participant uses a local application that does two things:

Responds to user inputs, and sends updates to the shared whiteboard server.

Receives change notifications and current state messages from the shared server, and displays the corresponding objects.

In the second, there is no common server, and the state of the whiteboard is replicated at each of the users' computers. The application on each computer:

Responds to user inputs, and sends updates to all of the other users' computers, including itself.

Receives a stream of update messages from other users' computers, processes them, and displays the corresponding objects.

It should be clear that if the updates are processed in the same order at each user's computer, those computers will display identical views of the whiteboard. (They are behaving as replicated determinstic state machines). Actually, the requirement of identical ordering is sufficient but not necessary: consider two users drawing in opposite corners of the whiteboard, for example. Can you formulate a weaker rule that will still guarantee consistency? (Hint: think about defining a causal order.)

What you should do

Form a design team, and give your team a name. Send cse515-hw an email message listing the name of your team and the names of the team members. Your design documents should not have your personal names on them, just the name of your team.
Write a high-level design for a distributed object-oriented system that will satisfy Ortenburger and Petrovska. You should describe your basic architectural approach (which will probably be one of the two alternatives outlined above, but might conceivably be one that I have not considered), and say why you have chosen it (e.g., by listing pros and cons for each approach). I recommend the decentraized approach, because the customers do not have a machine available on which to run a server, and because it seems that it will best meet the requirement for disconnected operation.

You should also describe the main classes of objects in your system, and give the responsibilities and collaborators for each class (e.g., with CRC cards). You do not have to design every detail of the interface of every object at this time. Objects that already exist in standard libraries, like dictionaries and ordered collections, may be assumed. If you plan to use an existing middleware package, identify the package and briefly explain its capabilities. For example,

We plan to use the Camford ordered multicast package, available from http://www.omc.camford.org. This package is CORBA accessible, and guarantees delivery of all multicast messages to all members of a group in the same order. Messages from different members of the group are ordered arbitrarily, but the same order is seen everywhere.

Your design document should be as brief as possible consistent with meeting these goals. Remember, in the next phase of the project, you will have to read several of these design documents and extract their best features.

There is a publicly writeable directory in the OGI file system at /projects/class/cse515/www/projectDesigns. Place your design documents as html (or pdf ) files in this directory before 4PM on 16th February. If your group name is wizards, call the document wizards.html. (Mail a copy to cse515-hw, and keep a copy, in case someone vandalizes this directory!) Try to limit the complexity of your document (for example, don't use a tree of 10 inter-linked html files) since this will make it much easier to print your design. Pictures are OK, in fact, they are encouraged.

	CSE515 Distributed Computing Systems Winter 2004

	Homework 4: Design a Shared Whiteboard Problem Summary For this Homework you are required to design a shared whiteboard service. The requirements are described later in this web page. No implementation of your design is required at this stage; that comes next! The purpose of the assignment is to help you gain a better understanding of the issues involved in designing a distributed application. Please do your design in teams of four or five students (that is, four groups for the whole class). Working in a group is a requirement, not a suggestion. There are several reasons for this: You will be able to take advantage of the expertise of the whole team. By discussing the design amongst the team, you will remove the most obviously broken ideas before you have to share them with the rest of the class! You will learn from your colleagues. The next step in the project will be to synthesize the best ideas from the outputs of these team designs to create a common class design. It will be hard enough to do this if you start with 4 designs as inputs; it would be am impossible task if you stared with 13 to 16. The output of this step in the project is a design document that you will share with the other teams in the class. User Requirements Professor Otto Ortenburger at OGI and Professor Paula Petrovska at PSU collaborate on research. When talking by telephone, they often feel the need to walk up to the whiteboard and show their colleague what they mean with a picture. But of course, they can't. Petrovska got the idea of asking you to implement a virtual whiteboard in hyperspace, because she does not like taking the MAX out to OGI in the rain. Ortenburger said that there was no way that a group of students could produce a whiteboard with all of the functions that he required as a class project, but Petrovska thought that OGI students were up to the challenge. In any case, Petrovska believes that many of the functions that Ortenburger wants are unnecessary, and that a "bare bones" design will be a lot better than nothing, even if it is not perfect. When I met with Professors Ortenburger and Petrovska to collect the requirements, in the form of user stories, the conversation went something like this. Petrovska: This first thing that I need to do is connect my computer to Ortenburger's computer. We will already be talking on the phone when we do this, so it's OK for us both to have to run the application. Ortenburger: Well, it would be nice if Petrovska could just "call me" on the computer, in the same way that she calls me on the 'phone. The computer could "ring", and I could choose to answer it, and that would open the whiteboard. P: Then I pick up a pen and draw some shapes on the whiteboard. Circles, rectangles, hexagons, irregular polygons, and so on. And I might also draw some lines connecting them. O: You'll want to be able to draw in different colors, of course. P: Ortenburger, you're colorblind! Why would you care what color I use! O: Well, although you might draw in, say, red and green, which I can't distinguish, I might choose to display the red as black and the green as light gray, which I can differentiate just fine. P: I'm happy with telephone black and blanched white. But I will need an eraser; I often change my mind. O: And I'll need to be able to draw over what you are drawing, and add my own ideas. P: Yes! And sometimes you will need to erase what I've drawn and put something else in the space. O: And you will need to type labels on some of the arrows and in some of the shapes. P: Yes, that would be useful. It would also be good to be able to point to things—to be able to say "this box here is a reactor", rather than having to type labels. O: One of the great things about a virtual whiteboard is that we won't have to worry about running out of space. We can just scroll down to some empty space and keep going. P: And when one of us goes off to teach a class, we can save the whiteboard so that we can carry on later. O: So of course we would need to be able to restore a whiteboard from a file. And to print it out ... P: We don't really have to print it—we could just take a screen dump, and print that. O: Once I have a whiteboard saved in a file, it would be really handy to be able to edit it even when Petrovska isn't online. Then, when we next connect, I can have a nice diagram ready and waiting. P: Yes, for once you've hit on something that would be really useful. I get tired of waiting for you to draw one of your fussily perfect diagrams. And I could do the same with one of my "big picture" diagrams while you are preparing your lecture. So long as I draw on the left of the screen and you draw on the right, everything should work out fine. Prof Black: What about latency? O: What's latency? P: What do you mean? Black: Well, Paula, when Otto picks up the pen and draws a box on the whiteboard, and says to you over the phone "think about this reactor", how long are you prepared to wait until you see the the reactor on your computer screen? P: What do you mean, "wait"? I don't want to wait at all! I'll need to see what he's drawing right away, or else the interaction won't work. O: Petrovska's right. And when she points to something, I have to see the pointer right at that time, not 5 seconds later. As you can see, the users were not always in agreement over what they wanted, and the relative importance of the various items. I pointed out to them that my students might be really confused by this, and not know how to choose what to implement first. Otto and Paula saw that this could be a problem, so they appointed me to be their representative, and to answer questions from my students about requirements. Here is the question and answer dialog from a previous discussion with a group of implementors. Architectural Alternatives There are two basic architectures for a shared whiteboard system. In the first, the state of the whiteboard is kept on a single common server. Each participant uses a local application that does two things: Responds to user inputs, and sends updates to the shared whiteboard server. Receives change notifications and current state messages from the shared server, and displays the corresponding objects. In the second, there is no common server, and the state of the whiteboard is replicated at each of the users' computers. The application on each computer: Responds to user inputs, and sends updates to all of the other users' computers, including itself. Receives a stream of update messages from other users' computers, processes them, and displays the corresponding objects. It should be clear that if the updates are processed in the same order at each user's computer, those computers will display identical views of the whiteboard. (They are behaving as replicated determinstic state machines). Actually, the requirement of identical ordering is sufficient but not necessary: consider two users drawing in opposite corners of the whiteboard, for example. Can you formulate a weaker rule that will still guarantee consistency? (Hint: think about defining a causal order.) What you should do Form a design team, and give your team a name. Send cse515-hw an email message listing the name of your team and the names of the team members. Your design documents should not have your personal names on them, just the name of your team. Write a high-level design for a distributed object-oriented system that will satisfy Ortenburger and Petrovska. You should describe your basic architectural approach (which will probably be one of the two alternatives outlined above, but might conceivably be one that I have not considered), and say why you have chosen it (e.g., by listing pros and cons for each approach). I recommend the decentraized approach, because the customers do not have a machine available on which to run a server, and because it seems that it will best meet the requirement for disconnected operation. You should also describe the main classes of objects in your system, and give the responsibilities and collaborators for each class (e.g., with CRC cards). You do not have to design every detail of the interface of every object at this time. Objects that already exist in standard libraries, like dictionaries and ordered collections, may be assumed. If you plan to use an existing middleware package, identify the package and briefly explain its capabilities. For example, We plan to use the Camford ordered multicast package, available from `http://www.omc.camford.org.` This package is CORBA accessible, and guarantees delivery of all multicast messages to all members of a group in the same order. Messages from different members of the group are ordered arbitrarily, but the same order is seen everywhere. Your design document should be as brief as possible consistent with meeting these goals. Remember, in the next phase of the project, you will have to read several of these design documents and extract their best features. There is a publicly writeable directory in the OGI file system at /projects/class/cse515/www/projectDesigns. Place your design documents as html (or pdf ) files in this directory before 4PM on 16th February. If your group name is wizards, call the document wizards.html. (Mail a copy to cse515-hw, and keep a copy, in case someone vandalizes this directory!) Try to limit the complexity of your document (for example, don't use a tree of 10 inter-linked html files) since this will make it much easier to print your design. Pictures are OK, in fact, they are encouraged.