Stanford University

Computer Science Department

CS 444N M. Baker

Exam Spring 2000

Name:_______________________________________________________________

This is a closed-book examination (i.e. no assistance from textbooks, notes, other people, etc.) You have 45 minutes to answer as many questions as possible. Write all of your answers directly on this paper. Make your answers as concise as possible. (You needn’t cover every available nano-acre with writing.)

In accordance with both the letter and spirit of the Honor Code, I didn’t cheat on this exam.

Signature:____________________________________________________________

Problem 1: (15 points)

Bayou supports four session guarantees to aid users and applications working with weakly consistent replicated data:

• read your writes (RYW): Reads are restricted to copies of the database that include all previous Writes made within this session
• monotonic reads (MR): Read operations are made only to database copies containing all Writes whose effects were seen by previous Reads within the session
• writes follow reads (WFR): a Write is incorporated into a server’s database copy only if the copy includes all Writes whose effects were seen by previous Reads in the session; the new Write is ordered after these previous Writes
• monotonic writes (MW): a Write is incorporated into a server’s database copy only if the copy includes all previous session Writes; the new Write is ordered after these previous Writes

Consider a bulletin board application to which users can read messages, post new messages, and post replies to existing messages, but cannot edit messages once they have been posted. If the user reads a reply to a message, she should also be able to read the original message. Which of these session guarantees would this application require?

Problem 2: (10 points)

Consider a wireless network that guarantees in-order delivery and retransmits lost or delayed packets for up to 500 ms (both at the link layer). How would these characteristics affect the following applications, either negatively or positively, and why?

1. large file transfer over TCP without selective acknowledgements

 

 

 

 

 

 

2. real-time voice over IP

Problem 3: (15 points)

What are the advantages of handling mobility at each of these layers? Keep in mind that handling mobility at layer N means enabling movement while maintaining the same layer-N address.

1. the link layer (e.g. Metricom network)

 

 

 

 

 

2. the network layer (e.g. Mobile IP)

 

 

 

 

 

 

(continued…)

 

 

3. the application layer (e.g. telephone forwarding, email .forward)

 

 

 

 

 

4. the "person layer" (e.g. human assistant, Mobile People Architecture)

Problem 4: (5 points)

Consider the problem of scheduling a CPU to execute a certain set of instructions while minimizing energy consumption. Why is it better to reduce the clock speed by half, than to have the CPU do the same work at normal speed in half the time and then sit idle for the other half the time?

Problem 5: (extra credit)

WAP is:

1. a horrendous perversion of existing Internet standards
2. a blatant case of reinventing the wheel
3. a textbook example of too many cooks spoiling the broth
4. all of the above