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.Shwartz, A.Subject: search.filters.subject.Signal Processing Systems

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    On Constrained Optimization of the Klimov Network and Related Markov Decision Processes
    (1991) Makowski, Armand M.; Shwartz, A.; ISR
    We solve a constrained version of the server allocation problem for a Klimov network and establish that the optimal constrained schedule is obtained by randomizing between two fixed priority schemes. This generalizes work of Nain and Ross in the context of the competing queue problem, and also covers the discounted cost case.

    In order to establish these results we develop a general framework for optimization under a single constraint in the presence of index-like policies. This methodology is in principle of wider applicability.

  • 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
    Guaranteed Performance Regions for Markov Models
    (1991) Shimkin, N.; Shwartz, A.; ISR
    A user facing a multi-user resource-sharing system considers a vector of performance measures (e.g. response times to various tasks). Acceptable performance is defined through a set in the space of performance vectors. Can the user obtain a (time- average) performance vector which approaches this desired set? We consider the worst-case scenario, where other users may, for selfish reasons, try to exclude his vector from the desired set. For a Markovian model of the system, we give a sufficient condition for approachability (which is also necessary for convex sets), and construct appropriate policies. The mathematical formulation leads to an approachability theory for stochastic games.