Stanford Distributed Systems and Networks Quals

2002 2001 2000 1999 1998 1997 1996 1995

2000 Problem Set

The objective of the exam is to find out what you know about distributed systems and networks and to assess your ability to identify and develop solutions for problems that arise in this area. Note that the questions may have many "correct" answer, so be sure to provide justifications for your answers. State any assumptions you make when answering the questions. The points in parentheses are a rough indication of how many minutes to spend on each question. The exam is closed-book. Brief, "bullet-style" answers are welcome. Problem 1 (15 Points) When TCP receives an out-of-order segment, it is required to send an immediate ACK, called a "duplicate ACK", to let the sender know that a segment was received out of order, and to tell it what sequence number is expected. After receiving three of the same duplicate ACKS in a row, older TCP senders enter slow start.

     a) Why wait for three duplicate ACKS and not just one before entering slow start?

Some newer TCPs do a fast retransmit of the missing segment after three duplicate ACKS and then enter congestion avoidance, rather than slow start.

     b) What is the benefit of this change?

     c) Why did the designers of these newer TCP implementations assume that a fast retransmit, without entering slow start, is probably sufficient response to the receipt of three duplicate ACKS?
Problem 2 (15 Points) NFS (Sun's Network File System) is considered a "stateless" protocol in that file servers do not need to keep any connection information about clients.

     1) What are the advantages of stateless file servers?

     2) What are some disadvantages? That is, what are some kinds of state information it might be valuable to keep on the file server, and why?
Problem 3 (10 Points) What is idempotency? Why is it often a good property for protocols for distributed systems to have? Problem 4 (20 Points) Using pseudo-code, describe the Two-phase Commit Protocol. Describe three different scenarios where one or more of the participants in the protocol crashes at some state of the protocol. Explain how the protocol copes (or does not) in each scenario.

Maintained by Gurmeet Singh Manku