Let consider well-known problem in distributed computing Broadcast Problem in network with stopping crashes.

The most appropriate solution to the broadcast problem is flooding algorithm, when the source of the message just send it to all available nodes of the network on the first round, if there are crashes on the edges some number of message will fail. Then on the second round, the nodes that received messages from the previous round send it to all available nodes and so on.

Let consider slightly different model, when on every round the source node with message is capable to send a message to only one single node of course stopping failure might occur. It's very useful model, which can represent a sort of controllable or limited spreading.

Unfortunately I don't know the formal name of the model. Do you familiar with result in the model of "limited spreading", I am sure there are must some work in this direction.

• seems like what you're describing is similar to gossiping. You might want to look at " Gossip-Based Computation of Aggregate Information" ( www.comp.nus.edu.sg/~ooibc/courses/cs6203/focs2003-gossip.pdf‎ ) – Peter Jun 9 '13 at 16:48

Both models you presented are the same with a slight modification. Theoreticians usually don't care about the difference between both except when calculating time complexity (or number of sent messages in radio networks sometimes).

The first model you presented, broadcast communication, the broadcast operation is only allowed. That is, a node $v$ may send at one time slot a message to all its neighbours, denoted $N(v)$.

In the second model, point-to-point communication, for a node to send a message to all its neighbours, it needs to send $|N(v)|$ messages each of which is at a different time slot. Therefore, we emulate the broadcast operation.

In the broadcast model, in order to emulate the point-to-point communication from $v$ to $u$, a node $v$ broadcasts a message that contains the identifier of $u$. If $u$ receives the message and finds that it contains its identifier, then it accept it. Otherwise, it just throw it.

• Yes, are your familiar with the following random protocol: on every round a sender (vertices with message) choice a receiver at random and send the message, with $f < \frac{n}{3}$ number of failures, time complexity $T=O(\log n)$ and the protocol succeeds with a high probability. I know, it exists, I am looking for a reference. – user16168 Jun 13 '13 at 16:19
• it should be very well-known algorithm, but I cannot find it, at the begging only a single vertex has a message that should be broadcasted, this vertex choice the receive at random and send him the message (only point-to-point communication), on second round there are two vertices with message that choice their receivers at random and so forth.With number of failures $t < \frac{n}{3}$, the time complexity is $T=O(\log n)$ on the arbitrary graph. The main idea is show that the set of vertices with message continuously grows, whether the set of vertices without message continuously reduces. – user16168 Jun 14 '13 at 2:54