2012 - Technical Reports
Number Report Title 2012/1 The Rabin Index of Parity Games
Michael Huth, Jim Huan-Pu Kuo, and Nir Piterman, 20pp2012/2 Discovering Service Dependencies in Mobile Ad Hoc Networks
Petr Novotny, Bong Jun Ko and Alexander L. Wolf, 20pp2012/3 Techniques for Locating Service Faults in Mobile Ad Hoc Networks
Petr Novotny, Bong Jun Ko and Alexander L. Wolf, 17pp2012/4 Pessimistic Bi-Level Optimization
Wolfram Wiesemann, Angelos Tsoukalas, Polyxeni-Margarita Kleniati, Berc Rustem, 39pp
The Rabin Index of Parity Games
Michael Huth, Jim Huan-Pu Kuo, and Nir Piterman, 20ppWe study the descriptive complexity of parity games by taking into account the coloring of their game graphs whilst ignoring their ownership structure. Different colorings of the same graph are identified if they determine the same winning regions and strategies, for all ownership structures of nodes. The Rabin index of a parity game is the minimum of the maximal color taken over all equivalent coloring functions. We show that deciding whether the Rabin index is at least k is in P for k=1 but NP-hard for all fixed k greater than or equal to 2. We present an EXPTIME algorithm that computes the Rabin index by simplifying its input coloring function. When replacing simple cycle with cycle detection in that algorithm, its output over-approximates the Rabin index in polynomial time. Experimental results show that this approximation yields good values in practice.
Discovering Service Dependencies in Mobile Ad Hoc Networks
Petr Novotny, Bong Jun Ko and Alexander L. Wolf, 20ppThe combination of service-oriented applications, with their run-time service binding, and mobile ad hoc networks, with their transient communication topologies, brings a new level of complex dynamism to the structure and behavior of software systems. This complexity challenges our ability to understand the dependence relationships among system components when performing analyses such as fault localization and impact analysis. Current methods of dynamic dependence discovery, developed for use in fixed networks, assume that dependencies change slowly. Moreover, they require relatively long monitoring periods as well as substantial memory and communication resources, which are impractical in the mobile ad hoc network environment. We describe a new method, designed speciacally for this environment, that allows the engineer to trade accuracy against cost, yielding dynamic snapshots of dependence relationships. Through extensive simulations, we evaluate the performance of our method in terms of the accuracy of the discovered dependencies, and draw insights on the selection of critical parameters under various operational conditions.
Techniques for Locating Service Faults in Mobile Ad Hoc Networks
Petr Novotny, Bong Jun Ko and Alexander L. Wolf, 17ppFault localization in general refers to a technique for identifying the likely root causes of failures observed in systems formed from components. Fault localization in systems deployed on mobile ad hoc networks (MANETs) is a particularly challenging task because those systems are subject to a wider variety and higher incidence of faults than those deployed in fixed networks, the resources available to track fault symptoms are severely limited, and many of the sources of faults in MANETs are by their nature transient. We present a method for localizing the faults occurring in service-based systems hosted on MANETs. The method is based on the use of dependence data that are discovered dynamically through decentralized observations of service interactions. We employ both Bayesian and timing-based reasoning techniques to analyze the data in the context of a specific fault propagation model, deriving a ranked list of candidate fault locations. We present the results of an extensive set of experiments exploring a wide range of operational conditions to evaluate the accuracy of our method.
Pessimistic Bi-Level Optimization
Wolfram Wiesemann, Angelos Tsoukalas, Polyxeni-Margarita Kleniati, Berc Rustem, 39ppWe study a variant of the pessimistic bi-level optimization problem, which comprises constraints that must be satisfied for any optimal solution of a subordinate (lower-level) optimization problem. We present conditions that guarantee the existence of optimal solutions in such a problem, and we charac- terize the computational complexity of various subclasses of the problem. We then focus on problem instances that may lack convexity, but that satisfy a certain independence property. We develop conver- gent approximations for these instances, and we derive an iterative solution scheme that is reminiscent of the discretization techniques used in semi-infinite programming. We also present a computational study that illustrates the numerical behavior of our algorithm on standard benchmark instances.
