Problem Set #3

Problem Set #3
Fall, 2009
Assigned: Wednesday, September 9
Due: Tuesday (noon), September 15
Total Points: 20

Please submit your answers in PDF format via email.

1. (6 points). Following the examples in the paper "Events Can Make Sense" show how to implement a procedure that allows an operation to be started and also provides a way for the caller to cancel the operation at a later point in time. The signature of this procedure is:

    tamed dnslookup-cancel (dnsname name, ipaddr a, event<bool> &cancel)

which might be used by a caller as follows:

    dnsname name;
    ipaddr addr;
    event<bool> cancel;
    ...
    dnslookup-cancel(name, addr, cancel)
    ...
    cancel.trigger(); /* this cancels the operation */
(Hint: see the example in Figure 5 of the paper).

2. (10 points) Multicasting means that a single message sent by a sender is received by all receivers. Multicasting is often used in system built for reliability where each receiver is performing the same computation, to deliver events from an event channel to all interested parties, or in protocols attempting to achieve agreement among distributed processes.

In this problem set, you will be asked to implement a simplified multicasting protocol using CSP. In this system there are three types of processes: a single Sender process, a single Multicast process, and n Receiver processes. The simplified protocol has three required properties:

A. each message sent by the Sender process is delivered exactly once to all Receiver processes.

B. the Sender is not allowed to present to the Multicast process send a second message until the the previous message has been received by all receivers.

C. a Receiver process ready to receive its copy of the message should not be blocked if the message is available at the Multicast process and no other Receiver process is ready to receive its copy of the message.

(a) (3 points). Suppose that the Multicast process were implemented as shown below. Which of the three requirements does this implementation
satsify? Which does it not satisfy? Explain you answer.

Multicast::*[ Sender?msg --> i: integer; i=1; *[i<=n --> Receiver(i)!msg; i := i+1 ]]

(b) (7 points). Show the CSP code for the Sender, Multicast, and Receiver processes which together satisfy the three properties given above. Be sure that you have considered all of the conditions necessary to implement a system in which the sender sends more than one message. You are allowed to introduce new types of processes.

3. (4 points) State four insightful questions for discussion in class about Chords and/or the Pi-calculus based on your reading of the papers available on our web site.