Homework 3

Due on 9/28/1999
Problems: 4.2, 4.7, 4.11, 4.13, 4.20, 4.23, 4.25

Homeworks were only accepted from teams. All homework papers should have on them:

the class prefix and number,
the date,
the assignment number,
the problem numbers,
the printed names of each team member, and
the signature of each team member beside their name,
an indication of which members played the special roles below.

4.2)
a) What is the advantage of using keys?
You can have multiple producers and consumers using the same mailbox or port.
You can use it to implement priorities.
Implement a dictionary-type structure where you store keyed values.

b) Blocking or non-blocking?
Producer/Consumer: Producer is non-blocking, consumer is blocking.
Priorities: Non-blocking because you could wait indefinetly for the key.
Keyed values: Blocking.

c) How should source and destination be identified?
Not needed, just need to use the same mailbox or port.

d) Relate this receive primitive to the two-producer, two-consumer problem.
See 4.2.a)

4.7)
a) What is the effect on the protocol's correctness and performance?
Correctness is not a factor. It is assumed/implied that a receiver will request a previous message from the server if it gets a message that is out of sequence. It will always remain correct, but will lead to delays. If the server then freezes, it will block the receiver. The receiver always needs to get the remaining messages.

b) Why is this limited to multicast in a single group?
The problem is that you would have different sequence numbers. It would be the same thing as losing a message.

4.11)
a) Asynchronous RPC:
The caller can continue with its own process after making a call to another host.

b) Light-weight RPC:
This is esentially what the synchronization package for user-level threads uses. It could be used in the same manner as threads.

c) Null RPC:
Could be used to test if the other host is still responding and kicking.

4.13)
a) Recovering Client?
Needs to remember what happened. Needs to inform server. If client never wakes up, then server never cleans up. Don't need any state info on server though.

b) Recovering Server?
Server may incorrectly kill off something. It also needs to maintain state info for each client, and is more work/complicated.

c) Expiration?
May also kill off clients inappropriately.

4.20)
a) When do they need to be invalidated?
Whenever the name of a host has a different ip address.

b) Propose a scheme:
Whenever a client requests an ip address for a remote host, the name server stores the client ID. Then, when the ip address of that remote host changes, the name server sends a message to all clients that have that host cached.

Note: There was a lot of confusion regarding this problem. The premise was that the cache was located on a client computer, and that a name server is available. When a remote host changes its ip address, the changes are replicated to the name server. The question is how does the client update its cache so that it can now find the new ip address of the remote host.

4.23)
a) What does the request queue look like at each node?

Node Queue

1 2 1

2 5 4 2

3 6 3 1

4 4

5 5

6 6

7 3

b) How are the request queues linked to form a global FIFO?
The request queues are linked by appending the current queue. In other words, if I pass the token along and have a non-empty queue, then my queue is appended to the queue of the next node.

c) What is the order of execution?
7,6,3,5,4,2,1

4.25)
Using Kruskal's Minimum Spanning Tree algorithm, we get O(|E|log|E|). Note that is not the same as O(nlogn).