A UML Profile for SysML-Based Comodeling for Embedded Systems Simulation and Synthesis - Mischkalla, Fabian; Müller, Wolfgang; He, Da (Proceedings of the M-BED Workshop)
It's wide application in the area of software engineering, UML is still not fully accepted for other engineering domains like for electronic systems design. The main obstacle is due to a major gap in the design flow between UML-based modeling and verification. To overcome this gap, we introduce a UML profile for synthesizable SystemC and C and present its implementation in the context of the advanced SysML modeling environment of ARTiSAN Studio. We demonstrate how to customize Studio for SystemC/C comodeling so that it can serve as a verification and synthesis front-end.

Eine strukturierte Methode zur Generierung von SystemVerilog-Testumgebungen aus textuellen Anforderungsbeschreibungen - Bol, Alexander; Müller, Wolfgang; Krupp, Alexander (Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen (MBMV))

The SATURN Approach to SysML-based HW/SW Codesign - Müller, Wolfgang; He, Da; Mischkalla, Fabian; Wegele, Arthur; Larkham, Adrian; Whiston, Paul; Penil, Pablo; Villar, Eugenio; Mitas, Nikolaos; Kritharidis, Dimitros; Azcarate, Florent; Carballeda, Manuel (Proceedings of the IEEE Computer Society Annual Symposium on VLSI)
The main obstacle for the wide acceptance of UML and SysML in the design of electronic systems is due to a major gap in the design flow between UML-based modeling and SystemC-based verification. To overcome this gap, we present an approach developed in the SATURN project which introduces UML profiles for the co-modeling of SystemC and C with code generation support in the context of the SysML tool suite ARTiSAN Studio®. We finally discuss the evaluation of the approach by two case studies.
Keywords: Communicate Sequential Process Virtual Platform Smart Camera Synchronous Data Flow Artisan Studio

Generation of Executable Testbenches from Natural Language Requirement Specifications for Embedded Real-Time Systems - Müller, Wolfgang; Bol, Alexander; Krupp, Alexander; Lundkvist, Ola
We introduce a structured methodology for the generation of executable test environments from textual requirement specifications via UML class diagrams and the application of the classification tree methodology for embedded systems. The first phase is a stepwise transformation from unstructured English text into a textual normal form (TNF), which is automatically translated into UML class diagrams. After annotations of the class diagrams and the definition of test cases by sequence diagrams, both are converted into classification trees. From the classification trees we can finally generate SystemVerilog code. The methodology is introduced and evaluated by the example of an Adaptive Cruise Controller.
Keywords: Natural Language UML SystemVerilog Testbenches

Mutation-Analysis Directed Constrained Random Verification - Xie, Tao; Letombe, Florian; Müller, Wolfgang

An Eclipse-based Framework for the IP-XACT-enabled Assembly of Mixed-Level IPs - Xie, Tao; Defo, Gilles B.; Müller, Wolfgang

Verification of a CAN Bus Model in SystemC with Functional Coverage - Defo, Gilles B.; Müller, Wolfgang; Kuznik, Christoph (Proceedings of SIES 2010)
Many heterogeneous embedded systems, for example industrial automation and automotive applications, require hard-real time constraints to be exhaustively verified - which is a challenging task for the verification engineer. To cope with complexity, verification techniques working on different abstraction levels are best practice. SystemC is a versatile C++ based design and verification language, offering various mechanisms and constructs required for embedded systems modeling. Using the add-on SystemC Verification Library (SCV) elemental constrained-random stimuli techniques may be used for verification. However, SCV has several drawbacks such as lack of functional coverage. In this paper we present a functional coverage library that implements parts of the IEEE 1800-2005 SystemVerilog standard and allows capturing functional coverage throughout the design and verification process with SystemC. Moreover, we will demonstrate the usability of the approach with a case study working on a CAN bus model written in SystemC.
Keywords: Libraries; Generators; Transfer functions; Monitoring; Computational modeling; Driver circuits; Adaptation model

Distributed Coordination of Task Migration for Fault-Tolerant FlexRay Networks - Klobedanz, Kay; Defo, Gilles B.; Müller, Wolfgang; Kerstan, Timo (Proceedings of SIES 2010)
In this paper we present an approach to increase the fault tolerance in FlexRay networks by introducing backup nodes to replace defect ECUs (Electronic Control Units). In order to reduce the memory requirements of such backup nodes, we distribute redundant tasks over different nodes and propose the distributed coordinated migration of tasks of the defect ECU to the backup node at runtime. This approach enhances our former work in, where we extended the FlexRay bus schedule by redundant slots to consider changes in the communication/slot assignment and investigated and evaluated different solutions to migrate the redundant tasks to the backup node using the static and/or dynamic segment of the communication cycle for transmissions. We present the approach of distributed coordination for migration and communication instead of additional dedicated coordinator nodes to further increase the fault tolerance. With this approach we improve the safety of FlexRay networks by avoiding a possible single point of failure due to a dedicated coordinator node also minimizing the necessary time needed for a reconfiguration after an ECU failure. Furthermore, we reduce the overhead within the communication and the demand for additional hardware components.
Keywords: Fault tolerant systems; Protocols; Redundancy; Runtime; Payloads; Schedules

