May 2005 - tr-announce - lists.rwth-aachen.de

2005-11: A Counterexample to the Fully Mixed Nash Equilibrium Conjecture
by Volker Stolz 10 May '05

10 May '05

The following technical report is available from http://aib.informatik.rwth-aachen.de/: A Counterexample to the Fully Mixed Nash Equilibrium Conjecture Simon Fischer, Berthold Vöcking AIB 2005-11 We study a well-known resource allocation game introduced by Koutsoupias and Papadimitriou. It was conjectured by Gairing et al. that the fully mixed Nash equilibrium is the worst Nash equilibrium for this game. The known algorithms for approximating the so-called "price of anarchy" w.r.t. mixed equilibria rely on this conjecture. We present a counterexample to the conjecture showing that fully mixed equilibria cannot be used to approximate the price of anarchy within reasonable factors.

1 0

2005-10: Automata and Logics for Message Sequence Charts
by Volker Stolz 10 May '05

10 May '05

The following technical report is available from http://aib.informatik.rwth-aachen.de/: Automata and Logics for Message Sequence Charts Benedikt Bollig AIB 2005-10 A message-passing automaton is an abstract model for the implementation of a distributed system whose components communicate via message exchange and thereby define a collection of communication scenarios called message sequence charts. In this thesis, we study several variants of message-passing automata in a unifying framework. We classify their expressiveness in terms of state-space properties, synchronization behavior, and acceptance mode and also compare them to algebraic characterizations of sets of message sequence charts, among them the classes of recognizable and rational languages. We then focus on finite-state devices with global acceptance condition that communicate via a priori unbounded channels. We show them to be exactly as expressive as the existential fragment of monadic second-order logic over message sequence charts and to be strictly weaker than full monadic second-order logic. It turns out that message-passing automata cannot be complemented and that they cannot be determinized in general. Those results rely on a new proof technique, which allows to apply graph acceptors as introduced by Thomas to the framework of message sequence charts.

1 0

2005-09: Byzantine Fault Tolerance on General Hybrid Adversary Structures
by Volker Stolz 09 May '05

09 May '05

The following technical report is available from http://aib.informatik.rwth-aachen.de/: Byzantine Fault Tolerance on General Hybrid Adversary Structures Klaus Kursawe, Felix C. Freiling AIB 2005-09 Adversary structures are a generalization of the classical ``at most $t$-out-of-$n$'' threshold failure model which is used in many published Byzantine-tolerant protocols. An adversary structure basically lists all coalitions of parties whose corruption the protocol should tolerate. Using adversary structures it is possible to encode dependent failure models, such as ``either all Linux machines fail or all Windows machines but not both at the same time''. We describe a general technique that allows to transform an algorithm designed for the threshold model into an algorithm that works for general adversary structures. Our technique is based on several (partly informal) rules which describe how the algorithm and its proof must be augmented so that general adversary structures can be tolerated. We demonstrate the applicability of our approach by transforming an asynchronous Byzantine-tolerant reliable broadcast protocol into one that tolerates Byzantine adversary structures. We also consider similar transformations for hybrid failures (combinations of different fault models) and discuss ways to map adversary structures to the real world and manage them efficiently.

1 0