Agent Mobility

Reification of the Computational State

Werner Van Belle

Theo D’Hondt

Programming Technology Lab (PROG)

Departement Computer Science (DINF)

Vrije Universiteit Brussel (VUB)

Mobile Multi Agent Systems

A Mobile Agent is an Active Autonomous Component

Able to Communicate with others

Able to Migrate to other Agent Systems

The Agent system is the “Operating System” to support these components

Mobile Multi Agent Systems

Application: interconnection of agents

Wide Area Network

Fine grained component structure

Frequent migration of components

Migration

Weak Migration

The agent can only migrate whenever the agent has stored its entire state in its objects

Cooperation from the agent is required

Code should be written in a special ‘state’-based manner

Migration

Strong Migration

At any moment an agent can migrate to another place without any special requirements towards the agent

The agent doesn’t need to take special precautions when executing

The agent doesn’t have to ‘cooperate’

Code mobility becomes useful

Use of Migration (I)

Use of Migration (II)

1

2

3

4

Use of Migration (II)

1

2

3

4

Migration Example

Fac(n)::

{

if(n\\1 = 0,

agentmove(place(“tecra/ses1”)),

agentmove(place(“void.tecra/ses1”)));

if(n=1,1,n*Fac(n-1))

}

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Strong Migration

1. Stop the execution of an agent

2. Gather its ‘state’

3. Remove the agent from memory

4. Send its entire ‘state’

5. Receive its entire state

6. Create an agent

7. Restore its entire state

8. Start running the agent

Capturing a Process

Non Interpreted Environment
memcpy of the process

 We need an Interpreted Environment

Heterogeneous architectures

Pointers to the operating system

Capturing a Process

Interpreted Environment:

Serialization and Deserialization of the program graph

Platform Independent

 No fixed connections to system dependent resources

 Interface all system resources as agents which cannot migrate

Pointers to system dependent resources: eg.

user interface, disc access...

Strong Migration

Problem: capturing the execution state of a running process

State consist of

Data Space

Code Space

Runtime Stack & IP

Runtime Stack

public Object evaluate(Object ag)

{if (ag instanceof Applicable)

{Object closure=evaluate(ag.application()));

Object[] args=evalargs(ag.args());

return closure.apply(args);}

if (ag instanceof Identifier) return lookup(ag);

if (ag instanceof Integer) return ag;

...

Evaluator uses its own runtime stack to

simulate a stack for the evaluated program

Runtime Stack

These stack frames are almost impossible to serialize

Capturing the instruction pointer is impossible

Deserializing is difficult because we have to create a new valid stack

Jumping to the new instruction pointer is impossible

 Explicit stack needed

 Write the evaluator in Continuation Passing Style

 Reify the stack in the evaluated language

Explicit Stack

2 stacks

continuation stack (what do I need to do in the future)

expression stack (the expressions accompaigning the continuations)

Before calling a continuation

the stack contains the arguments this continuation needs

Explicit Stack

2 stacks

continuation stack (what do I need to do in the future)

expression stack (the expressions accompaigning the continuations)

After calling a continuation

the top of the stack contains the result of the continuation

Explicit Stack

Pop_CNT, Pop_EXP

removes and returns value at top of expression/continuation stack

Push_CNT, Push_EXP

Pushes value at top of expression/continuation stack

Peek_CNT, Peek_EXP

returns value at top of continuation/expression stack

Poke_CNT, Poke_EXP

sets value at top of expression/continuation stack

Explicit Stack

Main-loop

while(1)

{CNT:POP_CNT();

CNT.invoke()}

Explicit Stack

evaluate

EXP

EXP

evaluate thunk

void evaluate()

{exp=PEEK_EXP();

if (exp instanceof Integer) return;

if (exp instanceof Identifier)

{POKE_EXP(lookup(exp));

return;}

...

Explicit Stack

evaluate

EXP

evaluate thunk

void evaluate()

...

if (exp instanceof Applicable)

{Object [] args=exp.args();

Object apl=exp.application();

POKE_EXP(apl);

PUSH_CNT(apply);

PUSH_CNT(evaluate);

PUSH_EXP(args);

PUSH_CNT(swap);

PUSH_CNT(evalargs);

}

}

apply

evaluate

evalargs

IDEN

EXP[]

Stack Trace

Program

Display(200+300)

evaluate

display(200+300)

Stack Trace

Program

Display(200+300)

apply

display

evaluate

[200+300]

swap

evalargs

Stack Trace

Program

Display(200+300)

apply

display

evaluate

[200+300]

swap

evalargs

Stack Trace

Program

Display(200+300)

apply

display

evaluate

[200+300]

swap

evalargs

Stack Trace

Program

Display(200+300)

apply

display

evaluate

[200+300]

swap

evalargs

Stack Trace

Program

Display(200+300)

apply

display

evaluate

[500]

swap

Stack Trace

Program

Display(200+300)

apply

evaluate

[500]

display

Stack Trace

Program

Display(200+300)

apply

[500]

native #83

Stack Trace

Program

Display(200+300)

“500”

Reification of the Runtime Stack

A snapshot of the complete execution state can be taken, just by serializing the runtime stack

Enables strong mobility

Concurrency can be managed within the evaluated language with primitives such as capture and restore

CBorg

Developed at PROG

Goal is to implement a light weight MMAS for research purposes

We try to achieve as much transparency as possible

Features

location transparency

strong migration

Based upon an interpreted language Pico

A CBorg Agent

Object Oriented

Own Code & Data Space

Single Threaded

Agents run concurrently

Can send messages to other agents

Can migrate to other agent systems

Written in PICO

CBorg/ Creation/Killing

Interactive

Dynamic

createagent(<object>,<name>)

agentdie(agent)

>

- makes a deep copy of the <object>

- super will not be copied

CBorg/ Communication

“tecra.vub.ac.be/ses1”

a:agent(“void.tecra/disc”);

a.calculate([[1,2],[3,4]]);

“void.tecra/disc”

calculate(matrix)::display(matrix)

- Automatic serialisation and deserialisation

- Transparant routering

- Connectionless

CBorg/ Callbacks

“tecra.vub.ac.be/ses1”

a:agent(“void.tecra/negate”);

a.calculate([[1,2]],agentself()) -> void

“void.tecra/negate”

calculate(matrix,resultto)::

resultto.display(negate(matrix))

- Asynchronous message passing

- Queued at receiver side

- Returns always void at sender side

CBORG/ Serialisation

“tecra/ses1”

makepoint(x,y)::

{show()::display(x+”:“+y);

clone()}

a:agent(“tecra/ses2”)

p:makepoint(10,20)

a.show(p) -> 10:20

“tecra/ses2”

show(p)::p.show()

- pass objects by reference

- pass primitives by value

CBorg/ Migration

CBorg supports the notion of strong migration.

agentmove(place(“void.tecra”))

Cborg

http://progwww.vub.ac.be/

poolresearch/cborg

werner.van.belle@vub.ac.be
tjdhondt@vub.ac.be

Location Transparent Routing in Mobile Agent Systems

Werner Van Belle

1999-12-10T14:12:40