[2020] COMPSCI 711 Parallel and Distributed Computing - Cidon's DFS
Question 3 [10 marks] – Cidon’s DFS
Discuss Cidon’s distributed DFS and explain how it improves over the naïve distributed DFS. If needed, use the following network diagram to clarify your arguments.
As an example, consider the following network, where node #1 is the start, and the following message types: fwd (forward), ret (return), vis (visited), and assume that fwd also carries the vis token.
(a) Using the above diagram, identify a particular asynchronous execution in which the forward token is sent to an already visited node.
Illustrate this execution by time-lines, one for each node, indicating sent/received messages and their global timestamps, using integer numbers (so the smallest time unit will
be 1), e.g.:
P1 timeline: send1(fwd):0, …
P2 timeline: receive1(fwd):1, send2(fwd):1, send3(vis):1, …
…
(b) How many messages are sent in scenario (b) and what is its normalised time complexity?
Get the Solution to This Question
WeChat
WhatsApp
