1
$\begingroup$

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.

$\endgroup$

migrated from cstheory.stackexchange.com Jun 11 '13 at 9:09

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ 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‎ ) $\endgroup$ – Peter Jun 9 '13 at 16:48
1
$\begingroup$

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.

does that answer your question ?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user16168 Jun 13 '13 at 16:19
  • $\begingroup$ can you be more detailed ? I remember some of these randomized fault-tolerant algorithms, but I dont understand your algorithm. $\endgroup$ – AJed Jun 13 '13 at 19:45
  • $\begingroup$ 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. $\endgroup$ – user16168 Jun 14 '13 at 2:54
1
$\begingroup$

Canonical solutions to the broadcast problem include, as you mention, flooding (controlled & uncontrolled, although uncontrolled flooding is untenable for a variety of reasons), as well as spanning-tree based approaches and N-way unicast (which is basically just to point out that broadcast protocols don't represent fundamentally more powerful communication mechanisms).

What you're asking about sounds somewhat similar to a sort of controlled flooding with fault tolerance. Alternatively, you might conceive of your scheme as a spanning-tree approach where multiple redundant spanning trees are defined for each node. In fact, a hybrid of these approaches would help avoid loops, explosion, etc.

Kurose and Ross provide a good explanation in their book "Computer Networks - A Top Down Approach", which you might use to develop your own broadcast protocol.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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