Incremental Inductive Verification of Parameterized Timed Systems - Isenberg, Tobias (Proceedings of the 15th International Conference on Application of Concurrency to System Design (ACSD))
We propose an incremental workflow for the verification of parameterized systems modeled as symmetric networks of timed automata. Starting with a small number of timed automata in the network, a safety property is verified using IC3, a state-of-the-art algorithm based on induction.The result of the verification, an inductive strengthening, is reused proposing a candidate inductive strengthening for a larger network.If the candidate is valid, our main theorem states that the safety property holds for all sizes of the network of timed automata. Otherwise the number of automata is increased and the next iteration is started with a new run of IC3.We propose and thoroughly examine optimizations to our workflow, e.g. Feedback mechanisms to speed up the run of IC3.

HybridTE: Traffic Engineering for Very Low-Cost Software-Defined Data-Center Networks - Wette, Philip; Karl, Holger (Proceedings of the 4th European Workshop on Software Defined Networks (EWSDN 2015))
The size of modern data centers is constantly increasing. As it is not economic to interconnect all machines in the data center using a full-bisection-bandwidth network, techniques have to be developed to increase the efficiency of data-center networks. The Software-Defined Network paradigm opened the door for centralized traffic engineering (TE) in such environments. Up to now, there were already a number of TE proposals for SDN-controlled data centers that all work very well. However, these techniques either use a high amount of flow table entries or a high flow installation rate that overwhelms available switching hardware, or they require custom or very expensive end-of-line equipment to be usable in practice. We present HybridTE, a TE technique that uses (uncertain) information about large flows. Using this extra information, our technique has very low hardware requirements while maintaining better performance than existing TE techniques. This enables us to build very low-cost, high performance data-center networks.

Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures - Scheideler, Christian; Setzer, Alexander; Strothmann, Thim Frederik (Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS))
Distributed applications are commonly based on overlay networks interconnecting their sites so that they can exchange information. For these overlay networks to preserve their functionality, they should be able to recover from various problems like membership changes or faults. Various self-stabilizing overlay networks have already been proposed in recent years, which have the advantage of being able to recover from any illegal state, but none of these networks can give any guarantees on its functionality while the recovery process is going on. We initiate research on overlay networks that are not only self-stabilizing but that also ensure that searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. We call this property monotonic searchability. We show that in general it is impossible to provide monotonic searchability if corrupted messages are present in the system, which justifies the restriction to system states without corrupted messages. Furthermore, we provide a self-stabilizing protocol for the line for which we can also show monotonic searchability. It turns out that even for the line it is non-trivial to achieve this property. Additionally, we extend our protocol to deal with node departures in terms of the Finite Departure Problem of Foreback et. al (SSS 2014). This makes our protocol even capable of handling node dynamics.

Towards a Universal Approach for the Finite Departure Problem in Overlay Networks - Koutsopoulos, Andreas; Scheideler, Christian; Strothmann, Thim Frederik (Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS))
A fundamental problem for overlay networks is to safely exclude leaving nodes, i.e., the nodes requesting to leave the overlay network are excluded from it without affecting its connectivity. There are a number of studies for safe node exclusion if the overlay is in a well-defined state, but almost no formal results are known for the case in which the overlay network is in an arbitrary initial state, i.e., when looking for a self-stabilizing solution for excluding leaving nodes. We study this problem in two variants: the Finite Departure Problem (FDP) and the Finite Sleep Problem (FSP). In the FDP the leaving nodes have to irrevocably decide when it is safe to leave the network, whereas in the FSP, this leaving decision does not have to be final: the nodes may resume computation when woken up by an incoming message. We are the first to present a self-stabilizing protocol for the FDP and the FSP that can be combined with a large class of overlay maintenance protocols so that these are then guaranteed to safely exclude leaving nodes from the system from any initial state while operating as specified for the staying nodes. In order to formally define the properties these overlay maintenance protocols have to satisfy, we identify four basic primitives for manipulating edges in an overlay network that might be of independent interest.

The impact of communication patterns on distributed locally self-adjusting binary search trees - Strothmann, Thim Frederik (Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM))
This paper introduces the problem of communication pattern adaption for a distributed self-adjusting binary search tree. We propose a simple local algorithm, which is closely related to the nearly thirty-year-old idea of splay trees and evaluate its adaption performance in the distributed scenario if different communication patterns are provided.To do so, the process of self-adjustment is modeled similarly to a basic network creation game, in which the nodes want to communicate with only a certain subset of all nodes. We show that, in general, the game (i.e., the process of local adjustments) does not converge, and convergence is related to certain structures of the communication interests, which we call conflicts.We classify conflicts and show that for two communication scenarios in which convergence is guaranteed, the self-adjusting tree performs well.Furthermore, we investigate the different classes of conflicts separately and show that, for a certain class of conflicts, the performance of the tree network is asymptotically as good as the performance for converging instances. However, for the other conflict classes, a distributed self-adjusting binary search tree adapts poorly.

The complexity of pure equilibria in mix-weighted congestion games on parallel links - Monien, Burkhard; Mavronicolas, Marios (Information Processing Letters)
We revisit the simple class of weighted congestion games on parallel links [10], where each player has a non-negative weight and her cost on the link she chooses is the sum of the weights of all players choosing the link. We extend this class to mix-weighted congestion games on parallel links, where weights may as well be negative. For the resulting simple class, we study the complexity of deciding the existence of a pure equilibrium, where no player could unilaterally improve her cost by switching to another link.We show that even for a singlenegative weight, this decision problem is strongly NP-complete when the number of links is part of the input; the problem is NP-complete already for two links. When the number of links is a fixed constant, we show, through a pseudopolynomial, dynamic programming algorithm, that the problem is not strongly NP-complete unless P = NP; the algorithm works for any number of negative weights.

Systematically Deriving Quality Metrics for Cloud Computing Systems - Becker, Matthias; Lehrig, Sebastian; Becker, Steffen (Proceedings of the 6th ACM/SPEC International Conference on Performance Engineering)
In cloud computing, software architects develop systems for virtually unlimited resources that cloud providers account on a pay-per-use basis. Elasticity management systems provision these resources autonomously to deal with changing workload. Such changing workloads call for new objective metrics allowing architects to quantify quality properties like scalability, elasticity, and efficiency, e.g., for requirements/SLO engineering and software design analysis. In literature, initial metrics for these properties have been proposed. However, current metrics lack a systematic derivation and assume knowledge of implementation details like resource handling. Therefore, these metrics are inapplicable where such knowledge is unavailable.To cope with these lacks, this short paper derives metrics for scalability, elasticity, and efficiency properties of cloud computing systems using the goal question metric (GQM) method. Our derivation uses a running example that outlines characteristics of cloud computing systems. Eventually, this example allows us to set up a systematic GQM plan and to derive an initial set of six new metrics. We particularly show that our GQM plan allows to classify existing metrics.

SynRace: Decentralized Load-Adaptive Multi-path Routing without Collecting Statistics - Schwabe, Arne; Karl, Holger (Proceedings of the 4th European Workshop on Software Defined Networks (EWSDN 2015))
Multi-rooted trees are becoming the norm for modern data-center networks. In these networks, scalable flow routing is challenging owing to vast number of flows. Current approaches either employ a central controller that can have scalability issues or a scalable decentralized algorithm only considering local information. In this paper we present a new decentralized approach to least-congested path routing in software-defined data center networks that has neither of these issues: By duplicating the initial (or SYN) packet of a flow and estimating the data rate of multiple flows in parallel, we exploit TCP’s habit to fill buffers to find the least congested path. We show that our algorithm significantly improves flow completion time without the need for a central controller or specialized hardware.

Rating Aggregation in Multi-Dimensional Rating Systems: How Do Reviewers Form Overall Ratings? - Gutt, Dominik; Kundisch, Dennis (INFORMS Annual Meeting)

Quantitative Evaluation of Model-Driven Performance Analysis and Simulation of Component-based Architectures - Brosig, Fabian; Meier, Philipp; Becker, Steffen; Koziolek, Anne; Koziolek, Heiko; Kounev, Samuel (Transactions on Software Engineering)
During the last decade, researchers have proposed a number of model transformations enabling performance predictions. These transformations map performance-annotated software architecture models into stochastic models solved by analytical means or by simulation. However, so far, a detailed quantitative evaluation of the accuracy and efﬁciency of different transformations is missing, making it hard to select an adequate transformation for a given context. This paper provides an in-depth comparison and quantitative evaluation of representative model transformations to, e.g., Queueing Petri Nets and Layered Queueing Networks. The semantic gaps between typical source model abstractions and the different analysis techniques are revealed. The accuracy and efﬁciency of each transformation are evaluated by considering four case studies representing systems of different size and complexity. The presented results and insights gained from the evaluation help software architects and performance engineers to select the appropriate transformation for a given context, thus signiﬁcantly improving the usability of model transformations for performance prediction.

Programs from Proofs of Predicated Dataflow Analyses - Jakobs, Marie-Christine; Wehrheim, Heike (Proceedings of the 30th Annual ACM Symposium on Applied Computing)
Programs from Proofs" is a generic method which generates new programs out of correctness proofs of given programs. The technique ensures that the new and given program are behaviorally equivalent and that the new program is easily verifiable, thus serving as an alternative to proof-carrying code concepts. So far, this generic method has one instantiation that verifies type-state properties of programs. In this paper, we present a whole range of new instantiations, all based on data ow analyses. More precisely, we show how an imprecise but fast data ow analysis can be enhanced with a predicate analysis as to yield a precise but expensive analysis. Out of the safety proofs of this analysis, we generate new programs, again behaviorally equivalent to the given ones, which are easily verifiable" in the sense that now the data ow analysis alone can yield precise results. An experimental evaluation practically supports our claim of easy verification.

Optimizing Water Tanks in Water Distribution Systems by combining Network Reduction, Mathematical Optimization and Hydraulic Simulation - Hallmann, Corinna; Suhl, Leena (OR Spectrum)
In the last two decades, water consumption in Germany has been decreasing, which causes the water tanks and pipes in water distribution systems to work inefficiently. This paper proposes a method that supports the planning process for tanks in water distribution systems. The method uses a combination of network reduction, mathematical optimization and hydraulic simulation. The mathematical optimization model is a non-convex Mixed Integer Quadratically Constrained Program (MIQCP) that is solved by a piecewise linearization. As this may lead to many binary variables and therefore high computing times, the size of the water distribution system model is reduced before building the optimization model. After applying several network reduction techniques and using a piecewise approximation of the original model, there may be some hydraulic differences between the original network model and the reduced network model. To make sure that the solution obtained in the optimization process is feasible in the original water distribution system model, the solution is verified by a hydraulic simulation. If the solution is not feasible, the reduced model has to be modified and solved again until the hydraulic simulation verifies a solution as feasible. In this paper, each of these processes is described and the results indicate the usefulness of each of them.