Verification of Real-Time Properties for Hardware-Dependant Software - Müller, Wolfgang; da S. Oliveira, Marcio F.; Zabel, Henning; Becker, Markus (Proceedings of HLDVT2010)
Seamless HW/SW codesign flows support early verification of hardware and Hardware-dependent Software (HdS) like drivers, operating systems, and firmware. For early estimation and verification, the application of SystemC in combination with Instruction Set Simulators and Software Emulators like QEMU is widely accepted. In this article, we present an advanced design flow for HW, (RT)OS and HdS refinement and verification with focus on the transition from abstract RTOS verification to full system RTOS/HdS emulation. In the context of assertion-based verification, we introduce a set of generic real-time properties which can be reused and verified at different abstraction levels and discuss their application. The properties are presented by the means of IEEE standard PSL assertions which are applied for mixed SystemC/HdS models.
Keywords: Hardware; Microprogramming; Application software; Timing; Protocols; Virtual prototyping; Real time systems; Sampling methods; Operating systems; Emulation

Design Space Abstraction and Metamodeling for Embedded Systems Design Space Exploration - Oliveira, Marcio F. S.; do Nascimento, Francisco Assis M.; Müller, Wolfgang (Proceedings of MoMPES 2010)

Strong NP-hardness of the quantum separability problem - Gharibian, Sevag (Quantum Information & Computation)
Given the density matrix rho of a bipartite quantum state, the quantum separability problem asks whether rho is entangled or separable. In 2003, Gurvits showed that this problem is NP-hard if rho is located within an inverse exponential (with respect to dimension) distance from the border of the set of separable quantum states. In this paper, we extend this NP-hardness to an inverse polynomial distance from the separable set. The result follows from a simple combination of works by Gurvits, Ioannou, and Liu. We apply our result to show (1) an immediate lower bound on the maximum distance between a bound entangled state and the separable set (assuming P != NP), and (2) NP-hardness for the problem of determining whether a completely positive trace-preserving linear map is entanglement-breaking.

Towards Adaptive Networking for Embedded Devices based on Reconfigurable Hardware - Lübbers, Enno; Platzner, Marco; Plessl, Christian; Keller, Ariane; Plattner, Bernhard (Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA))

Pruning the Design Space for Just-In-Time Processor Customization - Grad, Mariusz; Plessl, Christian (Proc. Int. Conf. on ReConFigurable Computing and FPGAs (ReConFig))

An Open Source Circuit Library with Benchmarking Facilities - Grad, Mariusz; Plessl, Christian (Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA))

Configurable Processor Architectures: History and Trends - Andrews, David; Plessl, Christian (Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA))

Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA)

Using Shared Library Interposing for Transparent Acceleration in Systems with Heterogeneous Hardware Accelerators - Beisel, Tobias; Niekamp, Manuel; Plessl, Christian (Proc. Int. Conf. on Application-Specific Systems, Architectures, and Processors (ASAP))

Reconfigurable Nodes for Future Networks - Keller, Ariane; Plattner, Bernhard; Lübbers, Enno; Platzner, Marco; Plessl, Christian (Proc. IEEE Globecom Workshop on Network of the Future (FutureNet))

Rupeas: Ruby Powered Event Analysis DSL - Woehrle, Matthias; Plessl, Christian; Thiele, Lothar (Proc. Int. Conf. Networked Sensing Systems (INSS))

Performance Estimation for the Exploration of CPU-Accelerator Architectures - Kenter, Tobias; Platzner, Marco; Plessl, Christian; Kauschke, Michael (Proc. Workshop on Architectural Research Prototyping (WARP), International Symposium on Computer Architecture (ISCA))

Smart Card basierte Berechnung einer Gruppensignatur als Teil einer biometrischen Authentisierung - Postler, Tim
Keywords: Diplomarbeit

Preference-Based Multi-Objective Particle Swarm Optimization Using Desirabilities - Mostaghim, Sanaz; Trautmann, Heike; Mersmann, Olaf (Parallel Problem Solving from Nature, PPSN XI)
The integration of experts’ preferences is an important aspect in multi-objective optimization. Usually, one out of a set of Pareto optimal solutions has to be chosen based on expert knowledge. A combination of multi-objective particle swarm optimization (MOPSO) with the desirability concept is introduced to efficiently focus on desired and relevant regions of the true Pareto front of the optimization problem which facilitates the solution selection process. Desirability functions of the objectives are optimized, and the desirability index is used for selecting the global best particle in each iteration. The resulting MOPSO variant DF-MOPSO in most cases exclusively generates solutions in the desired area of the Pareto front. Approximations of the whole Pareto front result in cases of misspecified desired regions.

