CSC 2/456 Distributed Programming Assignment

You are to implement a solution to a generalized distributed version of the Dining Philosophers problem. As motivation, consider a network of cellular telephone base stations. (This is a contrived example, and probably not the way real cell phone systems work, but hopefully it gives you a sense of why the algorithm might be useful.) With first-generation cell phone technology, each phone in a given cell communicates on a different frequency (this of course limits the number of active phones in a cell), and no frequency in use in a given cell may be used in any neighboring cell (call this the no-interference invariant).

From time to time, depending on the demand for connections, the number of frequencies in use in a given cell may need to change. When it needs a new frequency, a cell must synchronize with its neighbors to maintain the no-interference invariant.

In the classic Dining Philosophers problem, five "philsophers" sit around a table containing a communal plate of spaghetti. Between each pair of adjacent philosophers a fork lies on the table. Each philosopher repeated thinks for a while and then gets hungry. To eat, the philospher must pick up both adjacent forks. The challenge is to prevent the deadlock situation in which each philosopher has picked up the fork to the right (or left) and none can pick up the one to the left (or right).

In the cell phone example, the base stations correspond to philosophers and the copper of fibre connections between base stations correspond to forks. We have generalized the problem to allow an arbitrary graph of base stations (philosophers), rather than a five-station circle.

When a cell phone hangs up, the frequency it was using becomes unused in the current cell. When a cell phone is activated and requests a dial tone, the base station must allocate a frequency. To do so it must first "acquire" the "forks" it shares with its neighbors, to make sure that none of them uses the same frequency. In the process of acquiring "forks", the station obtains a list of frequencies in use by its neighbors. Once it has acquired all "forks", the station chooses a frequency (if any) that is not being used by any neighbor. If there is no such frequency, it denies service to the cell phone requesting a connection.

Your solution to cell phone problem must satisfy the following constraints:

Fairness
A base station that wishes to acquire all its "forks" must eventually be able to do so.
Symmetry
All base stations must follow exactly the same policy. You are not allowed to depend on any notion of priority or other static partial order among stations.
Economy
Each station must send a bounded number of messages between allocation decisions.
Concurrency
Non-adjacent base stations must be able to make allocation decisions simultaneously.
Boundedness
The size and number of messages in transit (sent but not yet received) on a given connection between stations must be bounded.

I recommend you use the algorithm summarized below. It is due to Chandy and Misra, and was published in the ACM Transactions on Programming Languages and Systems in October of 1984. A scanned copy is available on-line in the cs and csug networks.

The key to the algorithm is to establish a temporary, relative notion of precedence among each pair of adjacent base stations. We can represent this precedence by assigning a direction to each edge of the graph: the directed edge A -> B indicates that A has precedence over B. When A and B both want to allocate a frequency, and neither is prevented from doing so by activity in some other neighbor, our algorithm will be designed to let A win.

To avoid deadlock (that is, to avoid violating the fairness property), we must ensure that the directed graph is never circular. We can ensure acyclicity at start-up by giving processes with higher process ids initial precedence over processes with lower ids. That is, A -> B <=> A.pid > B.pid.

To achieve symmetry, we must alter the relative priorities of neighbors over time, taking care to keep the graph acyclic. We can achieve this goal by having each station make all its incident edges point toward itself (thereby yielding precedence to all of its neighbors) whenever it makes an allocation decision (i.e., whenever it allocates a frequency or discovers that it cannot do so, and instead denies service to a phone).

In addition to precedence, each edge carries a notion of ownership. A base station S is permitted to make an allocation decision if (1) S owns all adjacent edges, (2) S has received all outstanding messages on each adjacent edge, and (3) for each edge, either S has precedence over the corresponding neighbor or the neighbor has not requested ownership. When it wants to make an allocation decision but lacks ownership of a given edge, S requests that ownership from the corresponding neighbor. When it receives a request for ownership of an edge, S grants the request if any only if the neighbor currently has precedence. As noted above, when it makes an allocation decision, S yields precedence over all adjacent edges to the corresponding neighbors. These rules require S to remember, for each owned adjacent edge, whether it has made an allocation decision since acquiring ownership, and, for each unowned edge, whether it has requested ownership since losing ownership. S is said to have precedence over a given neighbor T if (1) S owns the connecting edge and has not made an allocation decision since gaining ownership, (2) T owns the edge, but has made an allocation decision since gaining ownership, or (3) T has sent a message to S giving it ownership of the edge, but S has not yet received the message. A more formal statement of the algorithm can be found in the Chandy and Mirsa article.

Your code should be structured as a master process and a collection of base station processes. You should start the master process from the console, passing it appropriate arguments. Based on those arguments (or on configuration information in a file specified among those arguments), the master process should start a collection of appropriately connected base station processes. The master must allow the human user to specify the graph of base stations and links, and the machines on which the base stations should run. You should test your code on a single machine at first. Once it is running, you should try spreading the process around among the machines in the lab, using rexec() or system(rsh()) to start them. Your processes should communicate using TCP/IP. They should produce output sufficient for the TA to verify that they operate correctly. To make it easier for a human observer to see what's going on, I recommend you introduce random multi-second delays between allocation decisions by any given process.

Additional assignment for 456

In addition to the generalized dining philosophers problem described above, you are to implement a solution to the so-called Drinking Philosophers problem. In this problem the edges between nodes in the graph of philosophers represent various sorts of "bottles". From time to time a philsopher becomes "thirsty" for some subset of the bottles. To drink it must acquire ownership of the desired bottles, but need not acquire the others. The key difference from the Dining Philosophers problem is that it must be possible for two neighboring philosophers to drink at the same time if they do not both desire the bottle corresponding to the edge between them. For more details on this problem, and a suggested solution, see the Chandy and Mirsa article.

Trivia assignment

By the date shown below, e-mail a postscript document to cs456 containing answers to the following questions:

  1. Who are the members of your team? (They need not necessarily be the same as last time.)
  2. What are the similarities and differences among rexec and rsh?
  3. What library call(s) should a base station use to receive any available message from any neighbor? (Hint: read the section-3 man page for select.)
  4. In the Chandy and Misra solution to the Dining Philosophers problem, does a philosopher always know whether it has precedence over a given neighbor? Why or why not?
  5. (456 only) To solve the Drinking Philosophers problem, why can't we simply follow the Chandy and Misra Dining Philosophers protocol on precisely those links representing bottles from which we want to drink? Alternatively, why can't we follow the full Dining protocol and then only use the bottles we want?

DUE DATES:

Remember: No extensions.


Back to the assignments and grading page

Back to the course home page

Last Change: 1 April 2000 / Michael Scott's email address