Homework 1
Due on September 19, 2003
1. Problems from Chapter 2 of text book: 2.2, 2.6, 2.8, 2.12.
2. Binding server used in distributed systems supporting RPCs help the caller to identify the location (the system) of the callee. The exact mechanisms used by the binding server varies accoring to its implementation. Check on the Sun Unix implementation and write a short report on how the binding servers work in Suns.
3. Consider a cut of a distributed computation, C = {c1, c2, c3, c4}. VTc1 = {5, 2, 4, 7}; VTc2
= {3, 6, 4, 6}; VTc3 = {4, 5, 7, 4}; VTc4 = {3, 4, 6, 8}. What is the value of VTc? Is C a
consistent cut?
4. Identify the consistent (if any) and strongly consistent (if any) global states in the following diagram.
5. What are the strongly consistent global states in the following space-time diagram?
6. Consider the following two space-time diagrams. Use SES (Schiper-Eggli-Sandoz Algorithm) to decide whether a message is to be buffered or delivered, and indicate it as such in the space-time diagram. (For instance, you may use dotted arrows to indicate buffering and solid arrows to indicate delivery). Explain the contents of V_Pi (i = 1, 2, 3) for all processes after every message is sent or received. Also, specify the vector clock of each process for every event (sending/receiving a message).
(i)
(ii)
7. Consider the following space-time diagram. Using BSS algorithm, what should be the vector clocks of P1, P2, and P3 at the end? (i.e., after all the message exchanges). Order the messages (using the BSS algorithm) before marking the clock vallues).
(i)
(ii)
8. Consider the following space-time diagram. Label the event points using:
- Lamport’s logical clocks
- Vector clocks
- Time of cuts Ca (={C1,C2}) and Cb (={C3,C4}).
(3 Marks)
9. A distributed computation application uses Huang’s termination detection algorithm.
Computation starts at process P (which acts as the controlling agent). P asks P1 to do some
computation. P1 requests P2 to do part of its computation. P2 passes on part of its job to P3.
After some time, P1 uses P4 to carry out another part of its computation. Draw a process-tree
diagram and mention the weights assigned to each process.
Now, the computation completes in the following sequence: (a) P4 completes and hands over the results to P1; (b) after that, P3 hands over the results to P2; (c) then, P2 passes the results to P1; (d) finally, P1 hands over to P. Draw the process-tree diagram for each of the step (a)-(d) and indicate the weights at each process.
Multiple Choice Questions:
1. Choose the true statement(s) with respect to CSP.
(a) Guards in CSP can handle only one Boolean condition. For multiple Boolean conditions, we need multiple guards.
(b) If an output command is present as part of a repetitive command, the execution of the repetitive command might get delayed till the message (sent as part of the output command) is received.
(c) Output commands need not specify the name of the receiving process, it can simply output the value.
(d) The name Communicating Sequential Processes (CSP) implies that it is not possible to have concurrent process executions in CSP. One can have only sequential process executions.
Answer:
2. Consider the following Serializer program segment.
procedure write(k:key, data:datatype);
begin
i. enqueue(writeq) until (empty(rcrowd) AND empty(wcrowd) AND empty(readq));
ii. joincrowd (wcrowd) then write-db(db[key], data);
end
Statement (ii) in the above program segment implies:
(a) There can be multiple writers carrying out write-db operations, since “joincrowd(wcrowd)” means a crowd of writers.
(b) Assuming choice (a) is true, if multiple writers carry out write-db operations in joincrowd, mutual exclusion will be handled by the underlying database management system.
(c) Joincrowd does not always mean that multiple processes must execute the body of statements in joincrowd. Number of processes in the crowd depends on the conditions used for enqueue command as well.
(d) It is difficult to answer how the above program segment will behave unless we know the characteristics of the underlying database management system, i.e., whether it supports concurrent write access or not.
Answer:
3. Consider the following monitor program segment.
readers-writers: monitor;
begin
readcount: integer; busy: Boolean;
OKtoread, OKtowrite: condition;
procedure startwrite
begin
if busy OR readcount != 0 then OKtowrite.wait;
busy := true;
end startwrite;
procedure endwrite
begin
busy := false;
if …………………..then ………….
else ……………………..;
end endwrite;
Procedure endwrite should have the following condition for ensuring writers priority.
(a) If OKtoread.queue then OKtoread.signal else OKtowrite.signal
(b) If OKtowrite.queue then OKtowrite.signal else OKtoread.signal
(c) It is not possible to specify the condition unless we know the condition in the corresponding read procedure.
(d) If OKtowrite.queue then OKtowrite.signal (no need for else clause).
Answer: