arXiv:cs/0503028v2 [cs.LO] 24 Mar 2005

Under consideration for publication in Theory and Practice of Logic Programming

1

Stabilization of Cooperative Information Agents
in Unpredictable Environment: A Logic
Programming Approach
PHAN MINH DUNG, DO DUC HANH, PHAN MINH THANG
Computer Science and Information Management Department
Asian Institute of Technology
Email: {dung,hanh,thangphm}@cs.ait.ac.th
submitted 1 January 2003; revised 1 January 2003; accepted 1 January 2003

Abstract
An information agent is viewed as a deductive database consisting of 3 parts:
• an observation database containing the facts the agent has observed or sensed from
its surrounding environment.
• an input database containing the information the agent has obtained from other agents
• an intensional database which is a set of rules for computing derived information from
the information stored in the observation and input databases.
Stabilization of a system of information agents represents a capability of the agents to
eventually get correct information about their surrounding despite unpredictable environment changes and the incapability of many agents to sense such changes causing them
to have temporary incorrect information. We argue that the stabilization of a system of
cooperative information agents could be understood as the convergence of the behavior
of the whole system toward the behavior of a “superagent”, who has the sensing and
computing capabilities of all agents combined. We show that unfortunately, stabilization
is not guaranteed in general, even if the agents are fully cooperative and do not hide any
information from each other. We give sufficient conditions for stabilization. We discuss the
consequences of our results.
KEYWORDS: Stabilization, Cooperative Information Agents, Logic Programming

1 Introduction
To operate effectively in a dynamic and unpredictable environment, agents need
correct information about the environment. Often only part of this environment
could be sensed by the agent herself. As the agent may need information about
other part of the environment that she could not sense, she needs to cooperate
with other agents to get such information. There are many such systems of cooperative information agents operating in the Internet today. A prominent example of
such system is the system of routers that cooperate to deliver messages from one
place to another in the Internet. One of the key characteristics of these systems is
their resilience in the face of unpredictable changes in their environment and the

2

P. M. Dung, D. D. Hanh, and P. M. Thang

incapability of many agents to sense such changes causing them to have temporary
incorrect information. This is possible because agents in such systems cooperate by
exchanging tentative partial results to eventually converge on correct and consistent
global view of the environment. Together they constitute a stabilizing system that
allows the individual agents to eventually get a correct view of their surrounding.
Agent communications could be classified into push-based communications and
pull-based communications. In the push-based communication, agents periodically
send information to specific recipients. Push-based communications are used widely
in routing system, network protocols, emails, videoconferencing calls, etc. A key
goal of these systems is to guarantee that the agents have a correct view of their
surrounding. On the other hand, in the pull-based communication, agents have
to send a request for information to other agents and wait for a reply. Until
now pull-based communications are the dominant mode of communication in research in multiagent systems, e.g. (Shoham 1993), (Satoh and Yamamoto 2002),
(Ciampolini et al. 2003), (Kowalski and Sadri 1999), (Wooldridge 1997), (Wooldridge and Jennings 1995).
In this paper, we consider multiagent systems where agent communications are
based on push–technologies. A prominent example of a push-based multiagent system is the internet routing system.
This paper studies the problem of stabilization of systems of cooperative information agents where an information agent is viewed as a deductive database which
consists of 3 parts:
• an observation database containing the facts the agent has observed or sensed
from its surrounding environment.
• an input database containing the information the agent was told by other
agents
• an intensional database which is a set of rules for computing derived information from the information stored in the observation and input databases.
It turns out that in general, it is not possible to ensure that the agents will
eventually have the correct information about the environment even if they honestly
exchange information and do not hide any information that is needed by others and
every change in the environment is immediately sensed by some of the agents. We
also introduce sufficient conditions for stabilization.
The stabilization of distributed protocols has been studied extensively in the literature ((Dijkstra 1974),(Flatebo et al. 1994),(Schneider 1993)) where agents are
defined operationally as automata. Dijkstra (1974) defined a system as stabilizing
if it is guaranteed to reach a legitimate state after a finite number of steps regardless of the initial state. The definition of what constitutes a legitimate state is left
to individual algorithms. Thanks to the introduction of an explicit notion of environment, we could characterize a legitimate state as a state in which the agents
have correct information about their environment. In this sense, we could say that
our agents are a new form of situated agents ((Rosenschein and Kaelbling 1995),
(Brooks 1991), (Brooks 1986)) that may sometimes act on wrong information but
nonetheless will be eventually situated after getting correct information about their

Stabilization of Cooperative Information Agents

3

surrounding. Further in our approach, agents are defined as logic programs, and
hence it is possible for us to get general results about what kind of algorithms
could be implemented in stabilizing multiagent systems in many applications. To
the best of our knowledge, we believe that our work is the first work on stabilization
of multiagent systems.
The rest of this paper is organized as follows. Basic notations and definitions used
in this paper are briefly introduced in section 2. We give an illustrating example
and formalize the problem in section 3. Related works and conclusions are given in
section 4. Proofs of theorems are given in Appendices.
2 Preliminaries: Logic Programs and Stable Models
In this section we briefly introduce the basic notations and definitions that are
needed in this paper.
We assume the existence of a Herbrand base HB.
A logic program is a set of ground clauses of the form:
H ← L1 , . . . , Lm
where H is an atom from HB, and L1 , . . . , Lm are literals (i.e., atoms or negations
of an atoms) over HB, m ≥ 0. H is called the head, and L1 , . . . , Lm the body of
the clause.
Given a set of clauses S, the set of the heads of clauses in S is denoted by head(S).
Note that clauses with variables are considered as a shorthand for the set of all
their ground instantiations. Often the variables appearing in a non-ground clause
have types that are clear from the context. In such cases these variables are instantiated by ground terms of corresponding types.
For each atom a, the definition of a is the set of all clauses whose head is a.
A logic program is bounded if the definition of every atom is finite.
Let P be an arbitrary logic program. For any set S ⊆ HB, let P S be a program
obtained from P by deleting
1. each rule that has a negative literal ¬B in its body with B ∈ S, and
2. all negative literals in the bodies of the remaining rules
S is a stable model ((Gelfond and Lifschitz 1988)) of P if S is the least model of
P S.
The atom dependency graph of a logic program P is a graph, whose nodes are
atoms in HB and there is an edge from a to b in the graph iff there is a clause in
P whose head is a and whose body contains b or ¬b. Note that in the literature
(Apt et al. 1988), the direction of the link is from the atom in the body to the head
of a clause. We reverse the direction of the link for the ease of definition of acyclicity
using the atom dependency graph.
An atom b is said to be relevant to an atom a if there is a path from a to b in
the atom dependency graph.
A logic program P is acyclic iff there is no infinite path in its atom dependency
graph. It is well known that

4

P. M. Dung, D. D. Hanh, and P. M. Thang

Lemma 2.1 ((Gelfond and Lifschitz 1988))
Each acyclic logic program has exactly one stable model.

3 Examples and Problem Formalization
Routing is one of the most important problems for internetworking. Inspired by
RIP (Huitema 2000), one of the most well-known internet routing protocols, we
will develop in this section, as an example, a multiagent system for solving the
network routing problem to motivate our work.
Example 3.1
Consider a network in Fig. 1. For simplicity we assume that all links have the same
cost, say 1.
A❜1

A❜2

❜

❜

A4

A5

A❜3

Fig. 1. A network example
The problem for each agent is to find the shortest paths from her node to other
nodes. The environment information an agent can sense is the availability of links
connecting to her node. The agents use an algorithm known as “distance vector
algorithm” ((Bellman 1957), (Ford and Fulkerson 1962)) to find the shortest paths
from their nodes to other nodes. If the destination is directly reachable by a link, the
cost is 1. If the destination is not directly reachable, an agent needs information
from its neighbors about their shortest paths to the destination. The agent will
select the route to the destination through a neighbor who offers a shortest path to
the destination among the agent’s neighbors. Thus at any point of time, each agent
needs three kinds of information:
• The information about the environment, that the agent can acquire with her
sensing capability. In our example, agent A1 could sense whether the links
connecting her and her neighbors A2 , A4 are available.
• The algorithm the agent needs to solve her problem. In our example the
algorithm for agent A1 is represented by the following clauses: 1
1

Contrary to the convention in Prolog, in this paper we use lower–case letters for variables and
upper–case letters for constants.

Stabilization of Cooperative Information Agents

5

sp(A1 , A1 , 0)
←
sp(A1 , y, d)
← spt(A1 , y, x, d)
spt(A1 , y, x, d + 1) ← link(A1 , x), sp(x, y, d),
not spl(A1 , y, d + 1)
spl(A1 , A1 , d + 1) ←
spl(A1 , y, d + 1)
← link(A1 , x), sp(x, y, d′ ), d′ < d
where
link(Ai , Aj ) is true iff there a link from Ai to Aj in the network and the link is
intact. Links are undirected, i.e. we identify link(Ai , Aj ) and link(Aj , Ai ).
sp(A1 , y, d) is true iff a shortest path from A1 to y has length d
spt(A1 , y, x, d) is true iff the length of shortest paths from A1 to y is d and
there is a shortest path from A1 to y that goes through x as the next node
after A1
spl(A1 , y, d) is true iff there is a path from A1 to y whose length is less than
d.
• The information the agent needs from other agents. For agent A1 to calculate
the shortest paths from her node to say A3 , she needs the information about
the length of the shortest paths from her neighbors A2 , and A4 to A3 , that
means she needs to know the values d, d′ such that sp(A2 , A3 , d), sp(A4 , A3 , d′ )
hold.
3.1 Problem Formalization
The agents are situated in the environment. They may have different accessibility
to the environment depending on their sensing capabilities. The environment is
represented by a set of (ground) environment atoms, whose truth values could
change in an unpredictable way.
Definition 3.1
An agent is represented by a quad-tuple
A = (IDB, HBE, HIN, δ)
where
• IDB, the intensional database, is an acyclic logic program.
• HBE is the set of all (ground) environment atoms whose truth values the
agent could sense, i.e. a ∈ HBE iff A could discover instantly any change in
the truth value of a and update her extensional database accordingly.
• HIN is the set of all atoms called input atoms, whose truth values the agent
must obtain from other agents.
No atom in HIN ∪ HBE appears in the head of the clauses in IDB and
HIN ∩ HBE = ∅.
• δ is the initial state of the agent.

6

P. M. Dung, D. D. Hanh, and P. M. Thang

Definition 3.2
An agent state is a pair σ = (EDB, IN ) where
• EDB ⊆ HBE represents what the agent has sensed from the environment.
That means for each a ∈ HBE, a ∈ EDB iff a is true.
• IN ⊆ HIN , the input database of A, represents the set of information A has
obtained from other agents, i.e. a ∈ IN iff A was told that a is true.
Given a state σ = (EDB, IN ), the stable model of A = (IDB, HBE, HIN, δ) at
σ is defined as the stable model of IDB ∪ EDB ∪ IN . Note that δ and σ could be
different states.
Example 3.2 (Continuation of the network routing example)
Imagine that initially the agents have not sent each other any information and all
links are intact. In this situation, agent A1 is represented as follows:
• IDB1 contains the clauses shown in Example 3.1.
• HBE1 = {link(A1 , A2 ), link(A1 , A4 )}
• HIN1 consists of ground atoms of the form
sp(A2 , Y, D), sp(A4 , Y, D)
where Y ∈ {A2 , . . . , A5 } and D is a positive integer.
• The initial state δ1 = (EDB1,0 , IN1,0 ) where
EDB1,0 = {link(A1 , A2 ), link(A1 , A4 )}
IN1,0 = ∅
Definition 3.3
A cooperative multiagent system is a collection of n agents (A1 , . . . , An ), with Ai =
(IDBi ,HBEi , HINi , δi ) such that the following conditions are satisfied
• for each atom a, if a ∈ head(IDBi ) ∩ head(IDBj ) then a has the same
definition in IDBi and IDBj .
n
S
(head(IDBj ) ∪ HBEj )
• for each agent Ai , HINi ⊆
j=1
• No environment atom appears in the head of clauses in the intentional database
of any agent, i.e. for all i,j: HBEi ∩ head(IDBj ) = ∅.
For each agent Ai let HBi = head(IDBi ) ∪ HBEi ∪ HINi .
3.2 Agent Communication and Sensing
Let Ai = (IDBi , HBEi , HINi , δi ) for 1 ≤ i ≤ n. We say that Ai depends on Aj
if Ai needs input from Aj , i.e. HINi ∩ (head(IDBj ) ∪ HBEj ) 6= ∅. The dependency of Ai on Aj is defined to be the set D(i, j) = HINi ∩(head(IDBj )∪HBEj ).
As we have mentioned before, the mode of communication for our agents corresponds to the “push–technology”. Formally, it means that if Ai depends on Aj

Stabilization of Cooperative Information Agents

7

then Aj will periodically send Ai a set S = D(i, j) ∩ Mj where Mj is the stable model of Aj . When Ai obtains S, she knows that each atom a ∈ D(i, j) \ S
is false with respect to Mj . Therefore she will update her input database INi to
U pai,j (INi , S) as follows
U pai,j (INi , S) = (INi \ D(i, j)) ∪ S
Thus her state has changed from σi = (EDBi , INi ) to σi′ = (EDBi , U pai,j (INi , S))
accordingly.
An environment change is represented by a pair C = (T, F ) where T (resp. F )
contains the atoms whose truth values have changed from false (resp. true) to
true (resp. false). Therefore, given an environment change (T, F ), what Ai could
sense of this change, is captured by the pair (Ti , Fi ) where Ti = T ∩ HBEi and
Fi = F ∩ HBEi . Hence when a change C = (T, F ) occurs in the environment, agent
Ai will update her sensing database EDBi to U pei (EDBi , C) as follows:
U pei (EDBi , C) = (EDBi \ Fi ) ∪ Ti
The state of agent Ai has changed from σi = (EDBi , INi ) to σi′ = (U pei (EDBi , C),
INi ) accordingly.

3.3 Semantics of Multiagent Systems
Let
A = (A1 , . . . , An )
with
Ai = (IDBi , HBEi , HINi , δi )
be a multiagent system. (δ1 , . . . , δn ) is called the initial state of A.
A state of A is defined as
△ = (σ1 , . . . , σn )
such that σi is a state of agent Ai .
There are two types of transitions in a multiagent system. A environment transition happens when there is a change in the environment which is sensed by a set of
agents and causes these agents to update their extensional databases accordingly.
A communication transition happens when an agent sends information to another
agent and causes the later to update her input database accordingly.
For an environment change C = (T, F ), let SC be the set of agents which could
sense parts of C, i.e.
SC = {Ai | HBEi ∩ (T ∪ F ) 6= ∅}

8

P. M. Dung, D. D. Hanh, and P. M. Thang

Definition 3.4
Let △ = (σ1 , . . . , σn ), △′ = (σ1′ , . . . , σn′ ) be states of A with σi = (EDBi , INi ),
σi′ = (EDBi′ , INi′ ).
1. A environment transition
C

△−
→ △′
caused by an environment change C = (T, F ) is defined as follows
(a) for every agent Ak such that Ak 6∈ SC : σk = σk′ , and
(b) for each agent Ai ∈ SC :
• EDBi′ = U pei (EDBi , C),
• INi′ = INi .
2. A communication transition
j

i

△ −−→ △′
caused by agent Aj sending information to agent Ai , where Ai depends on
Aj , is defined as follows:
(a) For all k such that k 6= i: σk = σk′
(b) EDBi′ = EDBi and INi′ = U pai,j (INi , S) where S = D(i, j)∩Mj
and Mj is the stable model of Aj at σj .
j

C

i

We often simply write △ → △′ if there is a transition △ −
→ △′ or △ −−→ △′ .
Definition 3.5
A run of a multiagent system A is an infinite sequence
△0 → △1 → . . . → △m → . . .
such that
• △0 is the initial state of A and for all agents Ai , Aj such that Ai depends on
Aj the following condition is satisfied:
j

i

For each h, there is a k ≥ h such that △k −−→ △k+1
The above condition is introduced to capture the idea that agents periodically
send the needed information to other agents.
• There is a point h such that at every k ≥ h in the run, there is no more
environment change.

For a run R = △0 → △1 → . . . → △k → . . . where △k = (σ1,k , . . . , σn,k ) we
often refer to the stable model of Ai at state σi,k as the stable model of Ai at point
k and denote it by Mi,k .

Stabilization of Cooperative Information Agents

9

Example 3.3
Consider the following multiagent system
A = (A1 , A2 )
where
IDB1
HBE1
HIN1
EDB1,0
IN1,0

= {a ← b, c
f ← a}
= {c}
= {b}
= {c}
= ∅

IDB2
HBE2
HIN2
EDB2,0
IN2,0

= {b ← a, d
b ← e}
= {d, e}
= {a}
= {d, e}
= ∅

Consider the following run R, where the only environment change occurs at point
2 such that the truth value of e becomes false:
2

1

1

(∅,{e})

2

1

2

2

1

△0 −−−→ △1 −−−→ △2 −−−−→ △3 −−−→ △4 −−−→ △5 . . .
The states and stable models of A1 and A2 at points 0, 1, 2, 3, and 4 are as follows

k
0
1
2
3
4

EDB
{c}
{c}
{c}
{c}
{c}

IN
∅
{b}
{b}
{b}
{b}

A1
Stable Model
{c}
{a, b, c, f }
{a, b, c, f }
{a, b, c, f }
{a, b, c, f }

EDB
{d, e}
{d, e}
{d, e}
{d}
{d}

IN
∅
∅
{a}
{a}
{a}

A2
Stable Model
{b, d, e}
{b, d, e}
{a, b, d, e}
{a, b, d}
{a, b, d}

Example 3.4 (Continuation of example 3.2)
Consider the following run R of the multiagent system given in Example 3.2.
2

(∅,{link(A1 ,A2 )})

1

△0 −−−→ △1 −−−−−−−−−−−→ △2 → . . .
Initially, all links are intact and all inputs of agents are empty, i.e. INi,0 = ∅ for
i = 1, . . . , 5. At point 0 in the run, agent A2 sends to agent A1 information about
shortest paths from her to other agents. At point 1 in the run, the link between A1
and A2 is down.
The information (output) an agent needs to send to other agents consists of
shortest paths from her to other agents. Thus from the stable model of an agent
we are interested only in this output.
Let SPi,k be the set {sp(Ai , Y, D)|sp(Ai , Y, D) ∈ Mi,k } where Mi,k is the stable
model of Ai at point k. SPi,k denotes the output of Ai at point k. It is easy to see
j

i

that if there is a transition △k −−→ △k+1 , then Aj sends to Ai :
S = D(i, j) ∩ Mj,k = SPj,k

10

P. M. Dung, D. D. Hanh, and P. M. Thang

At point 0, A1 and A2 have the following states and outputs:
EDB1,0
IN1,0
SP1,0
EDB2,0
IN2,0
SP2,0

=
=
=
=
=
=

{link(A1 , A2 ), link(A1 , A4 )}
∅
{sp(A1 , A1 , 0)}
{link(A2 , A1 ), link(A2 , A3 ), link(A2 , A5 )}
∅
{sp(A2 , A2 , 0)}
2

1

A2 sends S to A1 in the transition △0 −−−→ △1 where
S = SP2,0 = {sp(A2 , A2 , 0)}
Thus
IN1,1 = U pa1,2 (IN1,0 , S) = U pa1,2 (∅, S) = S = {sp(A2 , A2 , 0)}
The environment change C = (∅, {link(A1 , A2 )}) at point 1 is sensed by A1 and
A2 . The states of A1 and A2 are changed as follows:
IN1,2
EDB1,2
IN2,2
EDB2,2

=
=
=
=
=
=

IN1,1
U pe1 (EDB1,1 , C) = (EDB1,1 \ {link(A1 , A2 )}) ∪ ∅
{link(A1 , A4 )}
IN2,1
U pe2 (EDB2,1 , C) = (EDB2,1 \ {link(A1 , A2 )}) ∪ ∅
{link(A2 , A3 ), link(A2 , A5 )}

The following tables show the states and outputs of A1 and A2 at points 0, 1,
and 2 respectively.

k
0
1
2

EDB
{link(A1 , A2 ), link(A1 , A4 )}
{link(A1 , A2 ), link(A1 , A4 )}
{link(A1 , A4 )}

k
0
1
2

A1
IN
∅
{sp(A2 , A2 , 0)}
{sp(A2 , A2 , 0)}

A2
EDB
{link(A2 , A1 ), link(A2 , A3 ), link(A2 , A5 )}
{link(A2 , A1 ), link(A2 , A3 ), link(A2 , A5 )}
{link(A2 , A3 ), link(A2 , A5 )}

SP
{sp(A1 , A1 , 0)}
{sp(A1 , A1 , 0), sp(A1 , A2 , 1)}
{sp(A1 , A1 , 0)}

IN
∅
∅
∅

SP
{sp(A2 , A2 , 0)}
{sp(A2 , A2 , 0)}
{sp(A2 , A2 , 0)}

3.4 Stabilization
Consider a superagent whose sensing capability and problem solving capability are
the combination of the sensing capabilities and problem solving capabilities of all
agents, i.e. this agent can sense any change in the environment and her intensional
database is the union of the intensional databases of all other agents. Formally, the

Stabilization of Cooperative Information Agents

11

superagent of a multiagent system
A = (A1 , . . . , An )
where
Ai = (IDBi , HBEi , HINi , δi ), δi = (EDBi , INi )
is represented by
PA = (IDBA , δ)
where
• IDBA = IDB1 ∪ · · · ∪ IDBn
• δ, the initial state of PA , is equal to EDB1 ∪ · · · ∪ EDBn
The superagent actually represents the multiagent system in the ideal case where
each agent has obtained the correct information for its input atoms.
Example 3.5 (Continuation of Example 3.3)
Consider the multiagent system in Example 3.3. At point 0, the superagent PA is
represented as follows:
• IDBA consists of the following clauses:
a ← b, c

f ←a

b ← a, d

b←e

• δ = {c, d, e}.
Example 3.6 (Continuation of Example 3.4)
Consider the multiagent system in Example 3.4. Initially, when all links between
nodes are intact, the superagent PA is represented as follows:
• IDBA consists of the following clauses:
sp(x, x, 0)
←
sp(x, y, d)
← spt(x, y, z, d)
spt(x, y, z, d + 1) ← link(x, z), sp(z, y, d),
not spl(x, y, d + 1)
spl(x, x, d + 1)
←
spl(x, y, d + 1)
← link(x, z), sp(z, y, d′), d′ < d
• The initial state
δ={

link(A1 , A2 ), link(A1 , A4 ), link(A2 , A3 ),
link(A2 , A5 ), link(A3 , A5 ), link(A4 , A5 )}

Note that the possible values of variables x, y, z are A1 , A2 , A3 , A4 , A5 .
Definition 3.6
Let A be a multiagent system.
The I/O graph of A denoted by GA is a graph obtained from the atom dependency graph of its superagent’s intensional database IDBA by removing all nodes
that are not relevant for any input atom in HIN1 ∪ · · · ∪ HINn .

12

P. M. Dung, D. D. Hanh, and P. M. Thang

A is IO-acyclic if there is no infinite path in its I/O graph GA .
A is bounded if IDBA is bounded.
A is IO-finite if its I/O graph is finite.

Example 3.7
The atom dependency graph of IDBA and the I/O-graph GA of the multiagent
system in Examples 3.3 and 3.5 is given in Fig. 2.

Atom dependency graph

f

I/O graph
a

c

b

d

e

Fig. 2. The atom dependency graph and I/O graph
It is obvious that the multiagent system in Examples 3.3 and 3.5 is bounded
but not IO-acyclic and the multiagent system in Examples 3.1, 3.2, 3.4 and 3.6 is
IO-acyclic and bounded.

Proposition 3.1
If a multiagent system A is IO-acyclic then IDBA is acyclic.

Proof
Suppose IDBA is not acyclic. There is an infinite path η in its atom dependency
graph starting from some atom a. There is some agent Ai such that a ∈ HBi .
Since IDBi is acyclic, every path in its atom dependency graph is finite. η must
go through some atom b ∈ INi to outside of Ai ’s atom dependency graph. Clearly
starting from b, all atoms in η are relevant to b. The infinite path of η starting from
b is a path in the I/O graph GA . Hence GA is not acyclic. Contradiction!

Stabilization of Cooperative Information Agents

13

Definition 3.7
Let R = △0 → . . . △k → . . . be a run and Mi,k be the stable model of Ai at point
k.
1. R is convergent for an atom a if either of the following conditions is satisfied.
• There is a point h such that at every point k ≥ h, for every agent Ai
with a ∈ HBi = head(IDBi ) ∪ HBEi ∪ HINi ,
a ∈ Mi,k
In this case we write Conv(R, a) = true
• There is a point h such that at every point k ≥ h, for every agent Ai
with a ∈ HBi ,
a 6∈ Mi,k
In this case we write Conv(R, a) = f alse
2. R is convergent if it is convergent for each atom.
3. R is strongly convergent if it is convergent and there is a point h such that
at every point k ≥ h, for every agent Ai , Mi,k = Mi,h .
It is easy to see that strong convergence implies convergence. Define
Conv(R) = {a | Conv(R, a) = true}
as the convergence model of R.
Let R = △0 → △1 → . . . → △k → . . . be a run where △k = (σ1,k , . . . , σn,k )
with σi,k = (EDBi,k , INi,k ). As there is a point h such that the environment
does not change after h, it is clear that ∀k ≥ h : EDBi,k = EDBi,h . The set
n
S
EDBi,h is called the stabilized environment of R.
EDB =
i=1

Definition 3.8
• A multiagent system is said to be weakly stabilizing if every run R is
convergent, and its convergence model Conv(R) is a stable model of PA in the
stabilized environment of R, i.e. Conv(R) is a stable model of IDBA ∪ EDB
where EDB is the stabilized environment of R.
• A multiagent system is said to be stabilizing if it is weakly stabilizing and
all of its runs are strongly convergent.
Theorem 3.1
IO-acyclic and bounded multiagent systems are weakly stabilizing.
Proof
See Appendix A.
Unfortunately, the above theorem does not hold for more general class of multiagent systems as the following example shows.

14

P. M. Dung, D. D. Hanh, and P. M. Thang

Example 3.8 (Continuation of example 3.3 and 3.5)
Consider the multiagent system A and run R in Example 3.3. It is obvious that A
is bounded but not IO-acyclic.
For every point k ≥ 4, M1,k = {a, b, c, f }, M2,k = {a, b, d}. Conv(R) = {a, b, c, d, f }.
The stabilized environment of R is EBD = {c, d}. The stable model of PA in the
stabilized environment of R is {c, d}, which is not the same as Conv(R). Hence the
system is not weakly stabilizing.
Boundedness is very important for the weak stabilization of multiagent systems.
Consider a multiagent system in the following example which is IO-acyclic, but not
bounded.
Example 3.9
Consider the following multiagent system
A = (A1 , A2 )
where
IDB1 = {q ← ¬r(x)
s(x) ← r(x)}
HBE1 = {}
HIN1 = {r(0), r(1), . . . }
EDB1,0 = ∅ IN1,0 = ∅

IDB2 = {r(x + 1) ← s(x)
r(0) ←}
HBE2 = {}
HIN2 = {s(0), s(1), . . . }
EDB2,0 = ∅ IN2,0 = ∅

Since HBE = HBE1 ∪ HBE2 = ∅, for every run R the stabilized environment
of R is empty. The stable model of PA in the stabilized environment of R is the set
{r(0), r(1), . . . }∪{s(0), s(1), . . . }. It is easy to see that for each run, the agents need
to exchange infinitely many messages to establish all the values of r(x). Hence for
every run R, for every point h ≥ 0 in the run: q ∈ M1,h , but q is not in the stable
model of PA in the stabilized environment of R. Thus the system is not weakly
stabilizing.
Are the boundedness and IO-acyclicity sufficient to guarantee the stabilization
of a multiagent system? The following example shows that they are not.
Example 3.10 (Continuation of Example 3.4 and 3.6)
Consider the multiagent system in Example 3.2. Consider the following run R with
no environment change after point 6.
4

2

1

(1)

(∅,{link(A1 ,A2 )})

4

1

(2)

(∅,{link(A4 ,A5 )})

1

4

(3)

5

2

5

△0 −−−→ △1 −−−→ △2 −−−→
△3 −−−−−−−−−−−→ △4 −−−→
△5 −−−−−−−−−−−→ △6 −−−→
4

1

△7 −−−→ △8 → . . .

(4)

Initially all links in the network are intact. The states and outputs of agents are
as follows:
• EDB1,0 = {link(A1 , A2 ), link(A1 , A4 )},

Stabilization of Cooperative Information Agents

15

EDB2,0 = {link(A2 , A1 ), link(A2 , A3 ), link(A2 , A5 )}
EDB3,0 = {link(A3 , A2 ), link(A3 , A5 )}.
EDB4,0 = {link(A4 , A1 ), link(A4 , A5 )}.
EDB5,0 = {link(A5 , A2 ), link(A5 , A3 ), link(A5 , A4 )}.
• INi,0 = ∅ for i = 1, . . . , 5.
• SPi,0 = {sp(Ai , Ai , 0)} for i = 1, . . . , 5.
Recall that SPi,k denotes the output of Ai at point k and is defined as follows:
SPi,k = {sp(Ai , Y, D)|sp(Ai , Y, D) ∈ Mi,k }
The following transitions occur in R:
• At point 0, A5 sends SP5,0 = {sp(A5 , A5 , 0)} to A2 . This causes the following
changes in the input and output of A2 :
IN2,1 = {sp(A5 , A5 , 0)}
SP2,1 = {sp(A2 , A2 , 0), sp(A2 , A5 , 1)}
• At point 1, A5 sends SP5,1 = {sp(A5 , A5 , 0)} to A4 . This causes the following
changes in the input and output of A4 :
IN4,2 = {sp(A5 , A5 , 0)}
SP4,2 = {sp(A4 , A4 , 0), sp(A4 , A5 , 1)}
• At point 2, A2 sends SP2,2 = {sp(A2 , A2 , 0), sp(A2 , A5 , 1)} to A1 . This causes
the following changes in the input and output of A1 :
IN1,3 = {sp(A2 , A2 , 0), sp(A2 , A5 , 1)}
SP1,3 = {sp(A1 , A1 , 0), sp(A1 , A2 , 1), sp(A1 , A5 , 2)}
• At point 3, the link between A1 and A2 is down as shown in Fig. 3. This
A❜1

A❜2

❜

❜

A4

A5

A❜3

Fig. 3. The network after the link between A1 and A2 is down
causes the following changes in the states and outputs of A1 and A2 :
EDB1,4 = {link(A1, A4 )}
EDB2,4 = {link(A2 , A3 ), link(A2 , A5 )}
IN1,4 = {sp(A2 , A2 , 0), sp(A2 , A5 , 1)} IN2,4 = {sp(A5 , A5 , 0)}
SP1,4 = {sp(A1 , A1 , 0)}
SP2,4 = {sp(A2 , A2 , 0), sp(A2 , A5 , 1)}

16

P. M. Dung, D. D. Hanh, and P. M. Thang
• At point 4, A4 sends SP4,4 = {sp(A4 , A4 , 0), sp(A4 , A5 , 1)} to A1 . This causes
the following changes in the input and output of A1 :
IN1,5 =
SP1,5 =

{sp(A2 , A2 , 0), sp(A2 , A5 , 1), sp(A4 , A4 , 0), sp(A4 , A5 , 1)}
{sp(A1 , A1 , 0), sp(A1 , A4 , 1), sp(A1 , A5 , 2)}

• At point 5, the link between A4 and A5 is down as shown in Fig. 4. This
A❜1

A❜2

❜

❜

A4

A5

A❜3

Fig. 4. The network after the link between A4 and A5 is down
causes the following changes in the states and outputs of A4 and A5 :
EDB4,6 = {link(A4 , A1 )}
IN4,6 = {sp(A5 , A5 , 0)}
SP4,6 = {sp(A4 , A4 , 0)}

EDB5,6 = {link(A5 , A2 ), link(A5 , A3 )}
IN5,6 = ∅
SP5,6 = {sp(A5 , A5 , 0)}

