Algorithm as in LOFT06 article.
This version of the one-on-group communication algorithm is the algorithm from the extended abstract as presented at the "7th Conference on Logic and the Foundations of Game and Decision Theory (LOFT-06)". The form of the packages used in this algorithm have the following form:
Ksource(destination,-,group,position,-,data)
The fields with "-" are the checksum and window_size fields which deal with transmission errors and congestion control. Because they are not of interest for the knowlegde-based part of the algorithm they are left out in this summarized version of the protocol. An explanation of the fields that are used in this version of the algorithm.
| source | source port where this package is sent from [S,Ri]; |
| Ksource | the source who sends this package knows this package; |
| destination | destination port of package [S,Ri]; |
| group | group receivers to which the message is sent [RG, - ]("-" means that the sender communicates only to the destination (one-on-one communication)) |
| position | position of the data from the input tape; |
| data | data that has to be transmitted. |
Sender (incoming packages)
1 for (i = 1 to n)
{For all agents who sender is sending to, ... }
2 ack_Ri = 0
{... initialize the acknowledgement number.}
3 end
{ack_Ri's initialized}
4 while true do
{Get ready for receiving acknowledgements from the receivers, ... [12]}
5 when received KRi(S,-,-,seq,-,-) do
{You have received a package. Prepare for processing, ... [11]}
6 if (seq = ack_Ri+1) do
{If this acknowledgement from Ri is equal to the next ack_Ri, ... [10]}
7 ack_Ri = seq
{... this is the new current acknowledgement from Ri, ...}
8 store KSKRi(-.-,-,seq,-,-)
{... store the fact that you know that Ri knows it.}
9 ack_RG = min(ack_Ri (for i = 1 to n)
{The highest acknowledgement by the group is equal to the lowest ack_Ri.}
10 end
{[6] ... acknowledgement from Ri, and highest group updated.}
11 end
{[5] ... finished processing of incoming package.}
12 end
{... [4].}
Sender (outgoing packages)
1 seq = 0
{Reading of a tape starts at position 0.}
2 while true do
{Start reading and sending an infinite tape, ... [13]}
3 read(seq,alpha)
{... read the value from the tape, ...}
4 store KS(-,-,-,seq,-,alpha)
{... and store this information in your knowledge base.}
5 while (ack_RG ≠ seq) do
{While not al receivers have acknowledged the package with sequence seq ...[11]}
6 for (i = 1 to n) do
{For all receiving agents, ...}
7 if not KSKRi(-,-,-,seq,-,-) do
{... check if package `seq' has been acknowledged yet by Ri, ...}
8 send KS(Ri,-,RG,seq,-,alpha)
{... (re)send the package to Ri.}
9 end
{A package that was unacknowledged by Ri, has been (re)sent.}
10 end
{A package has been (re)sent to all agents that didn't acknowledge it.}
11 end
{[5] ... all agents Ri have acknowledged the package with sequence number seq.}
12 seq = seq +1
{Move the sequence number to the next position.}
13 end
{... [2].}
Receiver (incoming packages)
1 while true do
{Get ready for receiving an infinite tape, ... [5]}
2 when received KS(Ri,-,RG,seq,-,alpha) do
{You have received a package (from S). Prepare for processing, ... [4]}
3 store KRiKS(-,-,RG,seq,-,alpha)
{Store the received package.}
4 end
{[2] ... finished processing incoming package.}
5 end
{... [1].}
Receiver (outgoing packages)
1 when KRiKS(-,-,-,0,-,-)
{Wait until the first message is received.}
2 seq = 0
{Initiate the sequence at 0.}
3 while true do
{Get ready to acknowledge incoming packages, ... [8]}
4 while not KRiKS(-,-,-,seq+1,-,-) do
{Still not received package with sequence number 'seq+1', ...}
5 send KRi(S,-,-,seq,-,-)
{... (re)send acknowledgement.}
6 end
{You've received message seq+1.}
7 seq = seq +1
{You now the sequence number of the next message. Increment seq.}
8 end
{... [3].}
