1. consider the following program:
process P
var
sent=0;
*[true -->
send message(s) to Q,
sent=sent+1]
process Q
var
rcvd=0;
*[
message in channel from P -->
receive message(r) from P,
sent:=sent+1 ]]
rcvd:=r
]
a) Assume that it is coded on a real distributed architecture where the latency of message transmission between processes of P and Q is high (messages take very long to propagate).
What computations would reflect this behavior? Give examples. Explain.
b) Assume that the channel is fast but process Q is significantly slower than P. What computation would reflect this behavior? Give examples. Explain.
c) Assume that process P, Q have about the same speed in the target architecture, however, P seldom has any messages to send to Q. What computation would be appropriate for this behavior? Give examples. Explain.
2. Assume that a distributed program is written in a program-counter sequence of statements of the form assign initial values to variables;
statement1; statement2; statement3; statement4;
...
based notation. That is, it has a
Assuming that the atomicity of the program is the statement, construct an equivalent guarded- command based program. In this the equivalence means the program generates the same set of computations.
3. Convert Tarry's traversal algorithm (see our class slides on Traversals) into guarded command notation, discuss why your guarded-command based program is equivalent.
4. Assume the following modification for the Ring algorithm (See class slides on Waves)
proc initiator const
Next, Prev (* next and previous neighbor *) var
boolean started=false, gotone=false
*[
not started -->
started:=true
send to Next send to Prev
[]
receive from Next or Prev -->
if gotone then decide
else gotone:=true
]
proc non-initiator const
Next, Prev *[
receive from Prev --> send to Next
[]
receive from Next -->
send to Prev ]
a) formally prove or disprove that this is a wave algorithm
b) for a particular ring size of N processes count the number of non-equivalent computations c) compute the time and message complexity of the algorithm
5. Consider the following modification of the ring algorithm
proc initiator const
Next, Prev (* next and previous neighbor *) var
boolean started=false,
*[
not started -->
started:=true
send to Next send to Prev
]
proc all processes (including initiator) const
Next, Prev *[
receive from Prev --> send to Next
[]
receive from Next -->
send to Prev ]
Does this algorithm have computations that are not weakly fair? If your answer is negative, prove it; if positive: show a weakly unfair computation. Do not worry about the lack of "decide" event at the initiator: it is made to simplify the code; the answer does not depend on it.
6. Prove (provide convincing argument) or disprove (provide a counter-example) that every computation of any wave algorithm is weakly fair.
7. Will the tree algorithm (see class slides on Waves) work on non-tree networks? That is, there are no modifications to the algorithm but the topology of the network is not a tree. Explain your answer.
For the following topology:
ab \/ c /\
de
List a pair of computations that are not equivalent and explain why they are not equivalent.
8. Assuming that "a" is the initiator, list all possible spanning trees that can be formed for the following topology:
a----b |\ | |\| |\| | \| c----d
Show which ones can be produced by:
a) Tarry's algorithm b) Classical algorithm
9. Auerbach's algorithm is a modification of the classical depth-first traversal algorithm. The major change is that two new types of messages are introduced: and and the update rules for "used" array are modified. As a consequence of that it becomes necessary to explicitly require that only the initiator decides (notice that in Tarry's and Classical traversal algorithm it is done implicitly -- the only process that can possibly decide is the initiator). Explain why it is necessary and give an example where the Auerbach's algorithm without this particular modification fails.
10. In Auerbach's algorithm. When a process P receives message it first sends message to every neighbor, waits for from every neighbor and then proceeds to forward .
Would the algorithm be correct if a process does not wait for s to come back but forwards immediately after messages are sent? If yes, explain why; if no, explain why and provide a counter-example