Algorithm of Communication with Failures

Question

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.

Answer 1

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.

Answer 2

First let's look at the failure-free case:

The algorithm that you're describing, namely forwarding the message to a uniformly at random chosen neighbor, is essentially a gossiping algorithm.

Clearly, the $O(\log n)$ bound does not apply for arbitrary networks, which might have a diameter of $\omega(\log n)$, so the algorithm will terminate with probability $0$ in $O(\log n)$ rounds.

The (failure-free) model was studied for example in [1], but there's much prior work (see references in [1]):

In this model, nodes do not know the global topology of the network, and they may only initiate contact with a single neighbor in each round.

[1] show the general upper bound of $O(\phi^{-1}\log n)$ where $\phi$ is the conductance of the graph.

Regarding the case where $f$ links can fail: I'm assuming that you're talking about the failure model where messages can be lost over links and not corrupted, right?

Here the answer depends on what kind of adversary you're looking at. Does the adversary choose the $f$ failures in advance or can it observe the random choices of the algorithm? In the former case, we can simply discard those $f$ links from $G$ and get a new (sparser) network $G'$ with conductance $\psi$, which yields the upper bound $O(\psi^{-1}\log n)$, (for the smallest possible $\psi$).

[1] Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance. http://arxiv.org/abs/1104.2944 By Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov