Parallel Discrete Event Simulation Using Lookback

 

Who controls the past, controls the future.
Who controls the present, controls the past.

---- 1984 by George Orwell

Everyone who has played the classical computer game "Command and Conquer", or who has read the book 1984, should know the above quotation. Here, however, I am more willing to talk about discrete event simulation. This famous quotation perfectly summarizes a discovery made with my advisor, Professor Szymanski, during my research on the parallel discrete event simulation.

In reality, time appeared intuitively matter-of-fact before the advent of modern science. People naively believed in absolute time, as if there were a single global clock in our physical world. Of course,  we now know that this is not true according to Einstein's theory of relativity. Stephen Hawking suggested, in his A Brief History of Time, that there exist at least three arrows of time, which all point to the same direction; they are thermodynamic arrow, cosmological arrow, and psychological arrow.

In simulation, it appeared again that time was so simple. The course of a simulation was thought to have to follow a non-decreasing arrow of time, which we may call a computational arrow. This works fine for sequential simulations, but immediately runs into difficulty when the simulation is carried out on multiple processors, where a single global clock is no longer existent. To overcome this problem, researchers had developed a synchronization method which depends on the ability to predict the future, named lookahead. By looking into the future, each simulation on a single processor can adhere to the computational arrow of time.

Another class of synchronization protocols emerged in 1985, when David Jefferson published his famous paper, Virtual Time, in which the computational arrow of time can be reversed. Each processor tries to advance its simulation time aggressively, until a causality error occurs. In such a case, the simulation is forced to roll back in the opposite direction of the computational time arrow to the point at which the causality error can be prevented. But still, the net result is that the simulation still follows the computational arrow of time.

Our discovery that the execution of a simulation need not stick to the computational arrow of time frees the simulation furthermore by allowing out-of-timestamp order execution, which is made possible by the ability to change the past, named lookback. Interestingly, although lookback and lookahead seem to be two unrelated concepts, because they deal with different parts in the arrow of simulation time, it turns out that lookback incorporates lookahead. The reason is quite simple indeed, for when the simulation time is aggressively advanced, the future becomes the past. As a result, in the simulation world changing the past is easier than predicting the future. This is opposite to the real world, where changing the past is impossible while people have been able to predict the future to some extent from time to time.

The discovery of lookback enables a new class of synchronization protocols which have obtained good performance results on queuing network simulations and wireless network simulations. We are now looking into the possibility of applying it to other simulations, such as communication network simulations and biological simualtions. The lesson we learnt from the process of making such a discovery is important: the simulation world is quite different from the real world, and we must free our mind from the common sense obtained from the real work experiences, if we wish to fully understand in the simulation world what is possible and what is not.

Related Publications