0
$\begingroup$

We designed in the lecture of Distributed algorithm an algorithm to emulate a FIFO network as far as an asynchronous network isn't unavoidably FIFO.

Yet I have some difficultes to understand the condition of sending messages. Here is the algorithm:

Facteur_i

Begin
    While(True)
        Wait (buffer_i.test(T,∀k, connaissance_i[k,i]≥T[k,i]);
        Buffer_i.extract(`<j,c,m`>);
        connaissance_i=Max(connaissance_i,c);
        // max by element
        connaissance_i[j,i]++;
        deliver_from(j,m);
    End While
End

I don't understand these two lines:

Wait (buffer_i.test(T,∀k, connaissance_i[k,i]≥T[k,i]);
Buffer_i.extract(`<j,c,m`>);

Here is the description of the algorithm

Every site maintains an array $connaissance_i[j,k]$ the number of messages emited by $j$ to $k$ which arrive before a message emited by $i$. The value of the array go along every message sent. When receiving a message $m$, service of site $i$ determines if it has received every message that precedes causally $m$ comparing component by component the column of his own array with the one of message $m$. If this is the case, it delivers it and update his array. taking the maximum of both array (which is the equivalent of fusionning lists). Taking into account this message.

The other functions are

  • emit_to(j,m)

  • on_reception_from(j,(c,m))

primitives are

  • emit_to(j,m)

  • deliver_from(j,m)

Can you help me understand the condition of sending a message on distributed systems emulating a FIFO network?

I can provide more details if needed!

$\endgroup$
  • $\begingroup$ I don't understand what you're asking. Which condition? $\endgroup$ – Raphael Oct 24 '16 at 15:05
  • $\begingroup$ @Raphael I made it clearer writing in bold the condition : I don't understand these two lines: Wait (buffer_i.test(T,∀k, connaissance_i[k,i]≥T[k,i]); Buffer_i.extract(<j,c,m>); $\endgroup$ – ThePassenger Oct 24 '16 at 17:32
  • $\begingroup$ Apparently we have similar, circular problems. $\endgroup$ – Raphael Oct 24 '16 at 22:40

Your Answer

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

Browse other questions tagged or ask your own question.