Benchmarking Evolutionary Algorithms: Towards Exploratory Landscape Analysis - Mersmann, Olaf; Preuss, Mike; Trautmann, Heike (Proceedings of the 11th International Conference on Parallel Problem Solving from Nature: Part I)
We present methods to answer two basic questions that arise when benchmarking optimization algorithms. The first one is: which algorithm is the ’best’ one? and the second one: which algorithm should I use for my real world problem? Both are connected and neither is easy to answer. We present methods which can be used to analyse the raw data of a benchmark experiment and derive some insight regarding the answers to these questions. We employ the presented methods to analyse the BBOB’09 benchmark results and present some initial findings.
Keywords: benchmarking; multidimensional scaling; consensus ranking; evolutionary optimization; BBOB test set

On the Distribution of EMOA Hypervolumes - Mersmann, O; Trautmann, Heike; Naujoks, B; Weihs, C (Learning and Intelligent Optimization, 4$^th$ International Conference, LION 4, Venice, Italy)
We present methods to answer two basic questions that arise when benchmarking optimization algorithms. The first one is: which algorithm is the 'best' one? and the second one: which algorithm should I use for my real world problem? Both are connected and neither is easy to answer. We present methods which can be used to analyse the raw data of a benchmark experiment and derive some insight regarding the answers to these questions. We employ the presented methods to analyse the BBOB'09 benchmark results and present some initial findings.

Benchmarking evolutionary multiobjective optimization algorithms - Mersmann, Olaf; Trautmann, Heike; Naujoks, Boris; Weihs, Claus (IEEE Congress on Evolutionary Computation)
Choosing and tuning an optimization procedure for a given class of nonlinear optimization problems is not an easy task. One way to proceed is to consider this as a tournament, where each procedure will compete in different ‘disciplines’. Here, disciplines could either be different functions, which we want to optimize, or specific performance measures of the optimization procedure. We would then be interested in the algorithm that performs best in a majority of cases or whose average performance is maximal. We will focus on evolutionary multiobjective optimization algorithms (EMOA), and will present a novel approach to the design and analysis of evolutionary multiobjective benchmark experiments based on similar work from the context of machine learning. We focus on deriving a consensus among several benchmarks over different test problems and illustrate the methodology by reanalyzing the results of the CEC 2007 EMOA competition.

Sequential Parameter Optimisation for Multi-Objective Evolutionary Optimisation of Additive Layer Manufacturing - Ding, J; Wessing, S; Trautmann, Heike; Mehnen, J; Naujoks, B (Proceedings of the 7$^th$ CIRP International Seminar on Intelligent Computation in Manufacturing Engineering (CIRP ICME ’10))

New Uncertainty Handling Strategies in Multi-objective Evolutionary Optimization - Voß, Thomas; Trautmann, Heike; Igel, Christian (Parallel Problem Solving from Nature, PPSN XI)
Since many real-world optimization problems are noisy, vector optimization algorithms that can cope with noise and uncertainty are required. We propose new, robust selection strategies for evolutionary multi-objective optimization in the presence of noise. We apply new measures of uncertainty for estimating the recently introduced Pareto-dominance for uncertain and noisy environments (PDU). The first measure is the inter-quartile range of the outcomes of repeated function evaluations. The second is based on axis-aligned bounding boxes around the upper and lower quantiles of the sampled fitness values in objective space. Experiments on real and artificial problems show promising results.

Integration of Preferences in Hypervolume-Based Multiobjective Evolutionary Algorithms by Means of Desirability Functions - Wagner, Tobias; Trautmann, Heike (IEEE Transactions on Evolutionary Computation)
In this paper, a concept for efficiently approximating the practically relevant regions of the Pareto front (PF) is introduced. Instead of the original objectives, desirability functions (DFs) of the objectives are optimized, which express the preferences of the decision maker. The original problem formulation and the optimization algorithm do not have to be modified. DFs map an objective to the domain [0, 1] and nonlinearly increase with better objective quality. By means of this mapping, values of different objectives and units become comparable. A biased distribution of the solutions in the PF approximation based on different scalings of the objectives is prevented. Thus, we propose the integration of DFs into the S-metric selection evolutionary multiobjective algorithm. The transformation ensures the meaning of the hypervolumes internally computed. Furthermore, it is shown that the reference point for the hypervolume calculation can be set intuitively. The approach is analyzed using standard test problems. Moreover, a practical validation by means of the optimization of a turning process is performed.

Work roll cooling system design optimisation in presence of uncertainty and constrains - Azene, Y.T.; Roy, R.; Farrugia, D.; Onisa, C.; Mehnen, J.; Trautmann, Heike (CIRP Journal of Manufacturing Science and Technology)
The paper presents a framework to optimise the design of work roll based on the cooling performance. The framework develops meta-models from a set of finite element analyses (FEA) of the roll cooling. A design of experiment technique is used to identify the FEA runs. The research also identifies sources of uncertainties in the design process. A robust evolutionary multi-objective evaluation technique is applied to the design optimisation in constrained problems with real life uncertainty. The approach handles uncertainties associated both with design variables and fitness functions. Constraints violation within the neighbourhood of a design is considered as part of a measurement for degree of feasibility and robustness of a solution.
Keywords: Roll cooling design; Uncertainty; Design optimisation; Multi-objective optimisation; Constraint in design

Online convergence detection for evolutionary multi-objective algorithms revisited - Wagner, Tobias; Trautmann, Heike (IEEE Congress on Evolutionary Computation)
The design and application of termination criteria has become an important aspect in evolutionary multi-objective optimization. Online convergence detection (OCD) determines when further generations are no longer promising based on statistical tests on a set of performance indicators. The behavior of OCD mainly depends on two parameters, the number of preceding generations considered in the statistical tests and the desired variance limit. In this paper, guidelines for selecting appropriate combinations of these parameters are empirically derived based on design-of-experiment methods. Furthermore, a variant of OCD is introduced which directly operates on the hypervolume indicator - the internal measure of the SMS-EMOA. This allows a separated analysis of the variance criterion and reduces the complexity of OCD. Based on the experimental design, a systematic comparison with the classical OCD approach is performed and differences between the appropriate parameterizations of both variants are highlighted.

Mächtigkeit und Komplexität von Berechnungen mit der ganzzahligen Division - Lürwer-Brüggemeier, Katharina

On Fault-Tolerant Data Placement in Storage Networks - Mense, Mario

Size Equivalent Cluster Trees - Rendering CAD Models in Industrial Scenes - Kortenjan, Michael

Versatility of Bulk Synchronous Parallel Computing: From the Heterogeneous Cluster to the System on Chip - Bonorden, Olaf

Complexity and approximation of a geometric local robot assignment problem - Bonorden, Olaf; Degener, Bastian; Pietrzyk, Peter; Kempkes, Barbara

Complexity and Approximation of a Geometric Local Robot Assignment Problem - Bonorden, Olaf; Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter (Algorithmic Aspects of Wireless Sensor Networks)
We introduce a geometric multi-robot assignment problem. Robots positioned in a Euclidean space have to be assigned to treasures in such a way that their joint strength is sufficient to unearth a treasure with a given weight. The robots have a limited range and thus can only be assigned to treasures in their proximity. The objective is to unearth as many treasures as possible. We investigate the complexity of several variants of this problem and show whether they are in $\classP$ or are $\classNP$-complete. Furthermore, we provide a distributed and local constant-factor approximation algorithm using constant-factor resource augmentation for the two-dimensional setting with $\bigO(\log^*n)$ communication rounds.

3nuts: A Locality-Aware Peer-to-Peer Network Combining Random Networks, Search Trees, and DHTs - Schindelhauer, Christian; Mahlmann, Peter; Janson, Thomas
Categorizing peer-to-peer networks from an algorithmic point of view the two extremes of the spectrum are unstructured networks and networks based on plain distributed hash tables (DHT). Unstructured networks stand out with their simplicity, robustness, and support for complex queries. Though, they lack efficient query algorithms providing guarantees. On the other hand, DHT based networks feature efficient lookup algorithms with typically logarithmic hop distance and provide simple and efficient load balancing. Yet, they are limited to exact match queries and in many cases hard to maintain under churn.

Minimal Energy Path Planning for Wireless Robots - Ooi, Chia Ching; Schindelhauer, Christian (Mobile Networks and Applications (MONET))

Utilizing detours for energy conservation in mobile wireless networks - Ooi, Chia Ching; Schindelhauer, Christian (Telecommunication Systems)

Colouring Non-sparse Random Intersection Graphs - Raptopoulos, Christoforos L.; Nikoletseas, Sotiris E.; Spirakis, Paul G. (34st International Symposium on Mathematical Foundations of Computer Science)

Combinatorial Properties for Efficient Communication in Distributed Networks with Local Interactions - Nikoletseas, Sotiris E.; Raptopoulos, Christoforos L.; Spirakis, Paul G. (Proceedings of IPDPS - IEEE International Parallel & Distributed Processing Symposium)

Distributed Heterogeneous Hashing and Deterministic Dynamical Decompositions - Deveci, Deniz; Kortenjan, Michael; Schomaker, Gunnar (Parallel and Distributed Computing and Systems, Nr. 21)

Analysis and implementation of an Artificial Homeostatic Hormone System: A first case study in robotic hardware - Stradner, Jürgen; Hamann, Heiko; Schmickl, Thomas; Crailsheim, Karl (2009 IEEE/RSJ International Conference on Intelligent Robots and Systems)
One of the prominent challenges in mobile robotics is to develop control methodologies that allow the adaptation to dynamic and unforeseen environments. The classic approach of hand-coded controllers is very efficient for well-defined tasks and specific environments but poor in adapting to changing environmental conditions. One alternative approach is the application of evolutionary algorithms which need, in turn, easily evolvable representations of controllers. In this paper, we investigate one promising approach of an artificial hormone system as a control paradigm which is believed to be easily optimized by evolutionary processes. In a first step of this research, we focus on the simple task of collision avoidance. We present a brief mathematical analysis of this controller approach and an implementation of the controller on a mobile robot to check the feasibility in principle of our approach. The task is successfully accomplished and we conclude with a discussion of the hormone dynamics in the robot.

Two different approaches to a macroscopic model of a bio-inspired robotic swarm - Schmickl, Thomas; Hamann, Heiko; Wörn, Heinz; Crailsheim, Karl (Robotics and Autonomous Systems)
By compiling macroscopic models we analyze the adaptive behavior in a swarm of autonomous robots generated by a bio-inspired, distributed control algorithm. We developed two macroscopic models by taking two different perspectives: A Stock & Flow model, which is simple to implement and fast to simulate, and a spatially resolved model based on diffusion processes. These two models were compared concerning their prediction quality and their analytical power: One model allowed easy identification of the major feedback loops governing the swarm behavior. The other model allowed analysis of the expected shapes and positions of observable robot clusters. We found a high correlation in the challenges posed by both modeling techniques and we highlighted the inherent problems of inferring emergent macroscopic rules from a microscopic description of swarm behavior.

Pattern Formation as a Transient Phenomenon in the Nonlinear Dynamics of a Multi-Agent System - Hamann, Heiko; Troch, Inge; Breitenecker, F. (MATHMOD 2009 - 6th Vienna International Conference on Mathematical Modelling)

Compositional CSP Traces Refinement Checking - Wehrheim, Heike; Wonisch, Daniel (Electr. Notes Theor. Comput. Sci.)

Static Class Elements for Object-Z - Ruhroth, Thomas; Wehrheim, Heike (Electr. Notes Theor. Comput. Sci.)

Measure, Diagnose, Refactor: A Formal Quality Cycle for Software Models - Ruhroth, Thomas; Voigt, Hendrik; Wehrheim, Heike (35th Euromicro Conference on Software Engineering and Advanced Applications, SEAA 2009, Patras, Greece, August 27-29, 2009, Proceedings)

Integrated Formal Methods, 7th International Conference, IFM 2009, Düsseldorf, Germany, February 16-19, 2009. Proceedings

Hierarchisches Clustering mit minimalen Cluster-Durchmessern - Schröer, Carsten

Analyse und Evaluation eines identitätsbasierten Signcryption-Verfahrens - Liske, Gennadij

Die Schwierigkeit des k-Median Clusterings für Bregman-Divergenzen - Scholz, Christoph

Algorithms for the Bregman k-Median Problem - Ackermann, Marcel Rudolf

Reinforcement Learning for Blackjack - Kakvi, Saqib (Lecture Notes in Computer Science)

Coresets and Approximate Clustering for Bregman Divergences - Ackermann, Marcel R.; Blömer, Johannes (Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms)

Sampling methods for shortest vectors, closest vectors and successive minima - Blömer, Johannes; Naewe, Stefanie (Theoretical Computer Science)
Keywords: Geometry of numbers; Lattices; Shortest vectors

Three-Valued Spotlight Abstractions - Schrieb, Jonas; Wehrheim, Heike; Wonisch, Daniel (FM 2009: Formal Methods)

On the Analysis of Cryptographic Assumptions in the Generic Ring Model - Jager, Tibor; Schwenk, Jörg (Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings)

Musterbasiertes Re-Engineering von Softwaresystemen - Meyer, Matthias

Self-Organisation and Self-Optimization - Meyer auf der Heide, Friedhelm; Rammig, Franz-Josef (Public Service Review: Science and Technology)

Algorithmische und komplexitätstheoretische Aspekte kombinatorischer Preisoptimierung (Computational Aspects of Combinatorial Pricing Problems) - Briest, Patrick (it - Information Technology)

Foreword - D. Kleinberg, Robert; Scheideler, Christian (Theory Comput. Syst.)

Towards a Scalable and Robust DHT - Awerbuch, Baruch; Scheideler, Christian (Theory Comput. Syst.)

Robust random number generation for peer-to-peer systems - Awerbuch, Baruch; Scheideler, Christian (Theor. Comput. Sci.)

A Distributed and Oblivious Heap - Scheideler, Christian; Schmid, Stefan (Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part II)

A Self-stabilizing and Local Delaunay Graph Construction - Jacob, Riko; Ritscher, Stephan; Scheideler, Christian; Schmid, Stefan (Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings)

A distributed polylogarithmic time algorithm for self-stabilizing skip graphs - Jacob, Riko; W. Richa, Andrea; Scheideler, Christian; Schmid, Stefan; Täubig, Hanjo (Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, PODC 2009, Calgary, Alberta, Canada, August 10-12, 2009)

A DoS-resilient information system for dynamic data management - Baumgart, Matthias; Scheideler, Christian; Schmid, Stefan (SPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, Calgary, Alberta, Canada, August 11-13, 2009)