Online Resource Leasing - Markarian, Christine; Meyer auf der Heide, Friedhelm (Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC))
Many markets have seen a shift from the idea of buying and moved to leasing instead. Arguably, the latter has been the major catalyst for their success. Ten years ago, research realized this shift and initiated the study of "online leasing problems" by introducing leasing to online optimization problems. Resources required to provide a service in an "online leasing problem" are no more bought but leased for different durations. In this paper, we provide an overview of results that contribute to the understanding of "online resource leasing problems".

On-The-Fly Verification of Reconfigurable Image Processing Modules based on a Proof-Carrying Hardware Approach - Wiersema, Tobias; Wu, Sen; Platzner, Marco (Proceedings of the International Symposium in Reconfigurable Computing (ARC))
Proof-carrying hardware is an approach that has recently been proposed for the efficient verification of reconfigurable modules. We present an application of proof-carrying hardware to guarantee the correct functionality of dynamically reconfigured image processing modules. Our prototype comprises a reconfigurable-system-on-chip with an embedded virtual FPGA fabric. This setup allows us to leverage open source FPGA synthesis and backend tools to produce FPGA configuration bitstreams with an open format and, thus, to demonstrate and experimentally evaluate proof-carrying hardware at the bitstream level.

Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure - Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander (Transactions on Economics and Computation)
We consider structural and algorithmic questions related to the Nash dynamics of weighted congestion games. In weighted congestion games with linear latency functions, the existence of pure Nash equilibria is guaranteed by a potential function argument. Unfortunately, this proof of existence is inefficient and computing pure Nash equilibria in such games is a PLS-hard problem even when all players have unit weights. The situation gets worse when superlinear (e.g., quadratic) latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and pure Nash equilibria may not even exist. Given these obstacles, we consider approximate pure Nash equilibria as alternative solution concepts. A ρ--approximate pure Nash equilibrium is a state of a (weighted congestion) game from which no player has any incentive to deviate in order to improve her cost by a multiplicative factor higher than ρ. Do such equilibria exist for small values of ρ? And if so, can we compute them efficiently?We provide positive answers to both questions for weighted congestion games with polynomial latency functions by exploiting an “approximation” of such games by a new class of potential games that we call Ψ-games. This allows us to show that these games have d!-approximate pure Nash equilibria, where d is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate pure Nash equilibria when d is a constant. For games with linear latency functions, the approximation guarantee is 3+√5/2 + Oγ for arbitrarily small γ > 0; for latency functions with maximum degree d≥ 2, it is d2d+o(d). The running time is polynomial in the number of bits in the representation of the game and 1/γ. As a byproduct of our techniques, we also show the following interesting structural statement for weighted congestion games with polynomial latency functions of maximum degree d ≥ 2: polynomially-long sequences of best-response moves from any initial state to a dO(d2)-approximate pure Nash equilibrium exist and can be efficiently identified in such games as long as d is a constant.To the best of our knowledge, these are the first positive algorithmic results for approximate pure Nash equilibria in weighted congestion games. Our techniques significantly extend our recent work on unweighted congestion games through the use of Ψ-games. The concept of approximating nonpotential games by potential ones is interesting in itself and might have further applications.

Anonymous and Publicly Linkable Reputation Systems - Blömer, Johannes; Juhnke, Jakob; Kolb, Christina (Proceedings of the 18th International Conference on Financial Cryptography and Data Security (FC))
Reputation systems are used to compute and publish reputation scores for services or products. We consider reputation systems where users are allowed to rate products that they purchased previously. To obtain trustworthy reputations, they are allowed to rate these products only once. As long as users rate products once, they stay anonymous. Everybody is able to detect users deviating from the rate-products-only-once policy and the anonymity of such dishonest users can be revoked by a system manager. In this paper we present formal models for such reputation systems and their security. Based on group signatures presented by Boneh, Boyen, and Shacham we design an efficient reputation system that meets all our requirements.

An approach towards adaptive service composition in markets of composed services - Jungmann, Alexander; Mohr, Felix (Journal of Internet Services and Applications)
On-the-fly composition of service-based software solutions is still a challenging task. Even more challenges emerge when facing automatic service composition in markets of composed services for end users. In this paper, we focus on the functional discrepancy between “what a user wants” specified in terms of a request and “what a user gets” when executing a composed service. To meet the challenge of functional discrepancy, we propose the combination of existing symbolic composition approaches with machine learning techniques. We developed a learning recommendation system that expands the capabilities of existing composition algorithms to facilitate adaptivity and consequently reduces functional discrepancy. As a representative of symbolic techniques, an Artificial Intelligence planning based approach produces solutions that are correct with respect to formal specifications. Our learning recommendation system supports the symbolic approach in decision-making. Reinforcement Learning techniques enable the recommendation system to adjust its recommendation strategy over time based on user ratings. We implemented the proposed functionality in terms of a prototypical composition framework. Preliminary results from experiments conducted in the image processing domain illustrate the benefit of combining both complementary techniques.

A Metric for Functional Reusability of Services - Mohr, Felix (Proceedings of the 14th International Conference on Software Reuse (ICSR))
Services are self-contained software components that can beused platform independent and that aim at maximizing software reuse. Abasic concern in service oriented architectures is to measure the reusabilityof services. One of the most important qualities is the functionalreusability, which indicates how relevant the task is that a service solves.Current metrics for functional reusability of software, however, have verylittle explanatory power and do not accomplish this goal.This paper presents a new approach to estimate the functional reusabilityof services based on their relevance. To this end, it denes the degreeto which a service enables the execution of other services as its contri-bution. Based on the contribution, relevance of services is dened as anestimation for their functional reusability. Explanatory power is obtainedby normalizing relevance values with a reference service. The applicationof the metric to a service test set conrms its supposed capabilities.

A deterministic worst-case message complexity optimal solution for resource discovery - Kniesburges, Sebastian; Koutsopoulos, Andreas; Scheideler, Christian (Theoretical Computer Science)
We consider the problem of resource discovery in distributed systems. In particular we give an algorithm, such that each node in a network discovers the address of any other node in the network. We model the knowledge of the nodes as a virtual overlay network given by a directed graph such that complete knowledge of all nodes corresponds to a complete graph in the overlay network. Although there are several solutions for resource discovery, our solution is the first that achieves worst-case optimal work for each node, i.e. the number of addresses (O(n)O(n)) or bits (O(nlog⁡n)O(nlog⁡n)) a node receives or sends coincides with the lower bound, while ensuring only a linear runtime (O(n)O(n)) on the number of rounds.

Learning Boolean Specifications - Bubeck, Uwe; Kleine Büning, Hans (Artificial Intelligence)
In this paper we consider an extended variant of query learning where the hidden concept is embedded in some Boolean circuit. This additional processing layer modifies query arguments and answers by fixed transformation functions which are known to the learner. For this scenario, we provide a characterization of the solution space and an ordering on it. We give a compact representation of the minimal and maximal solutions as quantified Boolean formulas and we adapt the original algorithms for exact learning of specific classes of propositional formulas.
Keywords: Query learning; Propositional logic

How do reviews from professional critics interact with other signals of product quality? Evidence from the video game industry - Cox, Joe; Kaimann, Daniel (Journal of Consumer Behaviour)
Experience goods are characterised by information asymmetry and a lack of ex ante knowledge of product quality, such that reliable external signals of quality are likely to be highly valued. Two potentially credible sources of such information are reviews from professional critics and ‘word of mouth’ from other consumers. This paper makes a direct comparison between the relative influences and interactions of reviews from both of these sources on the sales performance of video game software. In order to empirically estimate and separate the effects of the two signals, we analyze a sample of 1480 video games and their sales figures between 2004 and 2010. We find evidence to suggest that even after taking steps to control for endogeneity, reviews from professional critics have a significantly positive influence on sales which outweighs that from consumer reviews. We also find evidence to suggest that reviews from professional critics also interact significantly with other signals of product quality. Consequently, we contend that professional critics adopt the role of an influencer, whereas word-of-mouth opinion acts more as a predictor of sales in the market for video games.

How do Different Sources of the Variance of Consumer Ratings Matter? - Herrmann, Philipp; Kundisch, Dennis; Zimmermann, Steffen; Nault, Barry (Proceedings of the 36th International Conference on Information Systems (ICIS), Fort Worth)
We examine the effect of the variance of consumer ratings on product pricing and sales using an analytical model, which considers goods that are characterized by experience attributes and informed search attributes (i.e., experience attributes that were transformed in search attributes by consumer ratings). For pure informed search goods, equilibrium price increases and demand decreases in variance. For pure experience goods, equilibrium price and demand decrease in variance. For hybrid goods with low total variance, equilibrium price and demand increase with an increasing relative share of variance caused by informed search attributes when the average rating and total variance of ratings are held constant. Hence, risk-averse consumers may prefer a more expensive good with a higher variance of ratings out of two similar goods with the same average rating. Moreover, our analytical model provides a theoretical foundation for the empirically observed j-shaped distribution of consumer ratings in electronic commerce.

Grammar-based model transformations: Definition, execution, and quality properties - Besova, Galina; Steenken, Dominik; Wehrheim, Heike (Computer Languages, Systems & Structures)
Model transformation is a key concept in model-driven software engineering. The definition of model transformations is usually based on meta-models describing the abstract syntax of languages. While meta-models are thereby able to abstract from uperfluous details of concrete syntax, they often loose structural information inherent in languages, like information on model elements always occurring together in particular shapes. As a consequence, model transformations cannot naturally re-use language structures, thus leading to unnecessary complexity in their development as well as in quality assurance.In this paper, we propose a new approach to model transformation development which allows to simplify the developed transformations and improve their quality via the exploitation of the languages׳ structures. The approach is based on context-free graph grammars and transformations defined by pairing productions of source and target grammars. We show that such transformations have important properties: they terminate and are sound, complete, and deterministic.

Filtering Reviews by Random Individual Error - Geierhos, Michaela; Bäumer, Frederik Simon; Schulze, Sabine; Stuß, Valentina (Proceedings of the 28th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE 2015))
Opinion mining from physician rating websites depends on the quality of the extracted information. Sometimes reviews are user-error prone and the assigned stars or grades contradict the associated content. We therefore aim at detecting random individual error within reviews. Such errors comprise the disagreement in polarity of review texts and the respective ratings. The challenges that thereby arise are (1) the content and sentiment analysis of the review texts and (2) the removal of the random individual errors contained therein. To solve these tasks, we assign polarities to automatically recognized opinion phrases in reviews and then check for divergence in rating and text polarity. The novelty of our approach is that we improve user-generated data quality by excluding error-prone reviews on German physician websites from average ratings.