• At point 6, A1 sends SP1,6 = {sp(A1 , A1 , 0), sp(A1 , A5 , 2)} to A4 . This causes
the following changes in the input and output of A4 :
IN4,7 = {sp(A5 , A5 , 0), sp(A1 , A1 , 0), sp(A1 , A5 , 2)}
SP4,7 = {sp(A4 , A4 , 0), sp(A4 , A1 , 1), sp(A4 , A5 , 3)}
Note that at point 6, sp(A1 , A5 , 2) ∈ M1,6 , i.e. the length of the shortest path
from A1 to A5 equals to 2, is wrong. But A1 sends this information to A4 .
Now the length of the shortest paths to A5 of agents A1 , and A4 equal to 2,
and 3 respectively (i.e. sp(A1 , A5 , 2) ∈ M1,7 and sp(A4 , A5 , 3) ∈ M4,7 , are all
wrong. Later on A1 and A4 exchange wrong information, increase the shortest
paths to A5 after each round by 2 and go into an infinite loop.
The states and outputs of A1 and A4 at points 0 → 8 are shown in Fig. 5 and
Fig. 6 respectively.
This example shows that
Theorem 3.2
IO-acyclicity and boundedness are not sufficient to guarantee the stabilization of a
multiagent system.
As we have pointed out before, the routing example in this paper models the popular routing RIP protocol that has been widely deployed in the internet. Example

Stabilization of Cooperative Information Agents
k
0

3

EDB
{link(A1 , A2 ),
link(A1 , A4 )}
{link(A1 , A2 ),
link(A1 , A4 )}
{link(A1 , A2 ),
link(A1 , A4 )}
{link(A1 , A4 )}

4
5

{link(A1 , A4 )}
{link(A1 , A4 )}

6

{link(A1 , A4 )}

7

{link(A1 , A4 )}

8

{link(A1 , A4 )}

1
2

IN
∅

SP
{sp(A1 , A1 , 0)}

∅

{sp(A1 , A1 , 0)}

∅

{sp(A1 , A1 , 0)}

{sp(A2 , A2 , 0), sp(A2 , A5 , 1)}

{sp(A1 , A1 , 0), sp(A1 , A2 , 1),
sp(A1 , A5 , 2)}
{sp(A1 , A1 , 0)}
{sp(A1 , A1 , 0), sp(A1 , A4 , 1),
sp(A1 , A5 , 2)}
{sp(A1 , A1 , 0), sp(A1 , A4 , 1),
sp(A1 , A5 , 2)}
{sp(A1 , A1 , 0), sp(A1 , A4 , 1),
sp(A1 , A5 , 2)}
{sp(A1 , A1 , 0), sp(A1 , A4 , 1),
sp(A1 , A5 , 4)}

{sp(A2 , A2 , 0), sp(A2 , A5 , 1)}
{sp(A2 , A2 , 0), sp(A2 , A5 , 1),
sp(A4 , A4 , 0), sp(A4 , A5 , 1)}
{sp(A2 , A2 , 0), sp(A2 , A5 , 1),
sp(A4 , A4 , 0), sp(A4 , A5 , 1)}
{sp(A2 , A2 , 0), sp(A2 , A5 , 1),
sp(A4 , A4 , 0), sp(A4 , A5 , 1)}
{sp(A2 , A2 , 0), sp(A2 , A5 , 1),
sp(A4 , A4 , 0), sp(A4 , A5 , 3)}

17

Fig. 5. State and output of A1
k
0

6
7

EDB
{link(A4 , A1 ),
link(A4 , A5 )}
{link(A4 , A1 ),
link(A4 , A5 )}
{link(A4 , A1 ),
link(A4 , A5 )}
{link(A4 , A1 ),
link(A4 , A5 )}
{link(A4 , A1 ),
link(A4 , A5 )}
{link(A4 , A1 ),
link(A4 , A5 )}
{link(A4 , A1 )}
{link(A4 , A1 )}

8

{link(A4 , A1 )}

1
2
3
4
5

IN
∅

SP
{sp(A4 , A4 , 0)}

∅

{sp(A4 , A4 , 0)}

{sp(A5 , A5 , 0)}

{sp(A4 , A4 , 0), sp(A4 , A5 , 1)}

{sp(A5 , A5 , 0)}

{sp(A4 , A4 , 0), sp(A4 , A5 , 1)}

{sp(A5 , A5 , 0)}

{sp(A4 , A4 , 0), sp(A4 , A5 , 1)}

{sp(A5 , A5 , 0)}

{sp(A4 , A4 , 0), sp(A4 , A5 , 1)}

{sp(A5 , A5 , 0)}
{sp(A5 , A5 , 0), sp(A1 , A1 , 0),
sp(A1 , A5 , 2)}
{sp(A5 , A5 , 0), sp(A1 , A1 , 0),
sp(A1 , A5 , 2)}

{sp(A4 , A4 , 0)}
{sp(A4 , A4 , 0), sp(A4 , A1 , 1),
sp(A4 , A5 , 3}
{sp(A4 , A4 , 0), sp(A4 , A1 , 1),
sp(A4 , A5 , 3}

Fig. 6. State and output of A4
3.10 shows that RIP is not stabilizing. In configuration 4, the routers at the nodes
A1 , A4 go into a loop and continuously change the length of the shortest paths from
them to A5 from 2 to infinite. This is because the router at node A1 believes that
the shortest path from it to A5 goes through A4 while the router at A4 believes
that the shortest path from it to A5 goes through A1 . None of them realizes that
there is no more connection between them and A5 . 2 . The above theorem general2

This is one of the key reasons why RIP, a very simple internet routing protocol, is gradually
replaced by OSPF, a much more complex routing protocol (Huitema 2000)

18

P. M. Dung, D. D. Hanh, and P. M. Thang

izes this insight to multiagent systems. The conclusion is that in general it is not
possible for an agent to get correct information about its environment if this agent
can not sense all the changes in the environment by itself and has to rely on the
communications with other agents. This is true even if all the agents involved are
honest and do not hide their information.
Obviously, if a multiagent system is IO-acyclic and IO-finite, every agent would
obtain complete and correct information after finitely many exchanges of information with other agents. The system is stabilizing. Hence
Theorem 3.3
IO-acyclic and IO-finite multiagent systems are stabilizing.
Proof
See Appendix B.
4 Related Works and Conclusions
There are many research works on multiagent systems where agents are formalized
in terms of logic programming such as (Ciampolini et al. 2003), (Kowalski and Sadri 1999),
(Satoh and Yamamoto 2002). An agent in our framework could be viewed as an abductive logic program as in (Ciampolini et al. 2003), (Satoh and Yamamoto 2002)
where atoms in the input database could be considered as abducibles. Satoh and
Yamatomo formalized speculative computation with multiagent belief revision. The
semantics of multiagent systems, which is defined based on belief sets and the
union of logic programs of agents, is similar to our idea of “superagent”. An agent
in (Ciampolini et al. 2003) is composed of two modules: the Abductive Reasoning Module (ARM), and the Agent Behaviour Module (ABM). Agents are grouped
within bunches according to the requirements of interaction between agents. The coordination (collaboration) of agents is implicitly achieved through the semantics of
the consistency operators. In both works ((Ciampolini et al. 2003) and (Satoh and Yamamoto 2002))
the communication for agents is based on pull-technologies. The authors did not
address the stabilization issue of multiagent systems. Sadri, Toni and Torroni in
(Sadri et al. 2001) used a logic-based framework for negotiation to tackle the resource reallocation problem via pull-based communication technology and the solution is considered as “stabilization” property.
In this paper, we consider a specific class of cooperative information agents without considering effects of their actions on the environment e.g. in (Ciampolini et al. 2003),
(Kowalski and Sadri 1999), (Satoh and Yamamoto 2002). We are currently working
to extend the framework towards this generalized issue.
In this paper, a logic programming based framework for cooperative multiagent
systems is introduced, and the stabilization of multiagent systems is then formally
defined. We introduced sufficient conditions in general for multiagent systems under
which the stabilization is guaranteed. We showed that IO-acyclic and bounded
multiagent systems are weakly stabilizing. But IO-acyclicity and boundedness are
not sufficient to guarantee the stabilization of a multiagent system. We showed that

Stabilization of Cooperative Information Agents

19

IO-acyclic and IO-finite multiagent systems are stabilizing. Unfortunately these
conditions are strong. So it is not an easy task to ensure that agents eventually get
right information in the face of unpredictable changes of the environment.
Our research is inspired by the network routing applications. As the RIP ((Hedrick 1988),
(Huitema 2000)) is very simple and had been widely accepted and implemented.
But the RIP has many limitations such as the bouncing effect, counting to infinity,
looping, etc. Many versions and techniques of the RIP have been introduced to reduce undesired features of the RIP, but the problem could not be solved thoroughly.
With logic programming approach, we showed in this paper, the main reason is that
in the RIP, the computation of the overall problem solving algorithm is distributed
over the network, while the logic program which represents the routing algorithm
is not IO-finite, the stabilization of the system is thus not guaranteed. It is also a
reason why most experts prefer the OSPF ((Moy 1998), (Huitema 2000)), which is
much more complicated and sophisticated protocol, to the RIP for network routing.
We have assumed that information sent by an agent is obtained immediately by
the recipients. But communications in real networks always have delay and errors
in transmissions. We believe that the results presented in this paper could also be
extended for the case of communication with delay and errors.
In this paper communications for agents are based on push-technologies. It is interesting to see how the results could be extended to multiagent systems whose communication is based on pull-technologies ((Satoh and Yamamoto 2002), (Ciampolini et al. 2003)).

Appendix A Proof of theorem 3.1
First it is clear that the following lemma holds.
Lemma Appendix A.1
Let M be a stable model of a logic program P . For each atom a: a ∈ M iff there is
a clause a ← Bd in P such that M |= Bd.
Given an IO-acyclic and bounded multiagent system A = (A1 , . . . , An ). By
proposition 3.1, IDBA is acyclic.
Let
R = △0 → · · · → △h → . . .
be a run of A such that after point h there is no more change in the environment.
The stabilized environment of R is EDB = EDB1,h ∪ · · · ∪ EDBn,h . Let [[PA ]] be
the stable model of PA in the stabilized environment of R, i.e. the stable model of
IDBA ∪ EDB.
The height of an atom a in the atom dependency graph of PA denoted by π(a) is
the length of a longest path from a to other atoms in the atom dependency graph of
PA . Since IDBA is acyclic, there is no infinite path in the atom dependency graph
of PA . From the boundedness of IDBA , π(a) is finite.
Theorem 3.1 follows directly from the following lemma.

20

P. M. Dung, D. D. Hanh, and P. M. Thang

Lemma Appendix A.2
For every atom a, R is convergent for a and conv(R, a) = true iff a ∈ [[PA ]].
It is easy to see that lemma Appendix A.2 follows immediately from the following
lemma.
Lemma Appendix A.3
For every atom a, there is a point k ≥ h, such that at every point p ≥ k in R, for
every Ai such that a ∈ HBi , a ∈ Mi,p iff a ∈ [[PA ]].
Proof
We prove by induction on π(a). For each i, let HBIi = head(IDBi ).
• Base case: π(a) = 0 (a is a leaf in the dependency graph of PA ).
Let Ai be an agent with a ∈ HBi . There are three cases:
1. a ∈ HBIi . There must be a clause of the form a ← in IDBi . a ← is also in
IDBA . At every point m ≥ 0, a ∈ Mi,m and a ∈ [[PA ]].
2. a ∈ HBEi . There is no change in the environment after h, at every point
k ≥ h, a ∈ Mi,k iff a ∈ EDBi,k iff a ∈ [[PA ]].
3. a ∈ HINi . There must be an agent Aj such that D(i, j) 6= ∅ and a ∈ HBEj ∪
HBIj . By definition 3.5 of the run, there must be a point p ≥ h such that
there is a transition
j

i

△p −−→ △p+1
Moreover, every transition that can delete (or insert) a from (or into) INi
j

i

after point h must also have the form △q −−→ △q+1 for some Aj such that
D(i, j) 6= ∅ and a ∈ HBEj ∪ HBIj . By the definition of transition of the
j

i

form △ −−→ △′ in definition 3.5 and the operator U pa in section 3.2, for a
j i
transition △p −−→ △p+1 , Ai will update INi as follows
INi,p+1 = (INi,p \ D(i, j)) ∪ S
where S = D(i, j) ∩ Mj,p . Since a ∈ D(i, j), a ∈ Mi,p+1 iff a ∈ INi,p+1 iff
a ∈ Mj,p . As shown in 1 and 2, at every point k ≥ h, for every Aj such that
a ∈ HBIj ∪HBEj , a ∈ Mj,k iff a ∈ [[PA ]]. So at every point k ≥ p, a ∈ Mi,k+1
iff a ∈ [[PA ]].
We have proved that for each Ai such that a ∈ HBi there a point pi such that at
every point k ≥ pi , a ∈ Mi,k iff a ∈ [[PA ]]. Take p = max(p1 , . . . , pn ). At every point
k ≥ p, for every agent Ai such that a ∈ HBi , a ∈ Mi,k iff a ∈ [[PA ]].
• Inductive case: Suppose the lemma holds for every atom a with π(a) ≤ m, m ≥ 0.
We show that the lemma also holds for a with π(a) = m + 1.
Let Ai be an agent with a ∈ HBi . Clearly a 6∈ HBE ⊇ HBEi . There are two cases:
1. a ∈ HBIi . The atom dependency graph of PA is acyclic, every child b of a
has π(b) ≤ m. By the inductive assumption, for each b there is a point pb
such that at every point k ≥ pb , b ∈ Mi,pb iff b ∈ [[PA ]]. The set of children of
a in the atom dependency graph of PA is the same as the set of atoms in the

Stabilization of Cooperative Information Agents

21

body of all clauses of the definition of a. As IDBA is bounded, a has a finite
number of children in the atom dependency graph of PA and the definition of
a is finite. Let pa is the maximum number in the set of all such above pb where
b is a child of a. At every point k ≥ pa , for every child b of a, by the inductive
assumption, b ∈ Mi,k iff b ∈ [[PA ]]. We prove that a ∈ Mi,k iff a ∈ [[PA ]].
By lemma Appendix A.1, a ∈ Mi,k iff there is a rule a ← Bd in Pi,k =
IDBi ∪ EDBi,k ∪ INi,k such that Mi,k |= Bd. By inductive assumption for
every b ∈ atom(Bd), b ∈ Mi,k iff b ∈ [[PA ]]. Moreover a ← Bd is also a rule in
PA . Thus a ∈ Mi,k iff there is a rule a ← Bd in PA such that [[PA ]] |= Bd iff
a ∈ [[PA ]] (by lemma Appendix A.1).
2. a ∈ HINi . As shown in 1, for every Aj such that a ∈ HBIj there is a point
pj , such that at every point k ≥ pj , a ∈ Mj,k iff a ∈ [[PA ]]. Let p be the
maximum of all such pj . Clearly, at every point k ≥ p, for every Aj such that
a ∈ HBIj , a ∈ Mj,k iff a ∈ [[PA ]].
Follow similarly as case 3 in base case of the proof, there is a point p′ ≥ p + 1
such that at every point k ≥ p′ , a ∈ Mi,k iff a ∈ Mj,k . It also means that at
every point k ≥ p′ , a ∈ Mi,k iff a ∈ [[PA ]].
We have proved that for each Ai such that a ∈ HBi there a point pi such that at
every point k ≥ pi , a ∈ Mi,k iff a ∈ [[PA ]]. Take p = max(p1 , . . . , pn ). At every point
k ≥ p, for every agent Ai such that a ∈ HBi , a ∈ Mi,k iff a ∈ [[PA ]].

Appendix B Proof of theorem 3.3
Let A be an IO-acyclic and IO-finite multiagent system. Obviously A is also bounded.
Let R be a run of A. By theorem 3.1, R is convergent. By lemma Appendix A.3,
for every atom a in GA there is a point ka such that at every point p ≥ ka , for
every agent Ai such that a ∈ HBi , a ∈ Mi,p iff a ∈ [[PA ]]. As GA is finite, take
the largest number k of all such ka ’s for every atoms a in GA . Obviously, at every
point p ≥ k, for every agent Ai , Mi,k = Mi,p . Thus R is strongly convergent. The
system is stabilizing and theorem 3.3 follows immediately.

References
Apt K., Blair H., and Walker A.1988. Towards a theory of declarative knowledge,
In J. Minker editor, Foundations of Deductive Databases and Logic Programming, pp.
89–148, Morgan Kaufman, San Mateo, CA., 1988.
Bellman R. E., 1957, Dynamic Programming, Princeton University Press, Princeton,
N.J., 1957.
Brooks R. A., 2002, Robot: the future of flesh and machines, Penguin. 2002
Brooks. R.A., 1991, Intelligence without Representation, Artificial Intelligence, Vol.47,
1991, pp.139-159
Brooks, R. A, 1986, A robust layered control system for a mobile robot, IEEE Journal
of Robotics and Automation. RA-2, April, 1986, pp. 14-23.

22

P. M. Dung, D. D. Hanh, and P. M. Thang

Ciampolini A., Lamma E., Mello P., Toni F., and Torroni P., 2003, Co-operation
and competition in ALIAS: a logic framework for agents that negotiate, Annals of
Mathematics and Artificial Intelligence, Special Issue on Computational Logic in MultiAgent Systems, Volume 37, nos. 1-2, pp. 28-37, January 2003.
Dijkstra E., 1974, Self-stabilizing systems in spite of distributed control, Communications of the ACM, 17(11), 1974.
Durfee E.H., Lesser V. R., and Corkill D.D., 1995, Trends in Cooperative Distributed
Problem Solving, IEEE Transactions on Knowledge and Data Engineering. July, 1995.
Flatebo M., Datta A. K., and Ghosh S., 1994, Self-stabilization in distributed systems,
Chapter 2, Readings in Distributed Computer Systems, pp. 100–114, IEEE Computer
Society Press, 1994.
Ford L. R. J. and Fulkerson D. R., 1962, Flows in Networks, Princeton University
Press, Princeton, N.J., 1962
Gelfond M., and Lifschitz V., 1988, The stable model semantics for logic programming., In R. Kowalski and K. Bowen, editors, Logic Programming: Proc. of the Fifth
International Conference and Symposium, pp. 1070–1080, 1988.
Hedrick C., 1988, Routing Information Protocol, RFC–1058, Rutgers University, 1988.
Huitema C., 2000, Routing in the Internet, 2nd Edition, Prentice Hall, 2000.
Kowalski R. A. and Sadri F., 1999, From Logic Programming to Multiagent Systems,
Annals of matematics and Artificial Intelligence, Baltzer Science Publishers, Editors:
Dix J. and Lobo J., volume 25, pp. 391–420, 1999.
Moy J., 1998, OSPF Version 2, RFC-2328, 1998.
Rosenschein S. J. and Kaelbling L. P., 1995, A Situated View of Representation and
Control, Artificial Intelligence, No. 73, pp. 149–173, 1995.
Sadri F., Toni F. and Torroni P., 2001, Dialogues for Negotiation: Agent Varieties
and Dialogue Sequences, Proc. ATAL’01, International workshop on Agents, theories,
Architectures and Languages, J.J. Maher ed., and ”Intelligent Agents VIII”, LNAI 2333,
pp. 405-421, Springer Verlag, 2001.
Satoh K. and Yamamoto K., 2002, Speculative Computation with Multi-Agent Belief
Revision, Proceedings of the First International Joint Conference on Autonomous Agent
and Multiagent Systems, Bologna, Italy (2002).
Schneider M., 1993, Self-stabilization, ACM Computing Surveys, 25(1), pp. 45–67, 1993.
Shoham Y., 1993, Agent-oriented programming, Artificial Intelligence, No. 60, pp. 51–92,
1993.
Steels L. and Brooks R. , 1995, The Artificial Life Route to Artificial Intelligence:
building Embodied, Situated Agents, Lawrance Erlbaum Associates Publishers, 1995.
Wooldridge M., 1997, Agent-Based Software Engineering, IEEE Proc. Software Engineering 144 (1), pp. 26-37.
Wooldridge M. and Jennings N. R., 1995, Intelligent agents: Theory and practice,
The Knowledge Engineering Review, 10 (2), pp. 115-152.

