If you want to make money online : Register now

[Solved]: Algorithm of Communication with Failures

, , No Comments
Problem Detail: 

I am interested in Distributed Algorithms especially in communication in network with failures.

I look for the proof of the following randomized algorithm of communication in network with failures. For me it seems like very general result in the communication, nevertheless I haven't found the proof yet.

Algorithm: Initially only vertex $v_0$ has the message, at the end of the algorithm every vertex of the network should have the message.

On every round every vertex that has the message choice the neighbour randomly and sends it the message.

Assumptions: only $f$ failures might happen on the edges between the vertices. $T = O(\log n)$ - time complexity and the entire network will know the message with high probability, when $f<n/3$, where n - number of vertices.

I will appreciate for link or reference to the paper.

Asked By : com

Answered By : Ran G.

The problem you state is very close to the problem of Byzantine Agreement with faulty links. Yet, it is not clear to me what is the guarantees you seek out of your algorithm.

The algorithm you give does not solve the Byzantine-agreement problem. Specifically, if the party that holds the message is corrupt, and it begins by sending $v_0$ to some player but also $v'$ to other player, then your algorithm will not converge (that is, maybe everyone will have $v_0$, but they will also have $v'$ and will not know what is the message that was originally sent). If you don't care about the parties having $v'$ as well, then why not just sending the message to all the parties (then repeated by each node)?

Note that when links fail, there is a question of connectivity. For instance, if one of the nodes is not connected to any other nodes (all the edges between are faulty), then that node will never get the message. Of course, if the number of faulty edges $f$ is less than $n/3$, and assuming each two nodes are connected, there is no problem at all.

The following paper might be at your help: Vassos Hadzilacos, Connectivity requirements for Byzantine agreement under restricted types of failures, Distributed Computing, Volume 2, Issue 2, pp. 95-103, 1987. That paper deals with Byzantine agreement with $t$ faulty nodes and $k$ faulty links, and it holds for any architecture of the underlying graph (as long as some connectivity condition holds).

You might also want to take a look at the case where only nodes are faulty. See for instance, K. Perry, Randomized Byzantine Agreement, IEEE Trans. on Software Engineering, Vol SE-11, Issue 6, pp. 539-546, 1985.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11590

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback