Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
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? –  fog Nov 29 '12 at 6:11
    
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. –  AJed Nov 29 '12 at 16:33
    
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 –  fog Dec 2 '12 at 13:22
    
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. –  AJed Dec 2 '12 at 16:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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