Stanford Distributed Systems and Networks Quals

2002 2001 2000 1999 1998 1997 1996 1995

1995 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 more than one "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. Problem 1 (15 Points) In some asymmetric networks the available bandwidth in one direction is much less than the available bandwidth in the other direction. Consider a network in which communication from a server to clients is handled via broadcast at 1 Gigabit/second. Unfortunately, the back-channel from each client to the server is only 1 Kilobit/second and has a high latency of 10 seconds.

You've been asked to design a distributed file system using this network. Assume the server is always available and is able to store all the files in the system. Assume the clients each have a small local disk and some reasonable amount of main memory for a file cache (10 Megabytes each).

In your design, how would you use the available network resources? How would you arrange for clients to receive copies that they need? Would you allow files on the server to be writable as well as readable? If so, what sort of cache consistency might you provide, if any?
Problem 2 (15 Points) You work for a company that seems happy to purchase workstations with large main memories and local disks for every employee, but they are queasy about purchasing machines to be designated as shared file servers. Nonetheless, your company needs some sort of distributed file service. You decide to implement a distributed file service that uses all the clients cooperatively. In particular, to eliminate central server file caching, you decide to allow all the clients to perform file caching duties for each other.

How might this solve your problem? What advantages does it have? What disadvantages does it have? (Consider such issues as latency of file accesses, throughput, availability, cache consistency, complexity, and trust.) What sort of cache consistency protocol might you propose?
Problem 3 (15 Points) A long-time goal in distributed systems has been location transparency -- one should not need to know the physical location of resources or users in order to communicate with them. Some systems have taken this point to an extreme and attempt to hide the location of entities in the system.

In networks of mobile hosts, this issue is being reconsidered. One proposal includes making location information about users, hosts and resources available to applications and users. Describe the advantages and disadvantages of this proposl. (Consider issues such as performance, network routing choices, and privacy.) What application(s) might this proposal enable?
Problem 4 (15 Points) Recently it has been suggested by some researchers that DSM (distributed shared memory (*)) is an appropriate application for a mobile, wireless computing environment. In this environment the hosts have about 20 Megabytes of memory each, moderately-sized local disks, and reasonable processor speed. Communication takes place over a 9.6 Kilobit/second network that suffers from a high bit error rate and intermittent lapses in connectivity. Do you think this idea is splendid, outrageously stupid, or just so-so? Why? If you had to implement DSM in this environment, what sorts of problems would you expect to see? How would you address these problems? What sort of memory consistency model(s) might you choose? What applications, if any, would you expect to run well on top of DSM in this environment? (*) A distributed shared memory system is one in which threads of a user process running on different hosts can all share virtual address space or can at least share various data structures in the virtual address space.

Maintained by Gurmeet Singh Manku