Comprehensive Service Matching with MatchBox - Börding, Paul; Bruns, Melanie; Platenius, Marie Christin (10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE'15))
Nowadays, many service providers offer software components in the form of Software as a Service. Requesters that want to discover those services in order to use or to integrate them, need to find out which service satisfies their requirements best. For this purpose, service matching approaches determine how well the specifications of provided services satisfy their requirements (including structural, behavioral, and non-functional requirements). In this paper, we describe the tool-suite MatchBox that allows the integration of existing service matchers and their combination as part of flexibly configurable matching processes. Taking requirements and service specifications as an input, MatchBox is able to execute such matching processes and deliver rich matching results. In contrast to related tools, MatchBox allows users to take into account many different kinds of requirements, while it also provides the flexibility to control the matching process in many different ways.

Competition and Product Innovation of Intermediaries in a Differentiated Duopoly - Brangewitz, Sonja; Manegold, Jochen
On an intermediate goods market we allow for vertical and horizontal product differentiation and analyze the influence of simultaneous competition for resources and customers on the market outcome. Asymmetries between intermediaries cannot arise just from distinct product qualities, but also from different production technologies. The intermediaries face either price or quantity competition on the output market and a monopolistic input supplier on the input market. We find that there exist quality and productivity differences such that for quantity competition only one intermediary is willing to procure inputs from the input supplier, while for price competition both intermediaries are willing to purchase inputs. Considering product innovation for symmetric productivities we derive equilibrium conditions on the investment costs and compare price and quantity competition. It turns out that on the one hand there exist product qualities and degrees of horizontal product differentiation for complements such that asymmetric investment equilibria fail to exist. On the other hand we find that there also exist product qualities and degrees of horizontal product differentiation for substitutes such that existence can be guaranteed if the investment costs are chosen accordingly.

Combining Service-oriented Computing with Embedded Systems - A Robotics Case Study - Jungmann, Alexander; Jatzkowski, Jan; Kleinjohann, Bernd (Proceedings of the 5th IFIP International Embedded Systems Symposium)
In this paper, we introduce an approach for combining embedded systems with Service-oriented Computing techniques based on a concrete application scenario from the robotics domain. Our proposed Service-oriented Architecture allows for incorporating computational expensive functionality as services into a distributed computing environment. Furthermore, our framework facilitates a seamless integration of embedded systems such as robots as service providers into the computing environment. The entire communication is based on so-called recipes, which can be interpreted as autonomous messages that contain all necessary information for executing compositions of services.

Temporal plans for software architecture reconfiguration - Ziegert, Steffen; Wehrheim, Heike (Computer Science - R & D)

Automated Online Service Composition - Mohr, Felix; Jungmann, Alexander; Kleine Büning, Hans (Proceedings of the 12th IEEE International Conference on Services Computing (SCC))
Services are self-contained and platform independent software components that aim at maximizing software reuse. The automated composition of services to a target software artifact has been tackled with many AI techniques, but existing approaches make unreasonably strong assumptions such as a predefined data flow, are limited to tiny problem sizes, ignore non-functional properties, or assume offline service repositories. This paper presents an algorithm that automatically composes services without making such assumptions. We employ a backward search algorithm that starts from an empty composition and prepends service calls to already discovered candidates until a solution is found. Available services are determined during the search process. We implemented our algorithm, performed an experimental evaluation, and compared it to other approaches.

On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games - Drees, Maximilian; Feldotto, Matthias; Riechers, Sören; Skopalik, Alexander (Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT))
In bandwidth allocation games (BAGs), the strategy of a player consists of various demands on different resources. The player's utility is at most the sum of these demands, provided they are fully satisfied. Every resource has a limited capacity and if it is exceeded by the total demand, it has to be split between the players. Since these games generally do not have pure Nash equilibria, we consider approximate pure Nash equilibria, in which no player can improve her utility by more than some fixed factor $α$ through unilateral strategy changes. There is a threshold $α_δ$ (where $δ$ is a parameter that limits the demand of each player on a specific resource) such that $α$-approximate pure Nash equilibria always exist for $α ≥ α_δ$, but not for $α < α_δ$. We give both upper and lower bounds on this threshold $α_δ$ and show that the corresponding decision problem is ${\sf NP}$-hard. We also show that the $α$-approximate price of anarchy for BAGs is $α+1$. For a restricted version of the game, where demands of players only differ slightly from each other (e.g. symmetric games), we show that approximate Nash equilibria can be reached (and thus also be computed) in polynomial time using the best-response dynamic. Finally, we show that a broader class of utility-maximization games (which includes BAGs) converges quickly towards states whose social welfare is close to the optimum.

On Adaptivity for Automated Composition of Service Functionality - Jungmann, Alexander (Proceedings of the IEEE 11th World Congress on Services (SERVICES))
Automated service composition aims at automatically generating software solutions based on services to provide more complex functionality. In this paper, we give an initial overview about why adaptivity becomes increasingly important when aiming for automated composition of service functionality in dynamic and freely accessible environments such as service markets. We systematically derive dependencies among crucial processes such as service composition and service execution in a holistic view. Furthermore, we briefly discuss the influences and effects of changes in the environment according to the derived dependencies, and derive possible future research directions.

Non-preemptive Scheduling on Machines with Setup Times - Mäcker, Alexander; Malatyali, Manuel; Meyer auf der Heide, Friedhelm; Riechers, Sören (Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings)
Consider the problem in which n jobs that are classified into k types are to be scheduled on m identical machines without preemption. A machine requires a proper setup taking s time units before processing jobs of a given type. The objective is to minimize the makespan of the resulting schedule. We design and analyze an approximation algorithm that runs in time polynomial in n,m and k and computes a solution with an approximation factor that can be made arbitrarily close to 3/2.

Network Creation Games: Think Global - Act Local - Cord-Landwehr, Andreas; Lenzner, Pascal (Proceedings of the 40th Conference on Mathematical Foundations of Computer Science (MFCS))
We investigate a non-cooperative game-theoretic model for the formation of communication networks by selfish agents. Each agent aims for a central position at minimum cost for creating edges. In particular, the general model (Fabrikant et al., PODC'03) became popular for studying the structure of the Internet or social networks. Despite its significance, locality in this game was first studied only recently (Bilò et al., SPAA'14), where a worst case locality model was presented, which came with a high efficiency loss in terms of quality of equilibria. Our main contribution is a new and more optimistic view on locality: agents are limited in their knowledge and actions to their local view ranges, but can probe different strategies and finally choose the best. We study the influence of our locality notion on the hardness of computing best responses, convergence to equilibria, and quality of equilibria. Moreover, we compare the strength of local versus non-local strategy changes. Our results address the gap between the original model and the worst case locality variant. On the bright side, our efficiency results are in line with observations from the original model, yet we have a non-constant lower bound on the Price of Anarchy.

MatchBox: A Framework for Dynamic Configuration of Service Matching Processes - Platenius, Marie Christin; Arifulina, Svetlana; Schäfer, Wilhelm (Proceedings of the 18th International ACM Sigsoft Symposium on Component-Based Software Engineering (CBSE'15))
Service discovery in global software markets is performed by brokers who act as intermediaries between service consumers and service providers.In order to discover services, brokers apply service matching for determining whether the specification of a provided service satisfies the consumer's requirements.Brokers can already choose between a lot of different service matching approaches considering different service properties (structural, behavioral, and non-functional properties).Different matching approaches can be combined into configurable matching processes leading to a high matching quality (e.g., accurate matching results). However, this combination and configuration is a manual procedure and has to be repeated for different consumers' or market requirements regarding matching quality. In this paper, we propose our framework MatchBox, which supports a broker in reusing existing matching approaches and combining them in a model-driven way based on a reconfigurable model of the matching process.Using this reconfigurable model, MatchBox takes care of control and data flow between matching approaches and executes the modeled processes automatically.As a case study, we integrated eleven matchers into MatchBox to demonstrate that it remains flexibility and reduces effort for a broker at the same time.

Self-Aware and Self-Expressive Systems – Guest Editor's Introduction - Torresen, Jim; Plessl, Christian; Yao, Xin (IEEE Computer)
Keywords: self-awareness; self-expression

Towards Vandalism Detection in Knowledge Bases: Corpus Construction and Analysis - Heindorf, Stefan; Potthast, Martin; Stein, Benno; Engels, Gregor (Proceedings of the 38th International ACM Conference on Research and Development in Information Retrieval (SIGIR 15))
We report on the construction of the Wikidata Vandalism Corpus WDVC-2015, the first corpus for vandalism in knowledge bases. Our corpus is based on the entire revision history of Wikidata, the knowledge base underlying Wikipedia. Among Wikidata's 24 million manual revisions, we have identified more than 100,000 cases of vandalism. An in-depth corpus analysis lays the groundwork for research and development on automatic vandalism detection in public knowledge bases. Our analysis shows that 58% of the vandalism revisions can be found in the textual portions of Wikidata, and the remainder in structural content, e.g., subject-predicate-object triples. Moreover, we find that some vandals also target Wikidata content whose manipulation may impact content displayed on Wikipedia, revealing potential vulnerabilities. Given today's importance of knowledge bases for information systems, this shows that public knowledge bases must be used with caution.

Towards Flexible Demands in Online Leasing Problems - Li, Shouwei; Mäcker, Alexander; Markarian, Christine; Meyer auf der Heide, Friedhelm; Riechers, Sören (Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON))
We consider online leasing problems in which demands arrive over time and need to be served by leasing resources. We introduce a new model for these problems such that a resource can be leased for K different durations each incurring a different cost (longer leases cost less per time unit). Each demand i can be served anytime between its arrival ai and its deadline ai+di by a leased resource. The objective is to meet all deadlines while minimizing the total leasing costs. This model is a natural generalization of Meyerson’s ParkingPermitProblem (FOCS 2005) in which di=0 for all i. We propose an online algorithm that is Θ(K+dmaxlmin)-competitive where dmax and lmin denote the largest di and the shortest available lease length, respectively. We also extend the SetCoverLeasing problem by deadlines and give a competitive online algorithm which also improves on existing solutions for the original SetCoverLeasing problem.

“…and they are really lying”: Clean Evidence on the Pervasiveness of Cheating in Professional Contexts from a Field Experiment. - Fahr, Rene; Mir Djawadi, Behnud (Journal of Economic Psychology)
We investigate the pervasiveness of lying in professional contexts such as insurance fraud, tax evasion and untrue job applications. We argue that lying in professional contexts share three characterizing features: (1) the gain from the dishonest behavior is uncertain, (2) the harm that lying may cause to the other party is only indirect and (3) lies are more indirect lies by action or written statements. Conducted as a field experiment with a heterogenous group of participants during a University ‘‘Open House Day’’, our ‘‘gumball-machineexperiment’’ provides field evidence on how preferences for lying are shaped in situations typically found in professional contexts which we consider to be particularly prone to lying behavior compared to other contexts. As a key innovation, our experimental design allows measuring exact levels of cheating behavior under anonymous conditions. We find clean evidence that cheating is prevalent across all sub groups and that more than 32% of the population cheats for their own gain. However, an analysis of the cheating rates with respect to highest educational degree and professional status reveals that students cheat more than non-students. This finding warrants a careful interpretation of generalizing laboratory findings with student subjects about the prevalence of cheating in the population.

Why Fit Leads to Surprise: An Extension of Cognitive Fit Theory to Creative Problems - John, Thomas; Kundisch, Dennis (Proceedings of the 36th International Conference on Information Systems (ICIS), Fort Worth, USA)
Cognitive fit theory (CFT) provides guidance for how best to represent information that is relevant for solving a given problem. CFT is widely established in information systems research and its validity has been demonstrated in a great variety of contexts. However, of the two major types of problems that exist (i.e., routine and creative problems) prior CFT research has addressed only one: routine problems. Creative problems, despite their importance, have been left unaddressed. Therefore, based on the visual sketching model of problem solving, we propose an extension of CFT and thereby demonstrate that cognitive fit can promote problem solving performance also for creative problems. In doing so, we extend the boundary of CFT and add to creativity research a previously unknown cognitive mechanism for promoting creative performance: cognitive fit. Moreover, we contribute to general problem solving research by bridging the gap between problem solving in creativity and information systems research.

What did you mean? Facing the Challenges of User-generated Software Requirements - Geierhos, Michaela; Schulze, Sabine; Bäumer, Frederik Simon (Proceedings of the 7th International Conference on Agents and Artificial Intelligence (ICAART), Special Session on Partiality, Underspecification, and Natural Language Processing (PUaNLP 2015))
Existing approaches towards service composition demand requirements of the customers in terms of service templates, service query profiles, or partial process models. However, addressed non-expert customers may be unable to fill-in the slots of service templates as requested or to describe, for example, pre- and postconditions, or even have difficulties in formalizing their requirements. Thus, our idea is to provide non-experts with suggestions how to complete or clarify their requirement descriptions written in natural language. Two main issues have to be tackled: (1) partial or full inability (incapacity) of non-experts to specify their requirements correctly in formal and precise ways, and (2) problems in text analysis due to fuzziness in natural language. We present ideas how to face these challenges by means of requirement disambiguation and completion. Therefore, we conduct ontology-based requirement extraction and similarity retrieval based on requirement descriptions that are gathered from App marketplaces. The innovative aspect of our work is that we support users without expert knowledge in writing their requirements by simultaneously resolving ambiguity, vagueness, and underspecification in natural language.

Weighted Boolean Formula Games - Monien, Burkhard; Mavronicolas, Marios; Wagner, Klaus (the ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday)
We introduce weighted boolean formula games (WBFG) as a new class of succinct games. Each player has a set of boolean formulas she wants to get satisfied; the formulas involve a ground set of boolean variables each of which is controlled by some player. The payoff of a player is a weighted sum of the values of her formulas. We consider both pure equilibria and their refinement of payoff-dominant equilibria [34], where every player is no worse-off than in any other pure equilibrium. We present both structural and complexity results:We consider mutual weighted boolean formula games (MWBFG), a subclass of WBFG making a natural mutuality assumption on the formulas of players. We present a very simple exact potential for MWBFG. We establish a polynomial monomorphism from certain classes of weighted congestion games to subclasses of WBFG and MWBFG, respectively, indicating their rich structure.We present a collection of complexity results about decision (and search) problems for both pure and payoff-dominant equilibria in WBFG. The precise complexities depend crucially on five parameters: (i) the number of players; (ii) the number of variables per player; (iii) the number of formulas per player; (iv) the weights in the payoff functions (whether identical or not), and (v) the syntax of the formulas. These results imply that, unless the polynomial hierarchy collapses, decision (and search) problems for payoff-dominant equilibria are harde than for pure equilibria.

Voronoi Cells of Lattices with Respect to Arbitrary Norms - Blömer, Johannes; Kohn, Kathlén
Motivated by the deterministic single exponential time algorithm of Micciancio and Voulgaris for solving the shortest and closest vector problem for the Euclidean norm, we study the geometry and complexity of Voronoi cells of lattices with respect to arbitrary norms.On the positive side, we show that for strictly convex and smooth norms the geometry of Voronoi cells of lattices in any dimension is similar to the Euclidean case, i.e., the Voronoi cells are defined by the so-called Voronoi-relevant vectors and the facets of a Voronoi cell are in one-to-one correspondence with these vectors. On the negative side, we show that combinatorially Voronoi cells for arbitrary strictly convex and smooth norms are much more complicated than in the Euclidean case.In particular, we construct a family of three-dimensional lattices whose number of Voronoi-relevant vectors with respect to the l_3-norm is unbounded.Since the algorithm of Micciancio and Voulgaris and its run time analysis crucially dependonthefactthatfortheEuclidean normthenumber of Voronoi-relevant vectors is single exponential in the lattice dimension, this indicates that the techniques of Micciancio and Voulgaris cannot be extended to achieve deterministic single exponential time algorithms for lattice problems with respect to arbitrary l_p-norms.

Fast Fuzzy Pattern Tree Learning for Classification - Senge, Robin; Hüllermeier, Eyke (IEEE Transactions on Fuzzy Systems)

Robust Equilibria in Location Games - Buechel, Berno; Röhl, Nils (European Journal of Operational Research)
In the framework of spatial competition, two or more players strategically choose a locationin order to attract consumers. It is assumed standardly that consumers with the same favorite location fully agree on the ranking of all possible locations. To investigate the necessity of this questionable and restrictive assumption, we model heterogeneity in consumers’ distance perceptions by individual edge lengths of a given graph. A proﬁle of location choices is called a “robust equilibrium” if it is a Nash equilibrium in several games which diﬀer only by the consumers’ perceptions of distances. For a ﬁnite number of players and any distribution of consumers, we provide a full characterization of all robust equilibria and derive structural conditions for their existence. Furthermore, we discuss whether the classical observations of minimal diﬀerentiation and ineﬃciency are robust phenomena. Thereby, we ﬁnd strong support for an old conjecture that in equilibrium ﬁrms form local clusters.

Topology model to generate realistic latency for simulations - Schwabe, Arne; Karl, Holger (2015 IEEE International Conference on Communications, ICC 2015, London, United Kingdom, June 8-12, 2015)

An Architecture for Energy-aware On-demand Mobile Network Management - Peuster, Manuel; Karl, Holger (Proceedings of the 5th Workshop on All Things Cellular: Operations, Applications and Challenges)
The increasing amount of mobile traffic leads to a significantly higher energy consumption of mobile networks that is mainly caused by the high number of required base stations. One recent solution for this is based on a two-layered network that uses long-range macro cells to provide a full coverage signaling overlay and short-range small cells for fast data transmissions. These small cells can be switched off when they are not needed and allow network-wide energy optimizations. This paper presents an architecture that extends existing mobile networks to integrate a small cell layer that supports on-demand cell activation. We discuss how additional small cells can be interconnected with existing core components and how they can be controlled by a resource management component. Finally, a Wi-Fi based proof of concept testbed implementation is presented that demonstrates the feasibility of the approach.

Minimizing Expectation Plus Variance - Monien, Burkhard; Mavronicolas, Marios (Theory of Computing Systems)
We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (mapping probability distributions to reals); such valuations are used to model risk. In contrast to games with expectation-optimizer players where mixed equilibria always exist (Nash 1950; Nash Ann. Math. 54, 286–295, 1951), a mixed equilibrium for such games, called a V-equilibrium, may fail to exist, even though pure equilibria (if any) transfer over. What is the exact impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question in the context of expectation plus variance, a particular concave valuation denoted as RA, which stands for risk-averse; so, variance enters as a measure of risk and it is used as an additive adjustment to expectation. We obtain the following results about RA-equilibria:A collection of general structural properties of RA-equilibria connecting to (i) E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable properties such as Weak Equilibrium and Strong Equilibrium. Some of these structural properties imply quantitative constraints on the existence of mixed RA-equilibria.A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. We provide suitable examples with a mixed RA-equilibrium that is not an E-equilibrium and vice versa.A purification technique to transform a player-specific scheduling game on two identical links into a player-specific scheduling game on two links so that all non-pure RA-equilibria are eliminated while no new pure equilibria are created; so, a particular player-specific scheduling game on two identical links with no pure equilibrium yields a player-specific scheduling game with no RA-equilibrium (whether mixed or pure). As a by-product, the first PLS-completeness result for the computation of RA-equilibria follows.

IccTA: Detecting Inter-Component Privacy Leaks in Android Apps - Li, Li; Bartel, Alexandre; Bissyande, Tegawende F.; Klein, Jacques; Le Traon, Yves; Arzt, Steven; Rasthofer, Siegfried; Bodden, Eric; Octeau, Damien; McDaniel, Patrick (2015 International Conference on Software Engineering (ICSE))
Keywords: CROSSING; ATTRACT; ITSECWEBSITE

Different Sources of the Variance of Online Consumer Ratings and their Impact on Price and Demand - Herrmann, Philipp; Kundisch, Dennis; Zimmermann, Steffen; Nault, Barry

Exploring Tradeoffs between Specialized Kernels and a Reusable Overlay in a Stereo-Matching Case Study - Kenter, Tobias; Schmitz, Henning; Plessl, Christian (International Journal of Reconfigurable Computing (IJRC))
FPGAs are known to permit huge gains in performance and efficiency for suitable applications but still require reduced design efforts and shorter development cycles for wider adoption. In this work, we compare the resulting performance of two design concepts that in different ways promise such increased productivity. As common starting point, we employ a kernel-centric design approach, where computational hotspots in an application are identified and individually accelerated on FPGA. By means of a complex stereo matching application, we evaluate two fundamentally different design philosophies and approaches for implementing the required kernels on FPGAs. In the first implementation approach, we designed individually specialized data flow kernels in a spatial programming language for a Maxeler FPGA platform; in the alternative design approach, we target a vector coprocessor with large vector lengths, which is implemented as a form of programmable overlay on the application FPGAs of a Convey HC-1. We assess both approaches in terms of overall system performance, raw kernel performance, and performance relative to invested resources. After compensating for the effects of the underlying hardware platforms, the specialized dataflow kernels on the Maxeler platform are around 3x faster than kernels executing on the Convey vector coprocessor. In our concrete scenario, due to trade-offs between reconfiguration overheads and exposed parallelism, the advantage of specialized dataflow kernels is reduced to around 2.5x.

Easy-to-Use On-The-Fly Binary Program Acceleration on Many-Cores - Damschen, Marvin; Plessl, Christian (Proceedings of the 5th International Workshop on Adaptive Self-tuning Computing Systems (ADAPT))
This paper introduces Binary Acceleration At Runtime(BAAR), an easy-to-use on-the-fly binary acceleration mechanismwhich aims to tackle the problem of enabling existentsoftware to automatically utilize accelerators at runtime. BAARis based on the LLVM Compiler Infrastructure and has aclient-server architecture. The client runs the program to beaccelerated in an environment which allows program analysisand profiling. Program parts which are identified as suitable forthe available accelerator are exported and sent to the server.The server optimizes these program parts for the acceleratorand provides RPC execution for the client. The client transformsits program to utilize accelerated execution on the server foroffloaded program parts. We evaluate our work with a proofof-concept implementation of BAAR that uses an Intel XeonPhi 5110P as the acceleration target and performs automaticoffloading, parallelization and vectorization of suitable programparts. The practicality of BAAR for real-world examples is shownbased on a study of stencil codes. Our results show a speedup ofup to 4 without any developer-provided hints and 5.77 withhints over the same code compiled with the Intel Compiler atoptimization level O2 and running on an Intel Xeon E5-2670machine. Based on our insights gained during implementationand evaluation we outline future directions of research, e.g.,offloading more fine-granular program parts than functions, amore sophisticated communication mechanism or introducing onstack-replacement.

Transparent offloading of computational hotspots from binary code to Xeon Phi - Damschen, Marvin; Riebler, Heinrich; Vaz, Gavin Francis; Plessl, Christian (Proceedings of the 2015 Conference on Design, Automation and Test in Europe (DATE))
In this paper, we study how binary applications can be transparently accelerated with novel heterogeneous computing resources without requiring any manual porting or developer-provided hints. Our work is based on Binary Acceleration At Runtime (BAAR), our previously introduced binary acceleration mechanism that uses the LLVM Compiler Infrastructure. BAAR is designed as a client-server architecture. The client runs the program to be accelerated in an environment, which allows program analysis and profiling and identifies and extracts suitable program parts to be offloaded. The server compiles and optimizes these offloaded program parts for the accelerator and offers access to these functions to the client with a remote procedure call (RPC) interface. Our previous work proved the feasibility of our approach, but also showed that communication time and overheads limit the granularity of functions that can be meaningfully offloaded. In this work, we motivate the importance of a lightweight, high-performance communication between server and client and present a communication mechanism based on the Message Passing Interface (MPI). We evaluate our approach by using an Intel Xeon Phi 5110P as the acceleration target and show that the communication overhead can be reduced from 40% to 10%, thus enabling even small hotspots to benefit from offloading to an accelerator.

Competitive outcomes and the inner core of NTU market games - Brangewitz, Sonja; Gamp, Jan-Philip (Economic Theory)

MaxiNet: Distributed Emulation of Software-Defined Networks - Wette, Philip; Dräxler, Martin; Schwabe, Arne; Wallaschek, Felix; Zahraee, Mohammad Hassan; Karl, Holger (Proceedings of the 2014 IFIP Networking Conference (Networking 2014))
Network emulations are widely used for testing novel network protocols and routing algorithms in realistic scenarios. Up to now, there is no emulation tool that is able to emulate large software-deﬁned data center networks that consist of several thousand nodes. Mininet is the most common tool to emulate Software-Deﬁned Networks of several hundred nodes. We extend Mininet to span an emulated network over several physical machines, making it possible to emulate networks of several thousand nodes on just a handful of physical machines. This enables us to emulate, e.g., large data center networks. To test this approach, we additionally introduce a trafﬁc generator for data center trafﬁc. Since there are no data center trafﬁc traces publicly available we use the results of two recent trafﬁc studies to create synthetic trafﬁc. We show the design and discuss some challenges we had in building our trafﬁc generator. As a showcase for our work we emulated a data center consisting of 3200 hosts on a cluster of only 12 physical machines. We show the resulting workloads and the trade-offs involved.

Verified Service Compositions by Template-Based Construction - Walther, Sven; Wehrheim, Heike (Proceedings of the 11th International Symposium on Formal Aspects of Component Software (FACS))
Today, service compositions often need to be assembled or changed on-the-fly, which leaves only little time for quality assurance. Moreover, quality assurance is complicated by service providers only giving information on their services in terms of domain specific concepts with only limited semantic meaning. In this paper, we propose a method to construct service compositions based on pre-verifiedtemplates. Templates, given as workflow descriptions, are typed over a (domain-independent) template ontology defining concepts and predicates. Templates are proven correct using an abstract semantics, leaving the specific meaning of ontology concepts open, however, only up to given ontology rules. Construction of service compositions amounts to instantiation of templates with domain-specific services.Correctness of an instantiation can then simply be checked by verifying that the domain ontology(a) adheres to the rules of the template ontology, and (b) fulfills the constraints of the employed template.

Using Application Layer Knowledge in Routing and Wavelength Assignment Algorithms - Wette, Philip; Karl, Holger (Proceedings of the IEEE International Conference on Communications 2014)
Preemptive Routing and Wavelength Assignment (RWA) algorithms preempt established lightpaths in case notenough resources are available to set up a new lightpath in aWavelength Division Multiplexing (WDM) network. The selectionof lightpaths to be preempted relies on internal decisions of theRWA algorithm. Thus, if dedicated properties of the networktopology are required by the applications running on the network,these requirements have to be known to the RWA algorithm.We present a family of preemptive RWA algorithms for WDMnetworks. These algorithms have two distinguishing features: a)they can handle dynamic traffic by on-the-fly reconfiguration,and b) users can give feedback for reconfiguration decisions andthus influence the preemption decision of the RWA algorithm,leading to networks which adapt directly to application needs.This is different from traffic engineering where the network is(slowly) adapted to observed traffic patterns.Our algorithms handle various WDM network configurationsincluding networks consisting of heterogeneous WDM hardware.To this end, we are using the layered graph approach togetherwith a newly developed graph model that is used to determineconflicting lightpaths.

Towards Systematic Configuration for Architecture Validation - Becker, Matthias; Becker, Steffen; Besova, Galina; Walther, Sven; Wehrheim, Heike (Proceedings of the 40th Euromicro Conference on Software Engineering and Advanced Applications (Work in Progress Session))

Towards Context-Sensitive Service Composition for Service-Oriented Image Processing - Jungmann, Alexander; Kleinjohann, Bernd (Proceedings of the 6th International Conference on Cloud Computing Technology and Science (CloudCom))
Automatically composing service-based software solutions is a challenging task. Considering context information during this service composition process is even more challenging. In domains such as image processing, however, context-sensitivity is inherent and cannot be ignored when developing techniques for automatic service composition. Formal approaches tend to create ambiguous solutions, whenever the expressive power of the applied formalism is limited. For example, services may have the same formal specification, although their actual functionality depends on the concrete context. In order to satisfy individual user requests while providing data-dependent functionality, formal approaches have to be extended. We propose to incorporate Reinforcement Learning techniques and combine them with planning based composition approaches. While planning ensures formally correct solutions, learning enables the composition process to resolve ambiguity by implicitly considering context information. Preliminary results show that our combined approach adapts to a static context while still satisfying formally specified requirements.

Towards a Flexible and Privacy-Preserving Reputation System for Markets of Composed Services - Brangewitz, Sonja; Jungmann, Alexander; Petrlic, Ronald; Platenius, Marie Christin (Proceedings of the 6th International Conferences on Advanced Service Computing (SERVICE COMPUTATION))
One future goal of service-oriented computing is to realize global markets of composed services. On such markets, service providers offer services that can be flexibly combined with each other. However, most often, market participants are not able to individually estimate the quality of traded services in advance. As a consequence, even potentially profitable transactions between customers and providers might not take place. In the worst case, this can induce a market failure. To overcome this problem, we propose the incorporation of reputation information as an indicator for expected service quality. We address On-The-Fly Computing as a representative environment of markets of composed services. In this environment, customers provide feedback on transactions. We present a conceptual design of a reputation system which collects and processes user feedback, and provides it to participants in the market. Our contribution includes the identification of requirements for such a reputation system from a technical and an economic perspective. Based on these requirements, we propose a flexible solution that facilitates the incorporation of reputation information into markets of composed services while simultaneously preserving privacy of customers who provide feedback. The requirements we formulate in this paper have just been partially met in literature. An integrated approach, however, has not been addressed yet.

Thread Shadowing: Using Dynamic Redundancy on Hybrid Multi-cores for Error Detection - Meisner, Sebastian; Platzner, Marco (Proceedings of the 10th International Symposium on Applied Reconfigurable Computing (ARC))
Dynamic thread duplication is a known redundancy technique for multi-cores. The approach duplicates a thread under observation for some time period and compares the signatures of the two threads to detect errors. Hybrid multi-cores, typically implemented on platform FPGAs, enable the unique option of running the thread under observation and its copy in different modalities, i.e., software and hardware. We denote our dynamic redundancy technique on hybrid multi-cores as thread shadowing. In this paper we present the concept of thread shadowing and an implementation on a multi-threaded hybrid multi-core architecture. We report on experiments with a block-processing application and demonstrate the overheads, detection latencies and coverage for a range of thread shadowing modes. The results show that trans-modal thread shadowing, although bearing long detection latencies, offers attractive coverage at a low overhead.

The Legal Classification of Identity-Based Signatures - Sorge, Christoph
Identity-based cryptography has attracted attention in the cryptographic research communityin recent years. Despite the importance of cryptographic schemes for applicationsin business and law, the legal implications of identity-based cryptography have not yetbeen discussed. We investigate how identity-based signatures fit into the legal framework.We focus on the European Signature Directive, but also take the UNCITRAL Model Law onElectronic Signatures into account. In contrast to previous assumptions, identity-basedsignature schemes can, in principle, be used even for qualified electronic signatures,which can replace handwritten signatures in the member states of the European Union.We derive requirements to be taken into account in the development of future identitybasedsignature schemes.

The Interaction of Signals: A Fuzzy set Analysis of the Video Game Industry - Kaimann, Daniel; Cox, Joe
Customers continuously evaluate the credibility and reliability of a range of signals both separately and jointly. However, existing econometric studies pay insufficient attention to the interactions and complex combinations of these signals, and are typically limited as a result of difficulties controlling for multicollinearity and endogeneity in their data. We develop a novel theoretical approach to address these issues and study different signaling effects (i.e., word-of-mouth, brand reputation, and distribution strategy) on customer perceptions. Using data on the US video games market, we apply a fuzzy set qualitative comparative analysis (fsQCA) to account for cause-effect relationships. The results of our study address a number of key issues in the economics and management literature. First, our results support the contention that reviews from professional critics act as a signal of product quality and therefore positively influence unit sales, as do the discriminatory effects of prices and restricted age ratings. Second, we find evidence to support the use of brand extension strategies as marketing tools that create spillover effects and support the launch of new products.

Template-based Generation of Semantic Services - Mohr, Felix; Walther, Sven (Proceedings of the 14th International Conference on Software Reuse (ICSR))
There are many technologies for the automation of processesthat deal with services; examples are service discovery and composition.Automation of these processes requires that the services are described semantically. However, semantically described services are currently not oronly rarely available, which limits the applicability of discovery and composition approaches. The systematic support for creating new semanticservices usable by automated technologies is an open problem.We tackle this problem with a template based approach: Domain independent templates are instantiated with domain specific services andboolean expressions. The obtained services have semantic descriptionswhose correctness directly follows from the correctness of the template.Besides the theory, we present experimental results for a service repository in which 85% of the services were generated automatically.

Template Embedding: Using Application Architecture to Allocate Resources in Distributed Clouds - Keller, Matthias; Robbert, Christoph; Karl, Holger (Proceedings of 7th International Conference on Utility and Cloud Computing (UCC))
In distributed cloud computing, application deployment across multiple sites can improve quality of service. Recent research developed algorithms to find optimal locations for virtual machines. However, those algorithms assume to have either single-tier applications or a fixed number of virtual machines – a strong simplification of reality. This paper investigates the placement and scaling of complex application architectures. An application is dynamically scaled to fit both the current demand situation and the currently available infrastructure resources. We compare two approaches: The first one is based on virtual network embedding. The second approach is a novel method called Template Embedding. It is based on a hierarchical 1-allocation hub flow problem and combines applica- tion scaling and embedding in one step. Extensive experiments on 43200 network configurations showed that Template Embedding outperforms virtual network embedding in all cases in three metrics: success rate, solution quality, and runtime. This positive result shows that template embedding is a promising approach for distributed cloud resource allocation.

Tampering attacks in pairing-based cryptography - Blömer, Johannes; Günther, Peter; Liske, Gennadij (Proceedings of Fault Tolerance and Diagnosis in Cryptography(FDTC))
In the last decade pairings have become an important, and often indispensable, ingredient in the construction of identity-based and attribute-based cryptosystems, as well as group signatures and credential systems. Consequently, the applicability of timing, power, or fault attacks to implementations of pairings is an important research topic. We will review some of the known results in this area.

Surrounding robots -- A discrete localized solution for the intruder problem - Blazovics, Laszlo; Lukovszki, Tamas; Forstner, Bertalan (Journal of Advanced Computational Intelligence and Intelligent Informatics)
Decentralized algorithms are often used in the cooperative robotics field, especially by large swarm systems. We present a distributed algorithm for a problem in which a group of autonomous mobile robots must surround a given target. These robots are oblivious, i.e., they have no memory of the past. They use only local sensing and need no dedicated communication among themselves. We introduce, then solve the problem in which the group of autonomous mobile robots must surround a given target – we call it the “discrete multiorbit target surrounding problem” (DMTSP). We evaluate our solution using simulation and prove that our solution invariably ensures that robots enclose the target in finite time.

Specifying and Placing Chains of Virtual Network Functions - Dräxler, Sevil; Keller, Matthias; Karl, Holger (Proceedings of the 3rd International Conference on Cloud Networking (CloudNet))
Network appliances perform different functions on network flows and constitute an important part of an operator’s network. Normally, a set of chained network functions process network flows. Following the trend of virtualization of networks, virtualization of the network functions has also become a topic of interest. We define a model for formalizing the chaining of network functions using a context-free language. We process deployment requests and construct virtual network function graphs that can be mapped to the network. We describe the mapping as a Mixed Integer Quadratically Constrained Program (MIQCP) for finding the placement of the network functions and chaining them together considering the limited network resources and requirements of the functions. We have performed a Pareto set analysis to investigate the possible trade-offs between different optimization objectives.

SeSAME: Modeling and Analyzing High-Quality Service Compositions - Arifulina, Svetlana; Becker, Matthias; Platenius, Marie Christin; Walther, Sven (Proceedings of the 29th IEEE/ACM International Conference on Automated Software Engineering (ASE 2014))
Today, software components are traded on markets in form of services. These services can also be service compositions consisting of several services. If a software architect wants to provide such a service composition in the market for trade, she needs to perform several tasks: she needs to model the composition, to discover existing services to be part of that composition, and to analyze the composition's functional correctness as well as its quality, e.g., performance. Up to now, the architect needed to find and use different tools for these tasks. Typically, these tools are not interoperable with each other. We provide the tool SeSAME that supports a software architect in all of these tasks. SeSAME is an integrated Eclipse-based tool-suite providing a comprehensive service specification language to model service compositions and existing services. Furthermore, it includes modules for service matching, functional analysis, and non-functional analysis. SeSAME is the first tool that integrates all these tasks into one tool-suite and, thereby, provides holistic support for trading software services. Thus, it contributes to a software provider's market success.

Security and Privacy Challenges in On-The-Fly Computing - Petrlic, Ronald; Jungmann, Alexander; Platenius, Marie Christin; Schäfer, Wilhelm; Sorge, Christoph (Tagungsband der 4. Konferenz Software-Technologien und -Prozesse (STeP 2014))
On-The-Fly (OTF) Computing constitutes an approach towards highly dynamic and individualized software markets. Based on service-oriented computing, OTF Computing is about realizing global markets of services that can be flexibly combined. We report on our current research activities, the security and privacy implications thereof, and our approaches to tackle the challenges. Furthermore, we discuss how the security and privacy challenges are addressed in research projects similar to OTF Computing.

Secure Distributed Data Structures for Peer-to-Peer-based Social Networks - Janiuk, Jens; Mäcker, Alexander; Graffi, Kalman (Proceedings of the International Conference on Collaboration Technologies and Systems (CTS))
Online social networks are attracting billions of nowadays, both on a global scale as well as in social enterprise networks. Using distributed hash tables and peer-to-peer technology allows online social networks to be operated securely and efficiently only by using the resources of the user devices, thus alleviating censorship or data misuse by a single network operator. In this paper, we address the challenges that arise in implementing reliably and conveniently to use distributed data structures, such as lists or sets, in such a distributed hash-tablebased online social network. We present a secure, distributed list data structure that manages the list entries in several buckets in the distributed hash table. The list entries are authenticated, integrity is maintained and access control for single users and also groups is integrated. The approach for secure distributed lists is also applied for prefix trees and sets, and implemented and evaluated in a peer-to-peer framework for social networks. Evaluation shows that the distributed data structure is convenient and efficient to use and that the requirements on security hold.

Scheduling Shared Continuous Resources on Many-Cores - Brinkmann, Andre; Kling, Peter; Meyer auf der Heide, Friedhelm; Nagel, Lars; Riechers, Sören; Suess, Tim (Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA))
We consider the problem of scheduling a number of jobs on $m$ identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement r_j \in {0,1}. The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature.In this paper, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include an efficient optimal algorithm for 2 processors. Moreover, we prove that balanced schedules yield a 2-1/m-approximation for a fixed number of processors. Such schedules are computed by our GreedyBalance algorithm, for which the bound is tight.

Routing Games with Progressive Filling - Harks, Tobias; Höfer, Martin; Schewior, Kevin; Skopalik, Alexander (Proceedings of the 33rd Annual IEEE International Conference on Computer Communications (INFOCOM'14))
Max-min fairness (MMF) is a widely known approach to a fair allocation of bandwidth to each of the users in a network. This allocation can be computed by uniformly raising the bandwidths of all users without violating capacity constraints. We consider an extension of these allocations by raising the bandwidth with arbitrary and not necessarily uniform time-depending velocities (allocation rates). These allocations are used in a game-theoretic context for routing choices, which we formalize in progressive filling games (PFGs).We present a variety of results for equilibria in PFGs. We show that these games possess pure Nash and strong equilibria. While computation in general is NP-hard, there are polynomial-time algorithms for prominent classes of Max-Min-Fair Games (MMFG), including the case when all users have the same source-destination pair. We characterize prices of anarchy and stability for pure Nash and strong equilibria in PFGs and MMFGs when players have different or the same source-destination pairs. In addition, we show that when a designer can adjust allocation rates, it is possible to design games with optimal strong equilibria. Some initial results on polynomial-time algorithms in this direction are also derived.

RoBuSt: A Crash-Failure-Resistant Distributed Storage System - Scheideler, Christian; Setzer, Alexander; Eikel, Martina (Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS))
In this work we present the first distributed storage system that is provably robust against crash failures issued by an adaptive adversary, i.e., for each batch of requests the adversary can decide based on the entire system state which servers will be unavailable for that batch of requests. Despite up to \gamma n^{1/\log\log n} crashed servers, with \gamma>0 constant and n denoting the number of servers, our system can correctly process any batch of lookup and write requests (with at most a polylogarithmic number of requests issued at each non-crashed server) in at most a polylogarithmic number of communication rounds, with at most polylogarithmic time and work at each server and only a logarithmic storage overhead. Our system is based on previous work by Eikel and Scheideler (SPAA 2013), who presented IRIS, a distributed information system that is provably robust against the same kind of crash failures. However, IRIS is only able to serve lookup requests. Handling both lookup and write requests has turned out to require major changes in the design of IRIS.

Response Time-Optimized Distributed Cloud Resource Allocation - Keller, Matthias; Karl, Holger (Proceedings of the SIGCOMM workshop on Distributed cloud computing)
In the near future many more compute resources will be available at different geographical locations. To minimize the response time of requests, application servers closer to the user can hence be used to shorten network round trip times. However, this advantage is neutralized if the used data centre is highly loaded as the processing time of re- quests is important as well. We model the request response time as the network round trip time plus the processing time at a data centre.We present a capacitated facility location problem formal- ization where the processing time is modelled as the sojourn time of a queueing model. We discuss the Pareto trade-off between the number of used data centres and the resulting response time. For example, using fewer data centres could cut expenses but results in high utilization, high response time, and smaller revenues.Previous work presented a non-linear cost function. We prove its convexity and exploit this property in two ways: First, we transform the convex model into a linear model while controlling the maximum approximation error. Sec- ond, we used a convex solver instead of a slower non-linear solver. Numerical results on network topologies exemplify our work.

Relocatable Hardware Threads in Run-Time Reconfigurable Systems - Wold, Alexander; Agne, Andreas; Torresen, Jim (Proceedings of the 10th International Symposium on Reconfigurable Computing: Architectures, Tools, and Applications)
Run-time reconfiguration provides an opportunity to increase performance, reduce cost and improve energy efficiency in FPGA-based systems. However, run-time reconfigurable systems are more complex to implement than static only systems. This increases time to market, and introduces run-time overhead into the system. Our research aims to raise the abstraction level to develop run-time reconfigurable systems. We present operating system extensions which enable seamless integration of run-time reconfigurable hardware threads into applications. To improve resource utilization, the hardware threads are placed on a fine granularity tile grid. We take advantage of a relocatable module placer targeting modern FPGA to manage the reconfigurable area. The module placer accurately models the FPGA resources to compute feasible placement locations for the hardware threads at run-time. Finally, we evaluate our work by means of a case study that consists of a synthetic application to validate the functionality and performance of the implementation. The results show a reduction in reconfiguration time of up to 42% and more than double resource utilization.

Reengineering Component-Based Software Systems with Archimetrix - von Detten, Markus; Platenius, Marie Christin; Becker, Steffen (Journal of Software and Systems Modeling)
Many software development, planning, or analysis tasks require an up-to-date software architecture documentation. However, this documentation is often outdated, unavailable, or at least not available as a formal model which analysis tools could use. Reverse engineering methods try to fill this gap. However, as they process the system’s source code, they are easily misled by design deficiencies (e.g., violations of component encapsulation) which leaked into the code during the system’s evolution. Despite the high impact of design deficiencies on the quality of the resulting software architecture models, none of the surveyed related works is able to cope with them during the reverse engineering process. Therefore, we have developed the Archimetrix approach which semi-automatically recovers the system’s concrete architecture in a formal model while simultaneously detecting and removing design deficiencies. We have validated Archi metrix on a case-study system and two implementation variants of the CoCoME benchmark system. Results show that the removal of relevant design deficiencies leads to an architecture model which more closely matches the system’s conceptual architecture.

Re-Chord: A Self-stabilizing Chord Overlay Network - Kniesburges, Sebastian; Koutsopoulos, Andreas; Scheideler, Christian (Theory of Computing Systems)
The Chord peer-to-peer system is considered, together with CAN, Tapestry and Pastry, as one of the pioneering works on peer-to-peer distributed hash tables (DHT) that inspired a large volume of papers and projects on DHTs as well as peer-to-peer systems in general. Chord, in particular, has been studied thoroughly, and many variants of Chord have been presented that optimize various criteria. Also, several implementations of Chord are available on various platforms. Though Chord is known to be very efficient and scalable and it can handle churn quite well, no protocol is known yet that guarantees that Chord is self-stabilizing, i.e., the Chord network can be recovered from any initial state in which the network is still weakly connected. This is not too surprising since it is known that the Chord network is not locally checkable for its current topology. We present a slight extension of the Chord network, called Re-Chord (reactive Chord), that turns out to be locally checkable, and we present a self-stabilizing distributed protocol for it that can recover the Re-Chord network from any initial state, in which the n peers are weakly connected, in O(nlogn) communication rounds. We also show that our protocol allows a new peer to join or an old peer to leave an already stable Re-Chord network so that within O(logn)^2) communication rounds the Re-Chord network is stable again.

