First of all, the agents are represented by the breed type objects (as we
saw in the previous paragraph, those are of the turtles type).
In figure 1 is presented the way the agents are defined together with the
global data structures proprietary to the agents.
breeds [agents] globals [variables that simulate the memory shared by all the agents] agent-own [message-queue current-view nogoods messages-received_ok messages-received_nogood] ;message-queue contains the received messages. ;current-view is a list indexed on the agent’s number, of the form [v0 v1 v2...], ;vi = -1 if we don’t know the value o that agent. ;nogoods is the list of inconsistent positions [0 1 1 0 ...] where 0 is a good position and 1 is inconsistent. ;messages-received_ok and messages-received_nogood are variables that count the number of ok and ;nogood messages received by an agent.
Figure 1. Agents’ definition in the case of the asynchronous search techniques
The initialization of the agents supposes building the agents and initialization of the necessary data structures for the agents' operation. For initialization there is proposed an initialization procedure for each agent, procedure presented in figure 2. Typically the num-agents required for the running of the asynchronous search technique are built and the most important data structures are initialized.
to setup-agents // the agents defined with the breeds [agents] are used
; the num-agents agents are created and are initialized
create-custom-agents num-agents [
set messages-received_ok 0
set messages-received_nogood 0
set current-view get-list num-agents -1
set nogoods get-list num-agents 0
set message-queue []
…
]
end
Figure 2. The initialization procedure for each agent
1.2 Representation and manipulation of messages.
Any asynchronous search technique is based on the use by the agents of some messages for communicating various information needed for obtaining the solution. The agents’ communication is done according to the communication model introduced when we defined DCSP. The manipulation of the messages supposes first of all message representation. This thing can be achieved in Netlogo by using some indexed lists. To represent complex messages that contain many information, Netlogo allows the use of lists of lists (the list’s elements are also lists). The way of representation of the main messages encountered at the asynchronous search techniques is presented as follows:
• set message (list "ok" agent value agent_costs) – messages of the ok or info type; • set message (list "nogood" agent current-view agent_costs) - messages of the nogood or back type; • set message (list "addl" agent1 agent2 agent_costs) • set message (list "removel" agent1 agent2 agent_costs )
The communication model existing in the DCSP frame supposes first of all the existence of some channels of communication of the FIFO type that can store the messages received by each agent. The simulation of the message queues for each agent can be done using Netlogo lists, for whom we define treatment routines corresponding to the FIFO principles. These data structures are defined in the same time with the definition of the agents. In the proposed implementations in this article that structure will be called message-queue. That structure proprietary to each agent will contain all the messages of the ok and nogood type received by that agent (or any other type of message). These queue type data structures that have a very important role in functioning of the asynchronous search techniques have to respect the FIFO principles.
The manipulation of these channels can be managed by a central agent (which in NetLogo is called observer) or by the agents itself. For that we propose the building of a procedure called update for global manipulation of the message channels. It will have a role also in detecting the termination of the asynchronous search techniques execution. That update procedure is some kind of a “main program”, a command center for agents. In such a procedure, that needs to run continuously (until emptying the message queues) is verified for each agent the message queue (to detect a break in message transmitting). Also, the procedure should allow the operation with messages that are transmitted by the agents. That procedure needs to call for each agent another procedure which will treat each message according to it’s type. That procedure will be called handle-message, and will be used to handle messages specific to each asynchronous search technique. In figures 3 and 4 are presented the two main procedures for handling and treating messages, update and handle-message. The two procedures are the most important from the point of view of their messages handling way asynchronous or synchronous (way of work that defines the asynchronous techniques).
to update
set no-more-messages true
ask agents [
if (not empty? message-queue)[
set no-more-messages false]
]
;if all queues are empty, there are no more messages, the algorithm can be stopped
if (no-more-messages) [stop]
;the procedure for handling messages from the message queues is called, for each agent. ask agents [handle-message] ask agents [ create-temporary-plot-pen "q" + who plot messages-received_nogood …. ] ;graphical representations can be made after various parameters such as the number of messages, etc end
Figure 3. The NetLogo update-1 procedure
In the update procedure from figure 3, the call "ask agents ..." can be noticed, which allows the execution of the computations for each agent, but with a synchronization after each run of the agents. The variant for the one above is based on the use of the observer in handling the message channels. That behavior of the ask command allows us to build a synchronous distributed system.
;the message from the queue is handled and it’s type is identified (ok or nogood, addl or removel) calling the handling procedure.
to handle-message
locals [msg … ]
if (empty? message-queue) [stop]
set msg retrieve-message
if (first msg = "ok")
[
set messages-received_ok messages-received_ok + 1
procedure_ok msg
;it’s called the procedure of handling the messages of the ok type
]
if (first msg = "nogood")
[
set messages-received_nogood messages-received_nogood + 1
procedure_nogood msg
; it’s called the procedure of handling the messages of the nogood type
]
if (first msg = "addl")
[
procedure_addlink msg
; it’s called the procedure for adding new links
]
…
end
Figure 4. Message handling procedure
In figure 4, where is presented the procedure for message handling, it can be observed the fact that each agent extracts a message at a time from the message queue, identifies the message type and calls the procedure for handling that type of message. The message handling procedures for a particular type of message can be implemented according to the respective algorithm.
Another analyzed aspect is that of the agets’ ordering. There are many techniques for asynchronous searching, such as those from the ABT family, in which the ordering of the agents is static. Thus, transmiting the ok messages (that inform on the apparition of a new value) is done through certain agents. There are asynchronous techniques that require or can use a certain dynamic order for the agents. In that category we have AWCS and an ABT variant with dynamic ordering.
A first problem is determined by the NetLogo environment features. The agents commands are performed using, mainly, the ask command. Each agent, using the ask command, handles the messages from it’s own message queue. That command is performed for the objects of the turtles or breed type. According with the NetLogo rules, the ask command is planned to execute in increasing order the agents, according with the order gien by the ordering number. The order of execution is chosen deterministic and in a reproducible way. Those features existent in NetLogo are appropriate for the case of the static, lexicographic ordering.
In the case of the techniques that use dynamical ordering, the solution consists in building lists that contain the agents with whom communication is needed. By exampe, in AWCS each agent’s neighbors can be kept in a list, messages being transmitted to those agents in the indices order. Such a list can be ordered after criteria given by various heuristics, such as to respect the specific of a certain technique.
1.3 Termination detection for the asynchronous search techniques
For most of the asynchronous search techniques, the solution is generally
detected only after a break period in sending messages (this means there is
no message being transmitted, state called quiescence). More CSP distributed
techniques detect silence in the transmission of messages by using the general
techniques in [2]. These algorithms are remarkable through the fact that ending
verification should be initiated by the agents that suspect the occurrence
of a break in the sending of messages. Still it needs to be specified the
fact that there are other techniques that could detect as fast as possible
a break in sending messages.
There are two situations that should be analyzed: the situation in which there
is a solution and that in which there’s no solution. To finish building
the solution in NetLogo, is based on detecting a break in message transmition.
That situation can be resolved through verifying the message queues, queues
that nedd to be empty.
For the detection of the asynchronous techniques’ termination, implemented on the NetLogo model that was presented, we propose two original methods for the detection of the execution’s termination for the asynchronous search techniques. The two methods are based on different solutions for detecting a break in message transmission. Those two methods could be applied for any implementation of an asynchronous technique, that uses the implementation model presented. Applying the two methods of detection f termination for the execution process leads to two multi-agent systems that colud be used to implement, evaluate and analyze the techniques of asynchronous search. Implementation examples of the asynchronous techniques that use the two methods can be found on the link NetLogo Models.
[2]. K. M. Chandy, L. Lamport. \emph{Distributed snapshots: Determining global states of distributed systems}, ACM Transactions on Computer Systems, 3(1), 63-75, 1985.
1.3.1. Termination detection for the process of execution by the central “Observer” agent
The first solution of termination detection is based on some of the facilities of the NetLogo environment: the ask command that allows the execution of the computations for each agent and the existence of the cental observer agent. Handling the communication channels will be realized by this central agent. For that the building of an update procedure is proposed for global handling the message channels. In such a procedure, that must run continuously (until the message queues are emptied) the observer agent verifies if it’s detected a break in message transmission. Also, the procedure must allow operating with messages that are transmitted by the agents. That procedure will call, for each agent the procedure for effective handling for the messages. That procedure was named handle-message and will be called from within the update procedure using ask. Those two elements (the call of the local procedures for message handling with ask and detection by the observer) will lead to a variant of implementation in which the synchronizing of the agents’ execution is done.
The first method of detection of termination has in it’s center the system agent „observer”, to whom is given that task of verifying a break in message transmission. That thing is done through asociating the update procedure to the NetLogo „observer”. This observer will call the ask command, to manipulate the messages received by an agent, because NetLogo doesn’t allow routines attached to the agents to be run only by the central agent. The “observer” can be regarded as a system agent that initiates the termination procedure of the algorithm.
The observer uses a global variabile (in figure 9 named no-more-messages) used for determining if the message queues are empty, which is a signal that a break has occurred in the message transmission. We can remark the fact that if there are messages in at least a message queue, is called the procedure for message handling, using the NetLogo instrument ask. That first method leads to a synchronization of the agents’ execution, caused by the behaviour of the “ask” command. That command waits that each agent finishes to perform it’s commands. As a consequence, it can be obtained a system with synchronization.
1.3.2. Detection of termination for the execution process by each DCSP agent
The second method allows us to obtain implementations with a completely asynchronous behaviour for the agents. That method is much more general allowing the evaluation of the asynchronous techniques in conditions of functioning similar to those from the practical applications, for whom doesn’t exist a synchronization of the agents’ execution. In that case, each agent executes asynchronously and concurrently it’s computations, having no synchronization. That situation is solved through introducing of indicators, that each moment retain the status of the communication channels for each agent (true if there are no messages and false, otherwise). If, at a given time, all the indicators are true, we can stop the execution of the techniques. We must remark the fact that those indicators change their value during execution, depending of the existence or inexistence of messages in the message queues.
The second method of detection starts from renouncing the role of the “observer” to detect the apparition of a break in message transmission and execution of the update procedure by each agent. The detection will be made by the first agent (of the turtle-breed type) that detects it’s apparition. The solution (from NetLogo) is given by the use of some buttons of the type “turtle forever-buttons”, buttons that aren’t attached to the observer. Practicaly, the “ask” command wouldn’t be used to execute the message handling routines. Those will be executed for each agent (turtle) through a button (attached to turtle) of the „forever-button” type (as you can see in figure 5).
To each agent will be attached an indicator that will detect its local status. Detecting of the algorithm’s termination is done using these indicators that will hold at any time the status of the communication channels for each agent (true, if there is no message in the message queue and false otherwise). If, at a given time, all the indicators are true, we can stop the algorithm. This thing is done by the first turtle agent that detects that state. In figure 10 is presented the code of the update procedure.
to update
handle-message
; detecting of execution termination is done by each turtle
; the first that notices that all queues are empty will stop the algorithm
if (sum (values-from vertices [gt]) = num-vertices)
[
ifelse Solution
[WriteSolution]
[WriteNoSolution]
stop
]
end
Figure 5. The update – 2 procedure
Using the second method of detection of termination requires an adaptation of the message manipulation routine, obtaining the routine from figure 6.
to handle-message
if not empty? message-queue
[
set msg retrieve-message
set gt 0
if (first msg = "ok?")[
handle-ok-message item 1 msg]
if (first msg = "nogood")[
handle-nogood-message msg]
]
if (empty? message-queue)
[
set gt 1
stop ]
end
Figure 6. The handle-message – 2 procedure
We can observe the fact that if the message queue of an agent isn’t empty, the gt indicator becomes 0 (false), otherwise it becomes 1. That thing is necessary because the agents send messages asynchronously and concurrently to other agents such as in different moments the message queues pass through different states.
That second solution allows the building of another type of evaluation system in NetLogo, with agents, without synchronization for the agents execution. That system allows studying the agents’ behaviour in conditions closer to the real ones.
As concerning the case in which there’s no solution, using a global variable “solution” is preffered, that will keep the state of the problem solving. First of all, the techniques that use a static ordering, a lexicographic ordering and some of the ones that use a dynamical ordering, the detection of inexistence of a solution (that is typically recognized through the apparition of an empty nogood) is founded if the agent with the „0” rank detects a nogood. In fact, such an agent doesn’t have where to send that nogood (which is in fact empty). As regarding some techniques that use a dynamical ordering for agents, such as the AWCS technique, detecting that the solution is inexistent is done if there were recorded all the possible nogoods or was detected an empty signal. The occurrence of any of there situations will lead to setting the “Solution” variable on false.
2. The architectures of the two proposed implementation and evaluation systems.
Starting from the modeling of the process of agents’ execution proposed in the previous paragraph, applying a method for the detection of termination of this process we can obtain two multi-agent systems that can be used to implement and evaluate the techniques of asynchronous search. The architectures of the two distributed systems that can be used for the asynchronous search techniques, are presented in figures 7 and 8.
The two systems are characterized by some common elements. First of all the agents simulation is made in the same way, each agent being simulated through the use of breed type objects. Second, we can attach a general message treating routine to the agents (in figures 7 and 8 handle-message). Third, the message treating procedures (which, usually differentiate each technique) are implemented in the same way for the two systems.
The main difference between the two systems consists in the detrection of termination of each implemented technique. The first multi-agent system uses the system agent called observator, in the second one the agents are simulated through breed type objects.
2.1.Architecture of a multi-agent system with agents’ execution synchronization.
The first multi-agent system of implementation and evaluation is obtained by applying the first method of detection of termination for the asynchronous search techniques. This system will be called implementation and evaluation system with sincronization-SIES. The main idea is to use the system observer agent for identifying the break in message transmission. That thing is done through attaching the update routine to a button attached to the observer.
The second element that differentiates this system is that of using the ask command for executing the handle-message routine of each agent (in the update routine). That solution leads to the synchronization of the agents execution. In figure 7 is presented this multi-agent system’s architecture, system that will be used in next chapters for implementing and evaluating more variants of asynchronous search techniques.
Figure 7. Arhitecture of a multi-agent system with execution synchronization - SIES
2.2. Architecture of a multi-agent system with asynchronous operating of the agents-SIEAS
The second multi-agent system is obtained applying the second method of termination detection for the agents’ execution at the model of implementation and evaluation proposed previously. That system will be called implementation and evaluation system with asynchronous operation of the agents-SIEAS. The multi-agent system is remarked by renouncing the observer and attaching the update routine to each agent of the breed type. That way the execution of the handlle-message routine isn’t done by the ask command, that being executed for each agent (turtle) by the turtle type button with „forever-button” feature setted. Giving up the ask command has the effect of asynchronous run of the agents, each agent processing its messages without waiting for a synchronization with the other agents.
Figure 8. Arhitecture of a multi-agent system with asynchronous agents operation-SIEAS
Usually, most of the simulators run more threads on the same computing system, a thread for each agent. The application runs in more cycles, a cycle consisting in that period necessary for each agent to receive messages, to execute the local computations and to transmit messages. Practically, after each cycle takes place a synchronization of the agents, expecting that each one to finish its cycle. Such a behaviour is defined as a distributed synchronous system.
That thing can be found also in NetLogo. A call of the main procedure, called in this study update, corresponds to the notion of cycle. In order that that routine to run until the determination of a solution or its inexistence, it is attached to a Observer type button, with „forever-button” feature set. In principle, it requires through the ask command, the manipulation of the messages from the message queues. Each agent, concurrenty and asynchronously, extracts, sends messages and executes its local computations, but the ask command, makes at the end a synchronization. That mecanism allows the definition of a behaviour of a distributed synchronous system and is obtained for the first multi-agent system.
That system can be transformed into a model that works as asynchronous as possible. The solution is given by the use of the second solution for detecting the termination of the algorithm and the use of some buttons attached to the objects of the turtle type, buttons that aren’t any more attached to the observer. In the mean time we renounce the use of the ask command for executing the routine of message handling, that being executed for each agent (turtle) by the button of the turtle „forever-button” type. These elements lead to the architecture presented in figure 8.