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

2005-19: Tangent-Linear Models by Augmented LL-Parsers
by Volker Stolz 09 Sep '05

09 Sep '05

The following technical report is available from http://aib.informatik.rwth-aachen.de: Tangent-Linear Models by Augmented LL-Parsers Uwe Naumann, Andre Vehreschild AIB 2005-19 We describe a novel method for the generation of tangent-linear code by augmentation of LL-parsers generated by the software tool ANTLR. The main advantage of this approach to source code augmentation is the missing requirement for an internal representation of the original program. We consider this work as the basis for further investigations into how far this technique can be extended in the context of more sophisticated transformations, for example, the automatic generation of adjoint codes. Our prototype tool AD_C_ANTLR currently accepts a subset of the ANSI C standard. We discuss its theoretical basis, and we present case studies to underline the elegance of the parser-based approach to source augmentation.

1 0

2005-17: Syntax-directed Derivative Code (Part II: Intraprocedural Adjoint Code)
by Volker Stolz 06 Sep '05

06 Sep '05

The following technical report is available from http://aib.informatik.rwth-aachen.de: Syntax-directed Derivative Code (Part II: Intraprocedural Adjoint Code) Uwe Naumann AIB 2005-17 This is the second instance in a series of papers on single-pass generation of derivative codes by syntax-directed translation. We consider the automatic generation of adjoint code by reverse mode automatic differentiation implemented as the bottom-up propagation of synthesized attributes on the abstract syntax tree. A proof-of-concept implementation is presented based on a simple LALR(1) parser generated by the parser generator bison. The approach offers all advantages of adjoint codes while exhibiting the highly desirable ease of implementation.

1 0

2005-18: Einsatz von Features im Software-Entwicklungsprozess - Abschlußbericht des GI-Arbeitskreises "Features"
by Volker Stolz 31 Aug '05

31 Aug '05

The following technical report is available from http://aib.informatik.rwth-aachen.de/: Einsatz von Features im Software-Entwicklungsprozess - Abschlußbericht des GI-Arbeitskreises "Features" Thomas von der Maßen, Klaus Müller, John MacGregor, Eva Geisberger, Jörg Dörr, Frank Houdek, Harbhajan Singh, Holger Wußmann, Hans-Veit Bacher, Barbara Paech AIB 2005-18 Featurelisten und Featuremodelle gewinnen als Mittel zur Definition von Produkten, aber auch zur Planung und Verfolgung von Entwicklungsprozessen zunehmend an Bedeutung. Die Feature-Modellierung als solche hat ihre Wurzeln im Bereich der Domänen-Analyse. Die praktische Anwendung von Features und Feature-Modellen geht aber deutlich über diesen Fokus hinaus. Features werden als Grundlage zum Festlegen des Produktumfangs, zur Release-Planung, zur Kommunikation zwischen Auftraggebern und Auftragnehmern, zur Projektplanung und vielem mehr eingesetzt. Natürlich werden vollständige Feature-Modelle auch als Grundlage zur Produktkonfiguration im Produktlinien-Kontext eingesetzt. Der vorliegende Bericht dokumentiert die Arbeiten des GI-Arbeitskreises "Features". Im Rahmen dieser Arbeit wurden unterschiedliche Einsatzszenarien der Feature-Modellierung dokumentiert. Zudem wurde eine Analyse des Feature-Begriffs durchgeführt, welche die Gemeinsamkeiten und Unterschiede in der Verwendung des Feature-Begriffs in den jeweiligen Einsatzgebieten beleuchtet und Gütekriterien für Features und Feature-Modelle skizziert. Keywords: Feature, Feature-Modellierung, Feature-Einsatzgebiete, Strategische Produktplanung, Feature-Gütekriterien

1 0

2005-16: Syntax-Directed Derivative Code (Part I: Tangent-Linear Code)
by Volker Stolz 25 Aug '05

25 Aug '05

The following technical report is available from http://aib.informatik.rwth-aachen.de: Syntax-Directed Derivative Code (Part I: Tangent-Linear Code) Uwe Naumann AIB 2005-16 This is the first instance in a series of papers on single-pass generation of various types of derivative code by syntax-directed translation. We consider the automatic generation of tangent-linear code by forward mode automatic differentiation implemented as the bottom-up propagation of synthesized attributes on the abstract syntax tree. A proof-of-concept implementation is presented based on a simple LALR(1) parser generated by the parser generator bison. The proposed technique can be generalized easily to provide a method for computing directional derivatives of mathematical vector functions that are implemented as computer programs in the context of computer algebra systems and compilers for scientific computing. The main advantage of the syntax-directed approach to automatic differentiation is its elegance in terms of the implementation.

1 0

2005-15: The Complexity of Derivative Computation
by Volker Stolz 07 Aug '05

07 Aug '05

The following technical report is available from http://aib.informatik.rwth-aachen.de/: The Complexity of Derivative Computation Uwe Naumann AIB 2005-15 We show that the problem of accumulating Jacobian matrices by using a minimal number of floating-point operations is NP-complete by reduction from Ensemble Computation. The proof makes use of the fact that, deviating from the state-of-the-art assumption, algebraic dependences can exist between the local partial derivatives. It follows immediately that the same problem for directional derivatives, adjoints, scalar, and higher derivatives is NP-complete too.

1 0

2005-14: Code Stabilization
by Volker Stolz 05 Jul '05

05 Jul '05

The following technical report is available from http://aib.informatik.rwth-aachen.de/: Code Stabilization Felix C. Freiling, Sukumar Ghosh AIB 2005-14 Dijkstra's concept of self-stabilization assumes that faults can only affect the variables of a program. We study the notion of self-stabilization if faults can also affect (i.e., augment) the program code of a system. A code stabilizing system automatically recovers from (almost) arbitrary perturbations of its program code. We prove some lower bounds for code stabilizing systems and argue that code stabilization has many resemblances to the area of integrity management in the domain of security.

1 0

2005-13: Revisiting Failure Detection and Consensus in Omission Failure Environments
by Volker Stolz 05 Jul '05

05 Jul '05

The following technical report is available from http://aib.informatik.rwth-aachen.de/: Revisiting Failure Detection and Consensus in Omission Failure Environments Carole Delporte-Gallet, Hugues Fauconnier, Felix C. Freiling AIB 2005-13 It has recently been shown that fair exchange, a security problem in distributed systems, can be reduced to a fault tolerance problem, namely a special form of distributed consensus. The reduction uses the concept of security modules which reduce the type and nature of adversarial behavior to two standard fault-assumptions: message omission and process crash. In this paper, we investigate the feasibility of solving consensus in asynchronous systems in which crash and message omission faults may occur. Due to the impossibility result of consensus in such systems, following the lines of unreliable failure detectors of Chandra and Toueg, we add to the system a distributed device that gives information about the failure of other processes. Then we give an algorithm using this device to solve the consensus problem. Finally, we show how to implement such a device in an asynchronous system using some weak timing assumptions.

1 0

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