Aug 14, 2009

Actor Simulation Synchronization Issues

A while back I did up a post about using Scala actors in a synchronized simulation. I'm hoping to use this to model a simple economy, however I've run into a major problem and I'm trying to find a solution to it - which is why it took so long for me to write a follow-up to that last post.

The way the other simulation worked is by using synchronized time steps. Normally this is good because it means that actors which take varying amounts of time to process can all finish their job before the next time step starts. This also helps when you decide to scale and use a distributed system, you will end up having slower machines and network delay, but can still maintain synchronization because the faster machines will either do more work, or will wait for the slower machines.

Synchronization in my simulation was done using the Act and DoneAct messages. When an agent receives an Act message, it means that the next time step is starting and that they should begin processing. Then when they are done, they send a DoneAct message to the simulation driver to say that they have finished processing. The problem with this is that some agents may send messages to other agents that are finished. There is the scenario that an agent, A, sends a message to another agent, B, and then A sends the DoneAct message to the simulator. However B may well still be processing away the message, which may in turn affect agent C, which may then wrap around and affect agent A. Effectively this could turn into an infinite loop, and due to the nasty halting problem there is not really any general way of detecting this.

I have a solution, however I am not sure if it will work. Basically agents cannot communicate with one another if they are using the ! approach (asynchronous messaging). They can use the ?! method (synchronous method) where when agent A sends a message to agent B, agent A will wait for agent B to return before continuing execution (basically the same as a method call in traditional OO languages like C++ or Java). However in the case where agent A wants to send an asynchronous message to agent B, it can do so by sending a Delayed() object to the simulator, which will then send the message to B at the next time step.

Basically I'm thinking out loud here, hoping that by explaining things here it might give me some insights on how to go about building this thing. If anybody is interested in this type of thing and wants to give their two cents, feel free to comment :)

No comments: