The original algorithm is available at here.
The proposed algorithm as follows:
Algorithm Lazy Probabilistic Broadcast (data dissemination)
Implements:
ProbabilisticBroadcast (pb).
Uses:
FairLossPointToPointLinks (flp2p);
UnreliableBroadcast (un).
upon event _ Init _ do
for all pi ∈ Π do
delivered[pi] := 0;
lsn := 0;
pending := stored := ∅;
procedure deliver-pending (s) is
while exists [Data, s, x, snx] ∈ pending such that
snx = delivered[s]+1 do
delivered[s] := delivered[s]+1;
pending := pending \ {[Data, s, x, snx]};
trigger (pbDeliver | s, x );
procedure gossip (msg) is
forall t ∈ pick-targets (fanout) do
trigger _(flp2pSend | t, msg );
upon event ( pbBroadcast | m )do
lsn := lsn+1;
trigger (unBroadcast | [Data, self, m, lsn] );
upon event (unDeliver | pi, [Data, sm, m, snm]) do
if (random() > store-threshold) then
stored := stored ∪ { [Data, sm, m, snm] };
if (snm = delivered[sm]+1) then
delivered[sm] := delivered[sm]+1;
trigger _ pbDeliver | sm,m _;
else if (snm > delivered[sm]+1) then
pending := pending ∪ { [Data, sm, m, snm] };
forall seqnb ∈ [delivered[sm] + 1, snm − 1] do
gossip ([Request, self, sm, seqnb, maxrounds−1]);
startTimer (TimeDelay, sn, snm);
end if
Algorithm Lazy Probabilistic Broadcast (recovery)
upon event (flp2pDeliver | pj, [Request, pi, sm, snm, r] )do
if ([Data, sm, m, snm] ∈ stored) then
trigger _ flp2pSend | pi, [Data, sm, m, snm] _;
else if (r > 0) then
gossip ([Request, pi, sm, snm, r − 1]);
upon event _ flp2pDeliver | pj, [Data, sm, m, snm] _ do
if (snm = delivered[sm]+1) then
delivered[sm] := delivered[sm]+1;
trigger _ pbDeliver | sm,m _;
deliver-pending (sm);
else if(snm > delivered[sm]+1) then
pending := pending ∪ { [Data, sm, m, snm] };
upon event (Timeout | s, sn ) do
forall seqnb ∈ [delivered[s] + 1, sn ] do
if exists [Data, s, x, sn] ∈ pending
delivered[s] := seqnb;
pending := pending \ {[Data, s, x, snx]};
trigger (pbDeliver | s, x );
end-if
else
{Msg is Lost}
end Algo
There are certain places where we changed the algorithm to increase the probability of the algorithm to broadcast messages to every node, and these are as follows
a) There is a problem in “unDeliver” Event, we start and trigger our timer
it should start timer for the Current node, not for the missed node as depicted in algorithm.
b) There is a new timer even in our proposed algorithm, that will take care of all missed messages from the last received sequence number up till the current one.
c) In “flp2pDeliver”, we should only add those sequence numbers to our pending list, which are greater than Delivered[Sn]+1, not all.
As our “Lazy Probabilistic Broadcast (LPB)” uses Unreliable broadcast abstraction to transmit messages to the nearby nodes (Process) in the topology, so the successful transmission is based on the structure of topology. Furthermore, LPB uses fair-loss-point-to-point links, so it also effects the transmission of messages.
As the unreliable broadcast algorithm we use for LPB just broadcast a message to all nodes in the network regardless of either a message is successfully reached to all nodes in the network or not, so it is required for the successful transmission that the topology should be fully connected, otherwise even if there is no Link Loss, messages will not arrive to all nodes in the network, because there may be a case that some nodes are not directly connected with the sender or broadcaster.
Proposed Improvements
One way of implementing this algorithm just like “Eager Reliable Broadcast”, so that every node who will deliver a message will broadcast it to other nodes connected to it, so we may assume that the flp2pDeliver Event will also broadcast the message to all other nodes directly connected to it. This solution is just like the “Flooding Algorithm” where
- Each node acts as both a transmitter and a receiver.
- Each node tries to forward every message to every one of its neighbors except the source node.
[Ref: Flooding Algorithm]
There are certain problems with this technique, and the most critical is the wastages of network resources and message redundancy, so one step ahead could be to use the improved version of Flooding Algorithm that is “Selective Flooding Algorithm” where messages are forwarded to most likely same direction as the recipient.
Note: I have seen somewhere during finding solution for reliable broadcasting that, “Spanning tree” is a solution for successfully transmit messages over node, and I guess it would also work fine in our case if we use this in our LPB approach. [Advice comment]
Usman Afzal 