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.
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.
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
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.
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.
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.
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.
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.
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.
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.