4
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

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)

  1. 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.

  2. 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\}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you very much for the answer, but I want to get it clear, even though in case (a) we have numbers of positions of $v$ and $v'$ we don't use it in solution? And in general, if node hasn't sent any message it's pulse always 0, right? $\endgroup$
    – com
    Commented Nov 29, 2012 at 6:11
  • $\begingroup$ well, because in the $\alpha$ case, the node cannot start a new pulse except if all its neighbors are safe. So let's assume that we have a line of nodes $x_1, ..., x _k$, and let's assume that $x _1$ started a pulse 1. Then, $x _1$ cannot start a new pulse 2 except if $x _2$ is safe. The same applies to $x _2$ and $x _3$ .. therefore, until $x _k$ receives pulse 1. Then all the nodes can start a newer pulse after being informed. It's quite confusing, but you can look at it as the dinning philosopher problem. $\endgroup$
    – AJed
    Commented Nov 29, 2012 at 16:33
  • $\begingroup$ Thank you very much for the help, but do you know something about the case when particular node doesn't have any to message, what happens then $\endgroup$
    – com
    Commented Dec 2, 2012 at 13:22
  • $\begingroup$ I think the synchronization algorithm forces it to increase its pulse even if it does'nt have any message to send. Actually, this would be an interesting malicious behavior that can be studied to improve fault-tolerance of the network. It would be interesting to adapt the synchrnoizers to such behaviors. $\endgroup$
    – AJed
    Commented Dec 2, 2012 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.