Systems qualifying exam - NDS
Ed Swierk
28 May 2002

I acknowledge and accept the Honor Code. ___________________________________

1.

+: advantage of leases
-: disadvantage of leases

(a)
- communication overhead can be higher than callback approach for heavily
  shared files due to frequent renewals of short leases
- application needs to predict its access pattern to determine what lease
  duration to request
- server harder to implement since it has to keep track of lease times in
  addition to which client has a lease on what
  
(b)
+ leases preserve sequential consistency and availability (assuming lease
  duration is sufficient); callbacks during disconnection can be missed,
  allowing multiple clients to write the file (but since AFS guarantees only
  session consistency this is not considered a failure)
- temptation to make leases unnecessarily long can make files unavailable
  to other clients during disconnection

(c)
- server must either record leases in stable storage (e.g. writeahead log) or
  upon recovery refuse requests for new leases for the maximum lease duration
  to prevent violating sequential consistency; for AFS the server can just
  issue callbacks to all clients upon recovery (assuming it at least knows
  who its clients are)
  

2.

(a)
Yes, if the low bandwidth results in congestion in the reverse direction
(e.g. due to multiple concurrent TCP connections or other traffic) then
acknowledgements can be delayed due to queueing, resulting in unnecessarily
slow ramp-up during slow start.

Also, slow acknowledgements can cause both sender and receiver to keep
larger buffers (sender: unacked segments; receiver: missing segment followed
by unacked segments).

(b)
Cumulative acks reduce traffic in the reverse direction.  For example, say
the window size is large and a segment gets lost.  The sender eventually
discovers this (due to repeated acks) and recovers my rexmitting the lost
segment.  When the receiver finally gets the missing segment, it needs to ack
the numerous segments it has received with higher sequence numbers.  With
cumulative acks it can send a single cumulative ack with the next expected
sequence number.


3.

UDP advantages:
- RPC reply can serve as ack of request
- no connection set-up overhead for short or infrequent requests
- supports broadcast and multicast

UDP disadvantages:
- lacks retransmission mechanism
- still need separate acks for operations that take a long time
- still need flow control
- need a way to split long requests and responses (due to MTU)
- authentication/encryption usually require multiple packets (obviating some
  of the advantages)
- hard to get through firewalls and NAT boxes

TCP advantages:
- acks, retransmission, flow control built-in
- easy to implement authentication/encryption on top
- easy to pass through firewalls and NAT boxes

TCP disadvantages:
- 6-packet overhead for connection set-up and teardown (assuming no T-TCP)
- acks unnecessary for short or infrequent requests
- requires a proxy to support broadcast or multicast


4.

Need to consider Byzantine failures, where nodes or subsystems can engage in
arbitrary and possibly malicious behavior.

A commit protocol that works in the presence of such failures requires
participation from the applications.

Also, since the reliable delivery protocol is implemented in the network
drivers, there is no guarantee that the OS will pass messages reliably to
the application unless the OS is also trusted.

The protocol cannot protect against denial-of-service attacks where numerous
(correct) junk messages are received but prevent legitimate messages from
getting through.