Simulated time
From DCOPolis
DCOPolis' Networkless platform runs in simulated time using the Sefirs simulation kernel. The idea behind this type of simulation is to have each agent's thread of execution run sequentially such that no two agents are competing for CPU cycles. Although the algorithms end up being executed sequentially, DCOPolis is able to keep track of which portions of the execution would have occurred concurrently in a distributed setting, and thereby can provide an accurate prediction of what the distributed runtime would be. Thus, DCOPolis is able to give an accurate lower bound on the runtime of an algorithm. This process is as described in the following algorithm:
Algorithm Simulate-Distributed-Execution
Input: A set of agents, A, whose execution are to be simulated.
E is a map from the agents in A to execution times.
Initialize the execution time to zero for every agent:
(∀ a ∈ A : E(a) ↦ 0)
Q is a priority queue that orders the agents by ascending execution time;
the a ∈ Q with minimum E(a) is returned first.
t is the current time of the simulation.
t ← 0
Q ← A
while Q ≠ ∅, do
a ← poll(Q)
t ← E(a)
c ← cpuTime()
execute(a)
if isAlive(a), then
E(a) ↦ t + (cpuTime() - c)
Q ← Q ∪ { a }
else
a died during its execution
if Q = ∅, then
t ← t + (cpuTime() - c)
- "←" is a loose shorthand for "changes to". For instance, "largest ← item" means that the value of largest changes to the value of item.
- "return" terminates the algorithm and outputs the value that follows.
Note that the execute(a) command in the algorithm will cause the thread of execution of agent a to run until it either sends a message, sleeps, performs a join on another thread, or explicitly yields its execution; the execute(a) command will block until the agent's thread has done so. This type of behavior is accomplished programmatically using the programming language concept known as "continuations," which in the case of DCOPolis is provided through Sefirs. A sequence diagram visualizing the execution of two agents running in simulated time is given in Figure 1.