Brief Announcement: On the Time Complexity of Distributed Topological Self-stabilization - Gall, Dominik; Jacob, Riko; W. Richa, Andrea; Scheideler, Christian; Schmid, Stefan; Täubig, Hanjo (Stabilization, Safety, and Security of Distributed Systems, 11th International Symposium, SSS 2009, Lyon, France, November 3-6, 2009. Proceedings)

Stabilizing Consensus with the Power of Two Choices - Doerr, Benjamin; Ann Goldberg, Leslie; Minder, Lorenz; Sauerwald, Thomas; Scheideler, Christian (Algorithmic Methods for Distributed Cooperative Systems, 06.09. - 11.09.2009)

Rupeas: Ruby Powered Event Analysis DSL - Woehrle, Matthias; Plessl, Christian; Thiele, Lothar
Wireless Sensor Networks (WSNs) are unique embedded computation systems for distributed sensing of a dispersed phenomenon. While being a strongly concurrent distributed system, its embedded aspects with severe resource limitations and the wireless communication requires a fusion of technologies and methodologies from very different fields. As WSNs are deployed in remote locations for long-term unattended operation, assurance of correct functioning of the system is of prime concern. Thus, the design and development of WSNs requires specialized tools to allow for testing and debugging the system. To this end, we present a framework for analyzing and checking WSNs based on collected events during system operation. It allows for abstracting from the event trace by means of behavioral queries and uses assertions for checking the accordance of an execution to its specification. The framework is independent from WSN test platforms, applications and logging semantics and thus generally applicable for analyzing event logs of WSN test executions.
Keywords: Rupeas; DSL; WSN; testing

On Stackelberg Pricing with Computationally Bounded Consumers - Briest, Patrick; Hoefer, Martin; Gualà, Luciano; Ventre, Carmine (Lecture Notes in Computer Science)
In a Stackelberg pricing game a leader aims to set prices on a subset of a given collection of items, such as to maximize her revenue from a follower purchasing a feasible subset of the items. We focus on the case of computationally bounded followers who cannot optimize exactly over the range of all feasible subsets, but apply some publicly known algorithm to determine the set of items to purchase. This corresponds to general multi-dimensional pricing assuming that consumers cannot optimize over the full domain of their valuation functions but still aim to act rationally to the best of their ability. We consider two versions of this novel type of Stackelberg pricing games. Assuming that items are weighted objects and the follower seeks to purchase a min-cost selection of objects of some minimum weight (the Min-Knapsack problem) and uses a simple greedy 2-approximate algorithm, we show how an extension of the known single-price algorithm can be used to derive a polynomial-time (2 + ε)-approximation algorithm for the leader’s revenue maximization problem based on so-called near-uniform price assignments. We also prove the problem to be strongly NP-hard. Considering the case that items are subsets of some ground set which the follower seeks to cover (the Set-Cover problem) via a standard primal-dual approach, we prove that near-uniform price assignments fail to yield a good approximation guarantee. However, in the special case of elements with frequency 2 (the Vertex-Cover problem) it turns out that exact revenue maximization can be done in polynomial-time. This stands in sharp contrast to the fact that revenue maximization becomes APX-hard already for elements with frequency 3.

Concepts for Model Verification and Validation during Simulation Runtime - Laroque, Christoph; Fischer, Matthias; Dangelmaier, Wilhelm (European Simulation and Modelling Conference (ESM 2009))
Modern companies are nowadays confronted with an increasing demand of multiple products, where they need to perform more flexible every day. Cost-intensive decisions are to be confirmed in short times, in order to minimize risks and secure efficient production programs as well as material flows. Tools for this digital planning via simulation methods are one well established possibility to receive decision support. Nevertheless, the creation of the necessary simulation models is a complicated and error-prone process, where complexity of modeling, validation and verification depends on the used tool and its functionalities. This paper presents implemented concepts for an innovative user support in his tasks of verification and validation of simulation models during the execution of a simulation run. Time-intensive procedures like stopping simulation, parameterization and restarting within the problem analysis are simplified. So the user is able to focus on the real problem solving task.

Improving Network Coded Cooperation by Soft Information - Volkhausen, Tobias; Woldegebreal, Dereje H.; Karl, Holger (2009 6th IEEE Annual Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks Workshops)

Combining for Cooperative WLANs - A Reality Check Based on Prototype Measurements - Valentin, S.; Woldegebreal, D. H.; Volkhausen, T.; Karl, Holger (2009 IEEE International Conference on Communications Workshops)

Ein System zur aggregierten Visualisierung verteilter Materialflusssimulationen - Suess, Tim; Fischer, Matthias; Huber, Daniel; Laroque, Christoph; Dangelmaier, Wilhelm (Augmented & Virtual Reality in der Produktentstehung)

Creating Butterflies in the Core – A Network Coding Extension for MPLS/RSVP-TE - Biermann, Thorsten; Schwabe, Arne; Karl, Holger (NETWORKING 2009)

