[2020] COMPSCI 711 Parallel and Distributed Computing - Bellman-Ford async vs sync
Question 4 [10 marks] – Bellman-Ford async vs sync
Discuss the distributed Bellman-Ford algorithm, and compare its synchronous and asynchronous versions. Explain why the exponential worst case for the asynchronous version cannot be adapted to construct a similar worst case for the synchronous version.
(a) Complete the diagrams that highlight the exponential message complexity of the asynchronous Bellman-Ford algorithm, by actually indicating required arc delays as integer numbers, starting with 1 for the fast (up/down green) edges.
For example, if delay(e,f) = delay(f,g) = 1, then delay(e, g) = 3. What are delay(c,e),
delay(a,c), delay(g,h)?
(b) Counting the “hops” from right to left, we have delay0 = delay(e,g) = 3, delay1 = delay(c,e) = ?, delay2 = delay(a,c) = ?. What is the general formula, for delayk?
(c) A delay of m time units could be synchronously simulated by inserting m-1 intermediate nodes. For example, to achieve a delay of 3 time units, we could insert two additional nodes between e and g.
Discuss why this construction could not force an exponential number of messages in thesynchronous Bellman-Ford algorithm.
Get the Solution to This Question
WeChat (微信)
WhatsApp
