Using message semantics to reduce rollback in the time warp mechanism

Hong Va Leong, Divyakant Agrawal, Jonathan R. Agre

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

3 Citations (Scopus)

Abstract

The time warp mechanism is one of the most favorite paradigm to carry out a distributed discrete event simulation, where the synchronization of events can be determined a priori when the program is being executed. The forward computation performed optimistically has to be rolled back when an out-of-order synchronization message is received. This excessive amount of rollback often haunts the performance of a time warp mechanism. We propose in this paper that the semantics of the synchronization messages being sent in a time warp execution can be exploited to reduce the amount of rollback. In particular, we illustrate with some examples how the commutativity and dependency properties of messages can be used to avoid certain types of rollback. For example, two commutative messages can be processed in any order and the resultant computation remains valid. We present a protocol for message handling in the time warp mechanism. We also give a correctness argument for the protocol, leaving the formal proof in the full paper. In the discussion, we suggest several optimization techniques that can be used in our protocol for a better improvement.
Original languageEnglish
Title of host publicationDistributed Algorithms - 7th International Workshop, WDAG 1993, Proceedings
PublisherSpringer Verlag
Pages309-323
Number of pages15
ISBN (Print)9783540572718
Publication statusPublished - 1 Jan 1993
Externally publishedYes
Event7th International Workshop on Distributed Algorithms, WDAG 1993 - Lausanne, Switzerland
Duration: 27 Sep 199329 Sep 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume725 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Workshop on Distributed Algorithms, WDAG 1993
Country/TerritorySwitzerland
CityLausanne
Period27/09/9329/09/93

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this