Knowledge-based algorithm for multi-agent transmission protocol
To establish a team in a communicating multi-agent environment, a certain degree of general knowledge has to be obtained through dialogue. For this, we need an extension of the knowledge-based TCP to the multi-agent domain. Van Baars & Verbrugge (2006) derived a knowledge-based algorithm for a transmission protocol from one agent to a group of agents. They showed that it is correct for communication media where deletion and reordering errors may occur. Furthermore, they showed that their algorithm establishes very precise levels of knowledge within the group of agents using the one-on-group protocol.
We will provide a short description of the inner workings of this algorithm (for a simulation, see figure 2). Packages are presented in the following form (based on TCP package form):
K_source(destination,-,group,position,-,data)
Explanation:
- source
- source port where this package is sent from [S,Ri];
- K_source
- 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.
Because of the group information stored in the package, as soon as a receiver Ri receives a package from sender S containing a fact fj with group G, it knows fj (in other words: KRi fj), and it knows that all members of group G know fj (KRi RG). The sender of fact fj has to wait with sending a new package until it has received acknowledgements about the package containing this fact from all the receivers. Now S knows that all receivers know that fj (in formula: KS EG fj).
The receivers know that S works this way. Therefore, when a receiver Ri receives a package with the next fact fj+1, it knows that all other receivers know that fj (KRi KS EG fj). This way, two kinds of general knowledge are built (Van Baars & Verbrugge, 2006):
- The depth of knowledge by the members of group G is equal to the amount of consecutive facts sent after this fact.
- The depth of knowledge within the group about the members of the group is equal to the depth of knowledge within the group about the first fact sent by the sender.
A simulation of a simplified version of the knowledge-based algorithm for multi-agent communication (Van Baars & Verbrugge, 2006) can be found here.
It is important to realize that this algorithm still solves only a kind of sequence transmission problem, where a tape is sent to multiple agents. As can be seen in the abovementioned simulation, each agents receives the tape in the correct order (safety) and each agent eventually receives the entire tape (liveness).
