World's most popular travel blog for travel bloggers.

, ,
Problem Detail:

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.

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.