Problem Detail: I experience a difficulty in solving exercises in distributed algorithm. Below is the the exercise I try to solve, it looks like I miss basic idea. Exercise. Consider a 15-processor asynchronous network with processors 0,…,14. The processors constantly run a synchronizer. Let $v$ and $v’$ be two processors in the network, and suppose that at a certain moment, the pulse counter at $v$ shows $p=27$. What is the range of possible pulse numbers at $v’$ in each of the following cases: a) The network is a ring, $v$ is processor number 11, $v’$ is processor number 2 and the synchronizer used is $alpha$. Idea: if $v’$ hasn’t sent any message up to pulse 27 of $v$, pulse of $v’$ is still 0, therefore lower bound of pulse of $v’$ is 0. The model of synchronizer is $alpha$ it means every node informs all nodes about it’s safe(v,p) state, hence I assume that $v’$ might be 11-2=9 pulses before $v$. b) The network is a full balanced binary tree (4 levels), $v$ is the root, $v’$ is one of the leaves and the synchronizer used $beta$. Idea: $v’$ also might have pulse 27, in this case $v$ sends at speed of $v’$. c) The same as in (b), except both $v$ and $v’$ are leaves. Honestly, I am completely confused by this exercise, I wrote few ideas, but I don’t have any understanding and any intuition behind the answers. I will appreciate if someone show me the way how to solve such exercises.
Asked By : com
Answered By : AJed
Please find solutions of all cases: For case A ($alpha$-synchronizer), the pulse at a node can either be more, equal, or less by one (therefore, ${26,27,28}$). This is because a node must inform its neighbors about its safeness and not all the other nodes (according to your question). You can see the rules in the following (copy-pasted from the paper)
- A new pulse may be generated at a node whenever it is guaranteed that no message sent at the previous pulses of the synchronous algorithm may arrive at that node in the future.
- Using the acknowledgment mechanism described above, each node detects eventually that it is safe and then reports this fact directly to all its neighbors. Whenever a node learns that all its neighbors are safe, a new pulse is generated.
For case B: ($beta$-synchrnoizer) – if $v$ is the root, then at $v’$ the pulse is either the same or less (therefore, ${26,27}$). For case C: ($beta$-synchrnoizer) – if both $v$ and $v’$ are leaves, then here we may assume that the broadcast of the root is not received at the same time – since the network is asynchronous (otherwise, why would we need a synchrnoizer). Here, if $v$ is 27 then $v’$ is either 28 if the update of $v’$ is received before $v$ ,, or 26 if the update of $v’$ is received after. Or they both have the same pulse (therefore, the range is ${26,27,28}$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7001
