Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Author: search.filters.author.Lubachevsky, Boris D.

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    An Analysis of Rollback-Based Simulation
    (1991) Lubachevsky, Boris D.; Shwartz, A.; Weiss, A.; ISR
    We present and analyze a general model of rollback in parallel processing. The analysis points out three possible modes where rollback may become excessive; we provide an example of each type. We identify the parameters which determine a stability, or efficiency region for the simulation. Our analysis suggests the possibility of a dangerous "phase-transition" from stability to instability in the parameter space. In particular, a rollback algorithm may work efficiently for a small system but become inefficient for a large system. Moreover, for a given system, it may work quickly for a while and then suddely slow down.

    On the positive side, we give a tunable algorithm, Filtered Rollback, that is designed to avoid the failure modes. Under appropriate assumptions, we provide a rigorous mathematical proof that Filtered Rollback is efficient, if implemented on a reasonably efficient multiprocessor. In particular: we show that the average time t to complete the simulation of a system with N nodes and R events on a p -processor PRAM satisfies t = 0 ((R/p) + (R/N) log p).

    The analysis is based on recent work by the authors on Branching Random Walks with a barrier.

  • Thumbnail Image
    Item
    A Braching Random Walk with a Barrier
    (1991) Biggins, J.D.; Lubachevsky, Boris D.; Shwartz, Adam; Weiss, Alan; ISR
    Suppose that a child is likely to be weaker than its parent, and child who is too weak will not reproduce. What is the condition for a family to survive? Let b denote the mean number of children a viable parent will have; we suppose that this is independent of strength of strength as long as strength is positive. Let F denote the distribution of the change in strength from parent to child, and define h = supq (- log U eqt dF(t))). We show that the situation is black or white: 1) If b < eh then P(family line dies) = 1, 2) If b > eh then P(family survives) > 0. Define f(x) := E(number of members in the family | initial strength x). We show that if b < eh, then there exists a positive constant C such that limx ƀ e-ax f(x) = C where a is the smaller of the (at most) two positive roots of b U est dF(t) = 1. We also find an explicit expression for f(x) when the walk is on a lattice and is skip-free to the left. This process arose in an analysis of rollback-based simulation, and these results are the foundation of that analysis.