Many distributed and parallel discrete-event simulation algorithms assume that processes only communicate through message passing. Cota and Sargent, in contrast, assume the existence of shared memory, permitting one process to cheaply access the state of another process.

The authors take a refreshing view by starting from first principles in formulating their algorithm. They begin by defining discrete-event simulation and examine the implications of partitioning the event list and event code modules among a set of logical processes (LPs) while allowing shared access to state variables. Their conservative algorithm determines when an LP can execute the head event in its event list. An LP traverses two graphs, of predecessor and neighbor LPs, created before simulation program execution. Let LP P simulate event e. P’s predecessors include LPs that schedule events in P. Traversing predecessors yields a minimum next event time. P’s neighbors include all LPs that (1) schedule events that e cancels, (2) cancel events that e schedules, (3) read or write state variables that e writes, and (4) write variables that e reads. Traversing neighbors verifies that all neighbors simulate their next event after timet.

The paper is well written, although the reader must commit several definitions to memory. The authors clearly relate their proposal to existing work. For example, the proposed algorithm requires only one processor to participate in each graph traversal and never deadlocks.

The algorithm has two costs: two partial graph traversals every time an event is executed and locking shared state variables on every access. The question of how these costs compare to the overhead in other parallel simulation algorithms is left unanswered.