Randomized Online Algorithms for Set Cover Leasing Problems - Abshoff, Sebastian; Markarian, Christine; Meyer auf der Heide, Friedhelm (Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA))
In the leasing variant of Set Cover presented by Anthony et al.[1], elements U arrive over time and must be covered by sets from a familyF of subsets of U. Each set can be leased for K different periods of time.Let |U| = n and |F| = m. Leasing a set S for a period k incurs a cost ckS and allows S to cover its elements for the next lk time steps. The objectiveis to minimize the total cost of the sets leased, such that elements arrivingat any time t are covered by sets which contain them and are leased duringtime t. Anthony et al. [1] gave an optimal O(log n)-approximation forthe problem in the offline setting, unless P = NP [22]. In this paper, wegive randomized algorithms for variants of Set Cover Leasing in the onlinesetting, including a generalization of Online Set Cover with Repetitionspresented by Alon et al. [2], where elements appear multiple times andmust be covered by a different set at each arrival. Our results improve theO(log2(mn)) competitive factor of Online Set Cover with Repetitions [2]to O(log d log(dn)) = O(logmlog(mn)), where d is the maximum numberof sets an element belongs to.

Quality of Service in Network Creation Games - Cord-Landwehr, Andreas; Mäcker, Alexander; Meyer auf der Heide, Friedhelm (Proceedings of the 10th International Conference on Web and Internet Economics (WINE))
Network creation games model the creation and usage costs of networks formed by n selfish nodes. Each node v can buy a set of edges, each for a fixed price α > 0. Its goal is to minimize its private costs, i.e., the sum (SUM-game, Fabrikant et al., PODC 2003) or maximum (MAX-game, Demaine et al., PODC 2007) of distances from v to all other nodes plus the prices of the bought edges. The above papers show the existence of Nash equilibria as well as upper and lower bounds for the prices of anarchy and stability. In several subsequent papers, these bounds were improved for a wide range of prices α. In this paper, we extend these models by incorporating quality-of-service aspects: Each edge cannot only be bought at a fixed quality (edge length one) for a fixed price α. Instead, we assume that quality levels (i.e., edge lengths) are varying in a fixed interval [βˇ,β^] , 0 series = LNCS

Provider Competition in Infrastructure-as-a-Service - Künsemöller, Jörn; Brangewitz, Sonja; Karl, Holger; Haake, Claus-Jochen (Proceedings of the 2014 IEEE International Conference on Services Computing (SCC))
This paper explores how cloud provider competition inﬂuences instance pricing in an IaaS (Infrastructure-as-a-Service) market. When reserved instance pricing includes an on-demand price component in addition to a reservation fee (two-part tariffs), different providers might offer different price combinations, where the client’s choice depends on its load proﬁle. We investigate a duopoly of providers and analyze stable market prices in two-part tariffs. Further, we study offers that allow a speciﬁed amount of included usage (three-part tariffs). Neither two-part nor three-part tariffs produce an equilibrium market outcome other than a service pricing that equals production cost, i.e., complex price structures do not signiﬁcantly affect the results from ordinary Bertrand competition.

Programs from Proofs -- Approach and Applications - Wonisch, Daniel; Schremmer, Alexander; Wehrheim, Heike (Proceedings of the Software Engineering Conference (SE))
Proof-carrying code approaches aim at safe execution of untrusted code by having the code producer attach a safety proof to the code which the code consumer only has to validate. Depending on the type of safety property, proofs can however become quite large and their validation - though faster than their construction - still time consuming. In this paper we introduce a new concept for safe execution of untrusted code. It keeps the idea of putting the time consuming part of proving on the side of the code producer, however, attaches no proofs to code anymore but instead uses the proof to transform the program into an equivalent but more eﬃciently veriﬁable program. Code consumers thus still do proving themselves, however, on a computationally inexpensive level only. Experimental results show that the proof eﬀort can be reduced by several orders of magnitude, both with respect to time and space.

Privacy-Preserving Reputation Management - Petrlic, Ronald; Lutters, Sascha; Sorge, Christoph (Proceedings of the 29th Symposium On Applied Computing (SAC))
Reputation systems provide reputation values of rated parties to users. These reputation values, typically aggregations of individual user ratings, shall be reliable, i.e. should enable a realistic assessment of the probability that the rated party behaves as expected in a transaction. In order for the reputation values to stay reliable and, thus, for the reputation system to provide a beneﬁt, the system needs to be resistant against manipulations by users, the rated parties trying to improve their reputation values, and even against competitors trying to worsen a reputation value. At the same time, a reputation system shall provide privacy protection for users: rated parties shall not be able to learn who provided a certain rating. Otherwise users might not take part in the system as they fear bad feedback in revenge for bad ratings, or users do not want to be connected to certain transactions based on their provided ratings. In this paper we come up with a solution that provides both, reliability of reputation values on the one hand, and privacy protection for users on the other hand. In contrast to related work, our solution only makes use of a single reputation provider that needs to be trusted (to a certain extent) and does not require any bulletin boards to be present in the system. We make use of the Paillier cryptosystem to provide an aggregation of individual user ratings in a way that no party can learn which user provided a certain rating.

Privacy-Preserving Digital Rights Management based on Attribute-based Encryption - Petrlic, Ronald; Sorge, Christoph (Proceedings of the Sixth IFIP International Conference on New Technologies, Mobility and Security (NTMS))
We present a privacy-preserving multiparty DRM scheme that does not need a trusted third party. Users anonymously buy content from content providers and anonymously execute it at content execution centers. The executions are unlinkable to each other. The license check is performed as part of the used ciphertext-policy attribute-based encryption (CP-ABE) and, thus, access control is cryptographically enforced. The problem of authorization proof towards the key center in an ABE scheme is solved by a combination with anonymous payments.

Principles of Robust Medium Access and an Application to Leader Election - Awerbuch, Baruch; Richa, Andrea W.; Scheideler, Christian; Schmid, Stefan; Zhang, Jin (Transactions on Algorithms)
This article studies the design of medium access control (MAC) protocols for wireless networks that are provably robust against arbitrary and unpredictable disruptions (e.g., due to unintentional external interference from co-existing networks or due to jamming). We consider a wireless network consisting of a set of n honest and reliable nodes within transmission (and interference) range of each other, and we model the external disruptions with a powerful adaptive adversary. This adversary may know the protocol and its entire history and can use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1 − )-fraction of the timesteps, for an arbitrary constant > 0 unknown to the nodes. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant (asymptotically optimal) throughput for the nonjammed time periods under any of the aforementioned adversarial strategies. The derived principles are also useful to build robust applications on top of the MAC layer, and we present an exemplary study for leader election, one of the most fundamental tasks in distributed computing.

Ontology-based Representation of Optimization Models - Stapel, Florian; Suhl, Lena
This article presents a new approach for representing and processing abstract optimization models. Confronted with model and data integration tasks for distributed Decision Support Systems which are especially composed out of software services, we describe model constituents such as constraints both structurally and semantically. Within our approach, typed model constituents can be integrated into complete models and the instantiation of model constituents itself with data and data models can be wrapped into semantic software services. Besides others, this supports the automated generation of adaptors and the search for and composition of services. The basic idea of our approach is to represent the optimization models as instance knowledge of diﬀerent ontologies for both optimization and application domains. By separating the model expression structure from the goal and constraint conceptualizations predeﬁned modeling constructs can be reused, where we do not only separate the model structure from data, but can also abstract the structure from a speciﬁc data model. We present an XML and ontology-query based approach for this separation and demonstrate the resulting ﬂexible model integration procedure out of reusable goal and constraint types on a network ﬂow problem.

On-the-Fly Computing: Automatic Service Discovery and Composition in Heterogeneous Domains - Huma, Zille; Gerth, Christian; Engels, Gregor (Computer Science - Research and Development)
In software markets of the future, customer-specific software will be developed on demand based on distributed software and hardware services. Based on a customer-specific request, available service offers have to be discovered and composed into sophisticated IT services that fulfill the customer's request.A prerequisite of this vision are rich service descriptions, which comprise structural as well as behavioral aspects of the services, otherwise an accurate service discovery and composition is not possible. However, automatic matching of service requests and offers specified in rich service descriptions for the purpose of service discovery is a complex task, due to the multifaceted heterogeneity of the service partners. This heterogeneity includes the use of different specification languages, different underlying ontologies, or different levels of granularity in the specification itself.In this article, we present a comprehensive approach for service discovery and composition, which overcomes the underlying heterogeneity of the service partners. Based on a realistic case study of our industrial partner from the e-tourism domain, we first introduce an automatic matching mechanism for service requests and offers specified in a rich service description language. In addition, we propose an automatic service composition approach, which determines possible service compositions by composing the service protocols through a composition strategy based on labeled transition systems.

Datenschutz im Future Internet: rechtliche Aspekte und technische Maßnahmen - Sorge, Christoph; Petrlic, Ronald (Tagungsband des 17. Internationalen Rechtsinformatik Symposions)
Das Future Internet soll den Anforderungen heutiger und zukünftiger daten-intensiver Internet-Anwendungen besser gerecht werden als dies heute der Fall ist. Seit einigen Jahren wird an unterschiedlichen Verfahren geforscht, die das „Future Internet“ ermöglichen sollen – diese Ansätze gehen weit über die Ziele von IPv6 hinaus. In diesem Beitrag stellen wir einige Kernpunkte der Future-Internet-Initiativen vor und identifizieren Gemeinsamkeiten der unterschiedlichen Konzepte. Wir beleuchten die Konsequenzen aus datenschutzrechtlicher Sicht und geben einen Überblick über Ansätze, die die identifizierten Datenschutz-Probleme durch technische Maßnahmen bis zu einem gewissen Grad verhindern.

Constructing CCA-secure predicate encapsulation schemes from CPA-secure schemes and universal one-way hash functions - Blömer, Johannes; Liske, Gennadij
We present a new transformation of chosen-plaintext secure predicate encryption schemes with public index into chosen-ciphertext secure schemes. Our construction requires only a universal one-way hash function and is selectively secure in the standard model. The transformation is not generic but can be applied to various existing schemes constructed from bilinear groups. Using common structural properties of these schemes we provide an efficient and simple transformation without overhead in form of one-time signatures or message authentication codes as required in the known generic transformations.

Constitutions and Social Networks - Mauleon, Ana; Röhl, Nils; Vannetelbosch, Vincent
The objective of this paper is to analyze the formation of group structures where individuals are allowed to engage in several groups at the same time. These structures are interpreted here as social networks. Each of the groups is supposed to have specific rules or constitutions governing which members may join or leave it. A social network is then considered to be stable if none of the groups is altered any more. Given this framework, we not only analyze which influence the constitutions have on network formation but we also provide requirements under which stable networks are induced for sure. Furthermore, by embedding many-to-many matchings into our setting, we apply our model to job markets with labor unions. To some extent the unions may provide job guarantees and, therefore, have influence on the stability of the job market.

Conceptual Model and Economic Experiments to Explain Nonpersistence and Enable Mechanism Designs Fosterin Behavioral Change - Mir Djawadi, Behnud; Fahr, Rene; Turk, Florian (Value in Health)
BackgroundMedical nonpersistence is a worldwide problem of striking magnitude. Although many fields of studies including epidemiology, sociology, and psychology try to identify determinants for medical nonpersistence, comprehensive research to explain medical nonpersistence from an economics perspective is rather scarce.ObjectivesThe aim of the study was to develop a conceptual framework that augments standard economic choice theory with psychological concepts of behavioral economics to understand how patients’ preferences for discontinuing with therapy arise over the course of the medical treatment. The availability of such a framework allows the targeted design of mechanisms for intervention strategies.MethodsOur conceptual framework models the patient as an active economic agent who evaluates the benefits and costs for continuing with therapy. We argue that a combination of loss aversion and mental accounting operations explains why patients discontinue with therapy at a specific point in time. We designed a randomized laboratory economic experiment with a student subject pool to investigate the behavioral predictions.ResultsSubjects continue with therapy as long as experienced utility losses have to be compensated. As soon as previous losses are evened out, subjects perceive the marginal benefit of persistence lower than in the beginning of the treatment. Consequently, subjects start to discontinue with therapy.ConclusionsOur results highlight that concepts of behavioral economics capture the dynamic structure of medical nonpersistence better than does standard economic choice theory. We recommend that behavioral economics should be a mandatory part of the development of possible intervention strategies aimed at improving patients’ compliance and persistence behavior.

Competitive outcomes and the inner core of NTU market games - Brangewitz, Sonja; Gamp, Jan-Philip (Economic Theory)
We consider the inner core as a solution concept for cooperative games with non-transferable utility (NTU) and its relationship to payoffs of competitive equilibria of markets that are induced by NTU games. An NTU game is an NTU market game if there exists a market such that the set of utility allocations a coalition can achieve in the market coincides with the set of utility allocations the coalition can achieve in the game. In this paper, we introduce a new construction of a market based on a closed subset of the inner core which satisfies a strict positive separability. We show that the constructed market represents the NTU game and, further, has the given closed set as the set of payoff vectors of competitive equilibria. It turns out that this market is not uniquely determined, and thus, we obtain a class of markets. Our results generalize those relating to competitive outcomes of NTU market games in the literature.

Competitive MAC under adversarial SINR - Ogierman, Adrian; Richa, Andrea W.; Scheideler, Christian; Schmid, Stefan; Zhang, Jin (Proceedings of the 33rd Annual IEEE International Conference on Computer Communications (INFOCOM))
This paper considers the problem of how to efficiently share a wireless medium which is subject to harsh external interference or even jamming. While this problem has already been studied intensively for simplistic single-hop or unit disk graph models, we make a leap forward and study MAC protocols for the SINR interference model (a.k.a. the physical model). We make two contributions. First, we introduce a new adversarial SINR model which captures a wide range of interference phenomena. Concretely, we consider a powerful, adaptive adversary which can jam nodes at arbitrary times and which is only limited by some energy budget. The second contribution of this paper is a distributed MAC protocol which provably achieves a constant competitive throughput in this environment: we show that, with high probability, the protocol ensures that a constant fraction of the non-blocked time periods is used for successful transmissions.

Combining Automatic Service Composition with Adaptive Service Recommendation for Dynamic Markets of Services - Jungmann, Alexander; Mohr, Felix; Kleinjohann, Bernd (Proceedings of the 10th World Congress on Services (SERVICES))
Automatic service composition is still a challengingtask. It is even more challenging when dealing witha dynamic market of services for end users. New servicesmay enter the market while other services are completelyremoved. Furthermore, end users are typically no experts in thedomain in which they formulate a request. As a consequence,ambiguous user requests will inevitably emerge and have tobe taken into account. To meet these challenges, we proposea new approach that combines automatic service compositionwith adaptive service recommendation. A best first backwardsearch algorithm produces solutions that are functional correctwith respect to user requests. An adaptive recommendationsystem supports the search algorithm in decision-making.Reinforcement Learning techniques enable the system to adjustits recommendation strategy over time based on user ratings.The integrated approach is described on a conceptional leveland demonstrated by means of an illustrative example fromthe image processing domain.

Cloud Computing Reduces Uncertainties in Quality-of-Service Matching! - Becker, Matthias; Platenius, Marie Christin; Becker, Steffen (Proceedings of the 2nd International Workshop on Cloud Service Brokerage (CSB))
Cloud computing resulted in a continuously growing number of provided software services to be used by consumers. Brokers discover services that fit best to consumers' requirements by matching Qualityof-Service (QoS) properties. In order to negotiate Service-Level Agreements (SLAs), a provider has to determine the provided QoS based on QoS analyses. However, the risk for the provider to violate the SLA is high as the service's actual quality can deviate from the specified QoS due to uncertainties that occur during the provider's quality analysis. In this paper, we discuss current software engineering paradigms like cloud computing and service-oriented computing with respect to the amount of uncertainty they induce into service matching and SLA negotiations. As a result, we explain, why cloud computing reduces such uncertainties.

Certification for Configurable Program Analysis - Jakobs, Marie-Christine; Wehrheim, Heike (Proceedings of the 21st International Symposium on Model Checking of Software (SPIN))
Configurable program analysis (CPA) is a generic concept for the formalization of different software analysis techniques in a single framework. With the tool CPAchecker, this framework allows for an easy configuration and subsequent automatic execution of analysis procedures ranging from data-flow analysis to model checking. The focus of the tool CPAchecker is thus on analysis. In this paper, we study configurability from the point of view of software certification. Certification aims at providing (via a prior analysis) a certificate of correctness for a program which is (a) tamper-proof and (b) more efficient to check for validity than a full analysis. Here, we will show how, given an analysis instance of a CPA, to construct a corresponding sound certification instance, thereby arriving at configurable program certification. We report on experiments with certification based on different analysis techniques, and in particular explain which characteristics of an underlying analysis allow us to design an efficient (in the above (b) sense) certification procedure.

Budget-restricted utility games with ordered strategic decisions - Drees, Maximilian; Riechers, Sören; Skopalik, Alexander (Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT))
We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analysed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.

Brief Announcement: A Model for Multilevel Network Games - Abshoff, Sebastian; Cord-Landwehr, Andreas; Jung, Daniel; Skopalik, Alexander (Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT))
Today's networks, like the Internet, do not consist of one but a mixture of several interconnected networks. Each has individual qualities and hence the performance of a network node results from the networks' interplay.We introduce a new game theoretic model capturing the interplay between a high-speed backbone network and a low-speed general purpose network. In our model, n nodes are connected by a static network and each node can decide individually to become a gateway node. A gateway node pays a fixed price for its connection to the high-speed network, but can utilize the high-speed network to gain communication distance 0 to all other gateways. Communication distances in the low-speed network are given by the hop distances. The effective communication distance between any two nodes then is given by the shortest path, which is possibly improved by using gateways as shortcuts.Every node v has the objective to minimize its communication costs, given by the sum (SUM-game) or maximum (MAX-game) of the effective communication distances from v to all other nodes plus a fixed price α > 0, if it decides to be a gateway. For both games and different ranges of α, we study the existence of equilibria, the price of anarchy, and convergence properties of best-response dynamics.

Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria - Feldotto, Matthias; Gairing, Martin; Skopalik, Alexander (Proceedings of the 10th International Conference on Web and Internet Economics (WINE))
In this paper we study the potential function in congestion games. We consider both games with non-decreasing cost functions as well as games with non-increasing utility functions. We show that the value of the potential function $Φ(\sf s)$ of any outcome $\sf s$ of a congestion game approximates the optimum potential value $Φ(\sf s^*)$ by a factor $Ψ_{\mathcal{F}}$ which only depends on the set of cost/utility functions $\mathcal{F}$, and an additive term which is bounded by the sum of the total possible improvements of the players in the outcome $\sf s$. The significance of this result is twofold. On the one hand it provides Price-of-Anarchy-like results with respect to the potential function. On the other hand, we show that these approximations can be used to compute $(1+ε)·Ψ_{\mathcal{F}}$-approximate pure Nash equilibria for congestion games with non-decreasing cost functions. For the special case of polynomial cost functions, this significantly improves the guarantees from Caragiannis et al. [FOCS 2011]. Moreover, our machinery provides the first guarantees for general latency functions.

Approximate pure Nash equilibria in weighted congestion games - Hansknecht, Christoph; Klimm, Max; Skopalik, Alexander (Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX))
We study the existence of approximate pure Nash equilibria in weighted congestion games and develop techniques to obtain approximate potential functions that prove the existence of alpha-approximate pure Nash equilibria and the convergence of alpha-improvement steps. Specifically, we show how to obtain upper bounds for approximation factor alpha for a given class of cost functions. For example for concave cost functions the factor is at most 3/2, for quadratic cost functions it is at most 4/3, and for polynomial cost functions of maximal degree d it is at at most d + 1. For games with two players we obtain tight bounds which are as small as for example 1.054 in the case of quadratic cost functions.

Approximate pure Nash equilibria in Social Context Congestion Games - Gairing, Martin; Kotsialou, Grammateia; Skopalik, Alexander (Proceedings of the 10th International Conference on Web and Internet Economics (WINE))
We study the existence of approximate pure Nash equilibriain social context congestion games. For any given set of allowed costfunctions F, we provide a threshold value μ(F), and show that for theclass of social context congestion games with cost functions from F, α-Nash dynamics are guaranteed to converge to α-approximate pure Nashequilibrium if and only if α > μ(F).Interestingly, μ(F) is related and always upper bounded by Roughgarden’sanarchy value [19].