Name: AndrewID:

CSE 291 SAMPLE Midterm Exam

Spring 2016 (Kesden)

1.  Networks [10 points]

a.  Given an uncongested 1GBps network with a maximum round-trip latency of 10mS, what would be the maximum useful sliding window size? Why?

b.  Answer exactly one of the following: (i) What are the 5 layers of the network reference model we used in class? Very briefly what are the responsibilities of each layer? (ii) What are the 7 layers of the ISO/OSI model? Very briefly what are the responsibilities of each layer? (iii) Please distinguish the type/character of the service provided by TCP from that of UDP.

2.  Middleware/RPC/RMI [15 points]

a.  Please provide two examples of ways that remote objects necessarily behave differently than local objects, from the perspective of the application programmer. Why are these behaviors necessarily different?

b.  How does the use of proxy objects improve the usability of remote objects, as observed by the application programmer?

c.  How do Java-style interfaces (or abstract base classes in other languages) improve the usability of remote objects, as observed by the application programmer?

3.  Distributed Concurrency Control [25 points]

a.  Why aren’t semaphores a common technique for implanting distributed mutual exclusion?

b.  Under what circumstances might a token ring approach outperform a central-server based approach to distributed mutual exclusion? Why?

c.  One common area of concern in voting based approaches to mutual exclusion and coordinator election involves no-win situations, such as ties and pluralities. Please describe one solution to this problem.

d.  What is the simplest way to prevent deadlock in situations where concurrent processes make use of multiple common resources?

e.  Please answer one of the following: (i) What is starvation? How can it be prevented? (ii) What is fairness? What is a potentially painful consequence of unfair concurrency control?

4.  Coordinator Election [20 points]

  1. One technique for ensuring the robustness of a coordinator is to anoint a slave or secondary coordinator that can enter service should the primary coordinator fail. Another technique is to elect a new coordinator. Please explain the advantages and disadvantages of each approach.
  1. Many mutual exclusion techniques can easily be adapted for coordinator election and vice-versa. From the set of coordinator election techniques and mutual exclusion techniques that we discussed in class, please describe one technique that would be poorly suited for the other purpose, even with reasonable adaptation. What about this technique makes it a good fit for one use, but a poor fit for the other?
  1. We discussed the Bully and Invitation approaches to coordinator election. Are these techniques fair? If so, what ensures their fairness? If not, why is fairness not a particularly compelling concern for coordinator election algorithms, but is for mutual exclusion algorithms?
  1. In the event of a network partitioning, it might be desirable to elect a coordinator in each partition, rather than just one or none at all. Please describe and explain one such circumstances.

5.  Replication and Quorums [10 points]

  1. Consider replication to multiple servers based upon a write-one, read-all static quorum with version numbering. What steps must be taken upon a write to ensure the correctness of the version number?
  1. Consider Coda Version Vectors (CVVs). Give an example of two concurrent CVVs. What is indicated by concurrent CVVs? Please describe one situation in which this might occur.

6.  Design Questions [20 points]

  1. We discussed the use of voting based techniques for enforcing mutual exclusion. Please extend one of these techniques to handle the more general problem of at-most-n-user and describe your solution.
  1. Consider a situation with 5 replica servers employing a write-2/read-4 policy and version numbering. Please design and describe a locking scheme that ensures that version numbers remain correct, even in light of concurrent writes. You do not need to consider failure. But, you do need to describe all necessary communication and state, such as communication between or among servers and/or participants.