Page 41 - Data Science Algorithms in a Week

26 Edwin Cortes, Luis Rabelo and Gene Lee

Figure 1: The process of rollback in TW using antimessages and the process of cancellation of events.

Breathing Time Buckets (BTB)

BTB is a hybrid between the Fixed Time Buckets algorithm and TW (Steinman,
1993). Unlike TW, “messages generated while processing events are never actually
released until it is known that the event generating the messages will never be rolled
back” (Steinman, 1993). This means that messages which cause invalid events with
potential antimessages are not released. Therefore, BTB is a hybrid in the following
sense:

 BTB is TW without antimessages.
 BTB processes events in time window cycles like Fixed Time Buckets however
cycles are not fixed.

The Event Horizon is an important concept in BTB (Steinman, 1994). The event
horizon is the point in time where events generated by the simulation turn back into the
simulation. At the event horizon, all new events that were generated through event
processing at the previous “bucket” could be sorted and merged back into the main event
queue. Parallelism can be exploited because the event processed in each event horizon
cycle has time tags earlier than the cycle’s event horizon. Therefore, it is important to
calculate the Global Event Horizon (GEH) with its respective Global Virtual Time (GVT)
to avoid problems with events that will be scheduled in others simulation objects
(Steinman, 1994). The local event horizon (Figure 2) only considers the event horizon for
events being processed on its node, while the global event horizon factors all nodes in its