Modeling obstacles in INET/Mobility framework: motivation, integration, and performance - Lichte, Hermann S.; Weide, Jannis (Proceedings of the Second International ICST Conference on Simulation Tools and Techniques)

Design considerations for a network of information - Ahlgren, Bengt; Vercellone, Vinicio; D'Ambrosio, Matteo; Marchisio, Marco; Marsh, Ian; Dannewitz, Christian; Ohlman, Börje; Pentikousis, Kostas; Strandberg, Ove; Rembarz, René (Proceedings of the 2008 ACM CoNEXT Conference on - CONEXT '08)

Planar Visibility Counting - Fischer, Matthias; Hilbig, Matthias; Jähn, Claudius; Meyer auf der Heide, Friedhelm; Ziegler, Martin (Proc. 25th European Workshop on Computational Geometry)
For a fixed virtual scene (=collection of simplices) S and given observer position p, how many elements of S are weakly visible (i.e. not fully occluded by others) from p? The present work explores the trade-off between query time and preprocessing space for these quantities in 2D: exactly, in the approximate deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an O(m^2/n^2) space data structure for S that, given p and time O(log n), allows to approximate the ratio of occluded segments up to arbitrary constant absolute error; here m denotes the size of the Visibility Graph--which may be quadratic, but typically is just linear in the size n of the scene S. On the other hand, we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k) preprocessing time and space with similar approximation properties and query time O(k*polylog n), where k<n is an arbitrary parameter. We describe an implementation of this approach and demonstrate the practical benefit of the parameter k to trade memory for query time in an empirical evaluation on three classes of benchmark scenes.

Solution Patterns for the Development of Self-Optimizing Systems - Dumitrescu, Roman; Gausemeier, Jürgen; Dangelmaier, Wilhelm; Klöpper, Benjamin (Self-x in Engineering)

Education Programme at Eurographics 2009 - Domik, Gitta; Scateni, Riccardo (Computer Graphics Forum)

Quantitative myocardial perfusion PET combined with coronary anatomy derived from CT angiography: Validation of a new fusion and visualisation software - Fricke, Harald; Elsner, Andreas; Weise, Reiner; Bolte, Matthias; van den Hoff, Jörg; Burchert, Wolfgang; Domik, Gitta; Fricke, Eva (Zeitschrift für Medizinische Physik)
Keywords: Coronary artery disease; CT angiography; cardiac PET; quantitative perfusion measurement; Koronare Herzerkrankung; CT-Angiographie; PET; quantitative Perfusionsmessung

Proceedings of the Workshop on Model Driven Development of Advanced User Interfaces (MDDAUI'09), Sanibel Island (FL, USA)

Proceedings of Design for Future - 1. Workshop des GI-Arbeitskreises "Langlebige Softwaresysteme (L2S2)"

Language-Independent Change Management of Process Models - Gerth, Christian; Küster, Jochen; Engels, Gregor (Proceedings of the ACM/IEEE 12th International Conference on Model Driven Engineering Languages and Systems (MODELS'09). Denver (CO, USA))
In model-driven development approaches, process models are used at different levels of abstraction and are described by different languages. Similar to other software artifacts, process models are developed in team environments and underlie constant change. This requires reusable techniques for the detection of changes between different process models and the computation of dependencies and conflicts between changes. In this paper, we propose a framework for the construction of process model change management solutions that provides generic techniques for the detection of differences and the computation of dependencies and conflicts between changes. The framework contains an abstract representation for process models that serves as a common denominator for different process models. In addition, we show how the framework is instantiated exemplarily for BPMN.

SOA-Business Case - Assmann, Martin; Haack, Markus; Scheider, Hendrik; vom Hagen, Nico; Zacharias, Roger (Transform IT: Optimale Geschäftsprozesse durch eine transformierende IT)

A Holistic Software Engineering Method for Service-Oriented Application Landscape Development - Baumann, Andrea; Engels, Gregor; Hofmann, Alexander; Sauer, Stefan; Willkomm, Johannes (Proceedings of the First NAF Academy Working Conference on Practice-Driven Research on Enterprise Transformation (PRET 2009), Amsterdam (The Netherlands))
Enterprises are transforming into enterprises which follow from a business as well as from an IT perspective a service-oriented paradigm. This change towards service-oriented enterprise and IT architectures has to be reflected in the methodologies of developing whole application landscapes as well as individual applications. Quasar (Quality Software Architecture) has been developed as the standard architecture and development method of Capgemini sd&m for individual applications. For the development of service-oriented enterprise application landscapes, Quasar Enterprise has been designed. Both Quasar and Quasar Enterprise are integrated with each other within a holistic software engineering method to seamlessly cover the full development lifecycle of service-oriented application landscapes, from business modeling and service design to actual software development. In this paper, we illustrate how a company-wide ontology of development artifacts serves as the key feature for integrating both methods.

Model Driven Development of Advanced User Interfaces 2009 - Meixner, Gerrit; Görlich, Daniel; Breiner, Kai; Hußmann, Heinrich; Pleuß, Andreas; Sauer, Stefan; Van den Bergh, Jan (Proceedings of the 2009 International Conference on Intelligent User Interfaces)

Dependent and Conflicting Change Operations of Process Models - Küster, Jochen; Gerth, Christian; Engels, Gregor (Proceedings of the 5th European Conference on Model-Driven Architecture Foundations and Applications (ECMDA-FA'09))
Version management of models is common for structural diagrams such as class diagrams but still challenging for behavioral models such as process models. For process models, conflicts of change operations are difficult to resolve because often dependencies to other change operations exist. As a consequence, conflicts and dependencies between change operations must be computed and shown to the user who can then take them into account while creating a consolidated version. In this paper, we introduce the concepts of dependencies and conflicts of change operations for process models and provide a method how to compute them. We then discuss different possibilities for resolving conflicts. Using our approach it is possible to enable version management of process models with minimal manual intervention of the user.

Sicherstellen der Betrachtung von nicht-funktionalen Anforderungen in SCRUM-Prozessen durch Etablierung von Feedback - Engels, Gregor; Geisen, Silke; Sauer, Stefan; Port, Olaf (Informatik 2009 - Im Focus das Leben)

Integrated Specification and Quality Assurance for Large Business Information Systems - Salger, Frank; Sauer, Stefan; Engels, Gregor (Proceedings of the 2nd India Software Engineering Conference (ISEC'09))

Model-Based System Testing Using Visual Contracts - Güldali, Baris; Mlynarski, Michael; Wübbeke, Andreas; Engels, Gregor (Proceedings of Euromicro SEAA Conference 2009, Special Session on “Model Driven Engineering”)

Zautomatyzowane testy akceptacyjne dla aplikacji internetowych w programowaniu sterowanym testami - Mlynarski, Michael; Jureczko, Marian (Proceedings of Krajowa Konferencja In?ynierii Oprogramowania 2009)

A UML Framework for IP-XACT-based IP Management - Schattkowsky, Tim; Xie, Tao (Proceedings of the conference on Design Automation and Test in Europe (DATE 2009), Nice (France))

Towards Test-Driven Semantics Specification - Soltenborn, Christian; Engels, Gregor (Proceedings of the 12th International Conference on Model Driven Engineering Languages and Systems (MODELS 2009), Denver, Colorado (USA))
Behavioral models are getting more and more important within the software development cycle. To get the most use out of them, their behavior should be defined formally. As a result, many approaches exist which aim at specifying formal semantics for behavioral languages (e.g., Dynamic Meta Modeling (DMM), Semantic Anchoring). Most of these approaches give rise to a formal semantics which can e.g. be used to check the quality of a particular language instance, for instance using model checking techniques. However, if the semantics specification itself contains errors, it is more or less useless, since one cannot rely on the analysis results. Therefore, the language engineer must make sure that the semantics he develops is of the highest quality possible. To help the language engineer to achieve that goal, we propose a test-driven semantics specification process: the semantics of the language under consideration is first informally demonstrated using example models, which will then be used as test cases during the actual semantics specification process. In this paper, we present this approach using the already mentioned specification language DMM.

Improving Reusability of Dynamic Meta Modeling Specifications with Rule Overriding - Engels, Gregor; Fisseler, Daniela; Soltenborn, Christian (Proceedings of the 2009 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC 2009), Corvallis, Oregon (USA))

Semi-automated Test Planning for e-ID Systems by Using Requirements Clustering - Güldali, Baris; Funke, Holger; Jahnich, Michael; Sauer, Stefan; Engels, Gregor (24th IEEE/ACM International Conference on Automated Software Engineering (ASE 2009), 16-20 November 2009, Auckland, New Zeland)
In acceptance testing, customer requirements as specified in system specifications have to be tested for their successful implementation. This is a time-consuming task due to inherent system complexity and thus a large number of requirements. In order to reduce efforts in acceptance testing, we introduce a novel approach that exploits redundancies and implicit relations in requirements specifications, which are based on multi-viewpoint techniques, in our case the reference model for open distributed processing (RM-ODP). It deploys requirements clustering and linguistic analysis techniques for reducing the total number of test cases. We report on concrete experiences with this approach within joint R&D work of the Software Quality Lab (s-lab) of the University of Paderborn and HJP Consulting, an international consulting company, specialized in planning, procurement and acceptance testing of national electronic identification (e-ID) systems. The paper is concluded with an overview on the current tool support especially for automated detection of the redundancies and implicit relations in requirements. Also the future work on the tool support for the overall test specification process is discussed.

Identifying Software Product Line Component Services - Assmann, Martin; Engels, Gregor; von der Maßen, Thomas; Wübbeke, Andreas (Proceedings of International Conference on Evaluation of Novel Approaches to Software Engineering (ENASE 09))

Flow Synchronization for Network Coding - Biermann, Thorsten; Dräxler, Martin; Karl, Holger (Journal of Communications)