Solutions to Problem Set 4

1. (4 points) One model of mobile agents defines the following methods:

dispatch(URL) - sends the executing agent to the location specified by the URL.
run() - a method that is called whenever the agent is created or begins executing at a new location

A typical agent in this model has the following structure:

class MyAgent
{ private state-variables;

     public void run()
     { //do some computation at the current site
       //decide on next location to visit
       dispatch(nextLocation);
     }
   }

In this model is that the dispatch method does not return. That is, you cannot structure the run method in the following way:

       public void run()
      { //do first part of the computation at the current site
         //decide on next location to visit
         dispatch(nextLocation);
         //do second part of the computation at the next site
      }

because the second part of the computation would never be executed.

The question: why are the dispatch and run methods defined as they are in this model. Hint: consider what would have to be done to allow the dispatch method to return at its new location.

Before we discuss the solution, let's clarify the meaning of the word 'return' in this question. It does not refer to an agent returning to a location that it had visited previously. The question is referring to the dispatch method returning. What happens when a method returns? Execution continues with the statement after the method call. The question asks about the dispatch method returning at a new location; this is because a side effect (indeed, the intended effect) of the dispatch method is for the agent to move to another site on which it will continue execution. So, when the agent moves as a result of the dispatch method, and when the dispatch method returns, code will continue executing at the new location, beginning with the statement after the method call.

So let's call the way this agent model is actually implemented as described above "method A." So, in method A, the dispatch method must be the last statement in the run method. Also, when the dispatch method is called and the agent moves to another site, the run method is restarted from the beginning. Now, let's call the way it's not implemented "method B." So, in method B, once the agent moves from one site to another because of an invocation of the dispatch method, the execution of the run method doesn't restart, but instead resumes execution at the new site with the statement immediately after the dispatch call.

The reason the model is defined as it is (method A) is because of the following: To allow the model to behave as described in method B, the agent would need to capture the state of its execution (thread or process) and take that state with it to the new site. In method A, only the state of the agent needs to be captured and transferred, which is much simpler and easier than capturing the state of an executing thread or process. The state of an agent can be represented by just the variables and other storage that are defined as part of the agent. Also, the code for the agent needs to be transferred. But, in method B, we would need to capture the state of that code in the middle of its execution and transfer it, which would involve "serializing" the system stack, possibly the heap, the Process Control Block (or similar information, such as the program counter), etc.

Also, what if the agent were to open a file or a socket connection before the dispatch call, and used it after the call? Then a resourced obtained at one site would have to be used at a different site. Coordinating this could be quite difficult.

2. (6 points) In one mobile agent system, agents are guaranteed to receive messages sent to them regardless of the agent's movements. For example, suppose that agent A is initially located at site X but moves from site X to site Y and then to size Z while a message M is being sent to agent A at site X. The system guarantees that M will be received by A. Propose and evaluate two different ways in which the message handling can be implemented to guarantee the delivery of messages. Evaluate each proposal in terms of overhead, reliability, and message delay.

There are many possible solutions to this problem, and almost any reasonable solution is correct. The important part is the evaluation of the methods that you choose to provide. Many method could be proposed, including:

Whenever an agent moves from site X to site Y, it leaves a "forwarding address" with X saying that it is now at Y. Each time an agent moves, it adds another such link in the chain of forwarding addresses that can lead a message to the agent. The message delivery system would follow this chain to get the message to the agent.
If an agent is not at the site to which the message is sent, then the site could broadcast the message to all sites, in the hopes that the agent will be at one of the recipient sites. This is probably not the best solution, but it is possible.
There could be a centralized "post office" that can always know the location of an agent. When sending a message to an agent, the sender can consult the post office (or ask it to act on its behalf) to see where the agent is and deliver the message to it. When an agent moves from one place to another, it would tell the post office where it will be.
There could be a "home" for an agent that always knows where an agent is. This is similar to the "post office" scheme, but instead of one site that knows where every agent is, there will be many sites that know where some of the agents are (collectively, though, the sites would know where all agents are -- each agent must have a home site that knows where it is.)