This paper addresses the problem of task allocation among multiple autonomous agents that must accomplish a complex global task. Solutions to the problem have real-world applications in defense, space, disaster management, etc. We solve this problem via agent coalition formation. Multiple coalition formation mechanisms were introduced in prior art, seldom accounting for interdependent tasks. We address this challenge. We introduce an anytime decentralized coalition formation mechanism that enables agents with complementary capabilities to form, autonomously and dynamically, feasible coalition structures that accomplish a global, composite task. The formed structures are incrementally improved via agent replacements to optimize a global utility. We analyze the complexity and show that, although the general problem is NP-hard, our mechanism provides a solution within acceptable time. We present extensive experimental results that illustrate the added value of our approach.

Text mining have gained great momentum in recent years, with user-generated content becoming widely available. One key use is comment mining, with much attention being given to sentiment analysis and opinion mining. An essential step in the process of comment mining is text pre-processing; a step in which each linguistic term is assigned with a weight that commonly increases with its appearance in the studied text, yet is offset by the frequency of the term in the domain of interest. A common practice is to use the well-known tf-idf formula to compute these weights. This paper reveals the bias introduced by between-participants' discourse to the study of comments in social media, and proposes an adjustment. We find that content extracted from discourse is often highly correlated, resulting in dependency structures between observations in the study, thus introducing a statistical bias. Ignoring this bias can manifest in a non-robust analysis at best and can lead to an entirely wrong conclusion at worst. We propose an adjustment to tf-idf that accounts for this bias. We illustrate the effects of both the bias and correction with with seven Facebook fan pages data, covering different domains, including news, finance, politics, sport, shopping, and entertainment.

Collective decision-making is a process in which participants make a collective choice from several alternatives. In this paper, we focus on collective decision contexts in which more than two selfish agents negotiate over multiple issues. We specifically consider a case of joint household energy purchase where the concerned households have to define a collective energy contract. The households involved may each be interested only in a subset of the issues at stake. We devise an effective protocol to regulate the interactions among the (household) agents and reduce their reasoning complexity. The mechanism we introduce is fully decentralized, it facilitates multi-lateral negotiation, and it reduces the complexity of the solution despite the inherent complexity of the problem.

Negotiation is a fundamental mechanism in multi-agent systems. It may be a complex mechanism involving multiple agents with conflicting interests that need to reach a joint agreement. Complexity intensifies when moving from bilateral to multilateral negotiation. An important issue in such negotiation is to define a specific and effective protocol that guides the interactions between the agents. In this paper, we propose a novel, fully decentralized mechanism for multilateral negotiation, that reduces the inherent complexity of the problem. We specifically reduce the complexity of searching in the agreement search space, utilizing the divide and conquer approach. The proposed negotiation mechanism structures the negotiation by dividing a set of agents into several groups. Proposals are initially exchanged only within groups, and only later across groups. This structure is enhanced with various interaction policies. These policies include rules that determine permissible behaviors of the agents within the structure. Via structure and policies our negotiation protocol controls the negotiation time and facilitates feasible multi-lateral negotiation. We provide theoretical and experimental results showing the efficiency of our protocol.

We address the problem of efficient coordination protocols in the contexts where mobile and ad-hoc devices which harbor the selfish agents must achieve a set of dynamic tasks. This work assumes that, due to the dynamic behaviors of the agents induced by the unpredictable availability of these devices and the dynamic of the tasks, it is not possible to devise an efficient coordination which uses prior knowledge about the information of the agents ahead of task achievements. In these contexts, we provide both protocols called depth exploration protocol and width exploration protocol which are based on the formalism of the MDP (Markov Decision Process) and on alliance principle. The aim of our protocols is to ensure and to adapt dynamically the stability of the agent's coordination teams (coalitions) which take into account the agent's withdrawal and the dynamic evolving of the tasks. We develop a theoretical study of our mechanism and we provide an analytical and experimental performance evaluation.

This paper aims at evaluating a set of automated tools of the FITTEST EU project within an industrial case study. The case study was conducted at the IBM Research lab in Haifa, by a team responsible for building the testing environment for future development versions of an IBM system management product. The main function of that product is resource management in a networked environment. This case study has investigated whether current IBM Research testing practices could be improved or complemented by using some of the automated testing tools that were developed within the FITTEST EU project. Although the existing Test Suite from IBM Research (TSibm) that was selected for comparison is substantially smaller than the Test Suite generated by FITTEST (TSfittest), the effectiveness of TSfittest, measured by the injected faults coverage is significantly higher (50% vs 70%). With respect to efficiency, by normalizing the execution times, we found the TSfittest runs faster (9.18 vs. 6.99). This is due to the fact that the TSfittest includes shorter tests. Within IBM Research and for the testing of the target product in the simulated environment: the FITTEST tools can increase the effectiveness of the current practice and the test cases automatically generated by the FITTEST tools can help in more efficient identification of the source of the identified faults. Moreover, the FITTEST tools have shown the ability to automate testing within a real industry case.

SUMMARY This paper addresses integration testing of data‐centric and event‐based dynamic service compositions. The compositions under test define abstract services that are replaced by concrete candidate services at runtime. Testing all possible instantiations of a composition leads to combinatorial explosion and is often infeasible. We consider data dependencies between services as potential points of failure and introduce the k‐node data flow test coverage metric, which helps to significantly reduce the number of test combinations. We formulate a combinatorial optimization problem for generating minimal sets of test cases. On the basis of this formalization, we present a mapping to the model of FoCuS, a coverage analysis tool. FoCuS efficiently computes near‐optimal solutions, which are used to automatically generate test instances. The proposed approach is applicable to various composition paradigms. We illustrate the end‐to‐end practicability based on an integrated scenario, which uses two diverse composition techniques: on the one hand, the Web Services Business Process Execution Language and on the other hand, WS‐Aggregation, a platform for event‐based service composition. Copyright © 2013 John Wiley & Sons, Ltd.

In this paper we study distributed agent matching in environments characterized by uncertain signals, costly exploration, and the presence of an information broker. Each agent receives information about the potential value of matching with others. This information signal may, however be noisy, and the agent incurs some cost in receiving it. If all candidate agents agree to the matching the team is formed and each agent receives the true unknown utility of the matching, and leaves the market. We consider the effect of the presence of information brokers, or experts, on the outcomes of such matching processes. Experts can, upon payment of a fee, perform the service of disambiguating noisy signals and revealing the true value of a match to any agent. We analyze equilibrium behavior given the fee set by a monopolist expert and use this analysis to derive the revenue maximizing strategy for the expert as the first mover in a Stackelberg game. Surprisingly, we find that better information can hurt: the presence of the expert, even if the use of its services is optional, can degrade both individual agents' utilities and overall social welfare. While in one-sided search the presence of the expert can only help, in two-sided (and general k-sided) search the externality imposed by the fact that others are consulting the expert can lead to a situation where the equilibrium outcome is that everyone consults the expert, even though all agents would be better off if the expert were not present. As an antidote, we show how market designers can enhance welfare by taxing use of expert services.

Large systems generate immense quantities of code coverage data. A user faced with the task of analyzing this data, for example, to decide on test areas to improve, faces a 'needle in a haystack' problem.

This paper addresses the problem of integration testing of data-centric dynamic compositions in service-based systems. These compositions define abstract services, which are replaced by invocations to concrete candidate services at runtime. Testing all possible runtime instances of a composition is often unfeasible. We regard data dependencies between services as potential points of failure, and introduce the k-node data flow test coverage metric. Limiting the level of desired coverage helps to significantly reduce the search space of service combinations. We formulate the problem of generating a minimum set of test cases as a combinatorial optimization problem. Based on the formalization we present a mapping of the problem to the data model of FoCuS, a coverage analysis tool developed at IBM. FoCuS can efficiently compute near-optimal solutions, which we then use to automatically generate and execute test instances of the composition. We evaluate our prototype implementation using an illustrative scenario to show the end-to-end practicability of the approach.

Many service-oriented systems are not well equipped to guarantee that service time is optimized. We have specifically examined two industrial systems which implement service-oriented architectures in real, field environments. We discovered that both were not engineered to properly address surges in service request rate. In the absence of an integral solution, it is difficult and costly to (re-) engineer such a solution in the field. The challenge faced by this study was to deliver a low cost solution, without re-engineering the target systems. This paper introduces such a generic solution. The solution slows-down some components to deliver improvement in request service time. It was implemented, tested, and successfully applied to two industrial systems with no need to modify their logic or architecture. Experiments with those systems exhibited significant improvement in performance. These results have validated our solution and its industrial applicability across systems and environments.

While a number of modeling languages for constructing multiagent systems (MASs) have been suggested, none of them is widely accepted and used. A prominent reason for this is the gap that exists between agent-oriented modeling languages and the agent-based system modeling needs, including accessibility, flexibility, and expressiveness. This paper addresses the need for such a language by proposing object-process methodology (OPM)/MAS, an agent modeling language (AML) that extends OPM with an intermediate metamodel of the MAS domain. Three case studies and a comparison to contemporary AMLs demonstrate the novelty and benefits of OPM/MAS.

Component level performance thresholds are widely used as a basic means for performance management. As the complexity of managed systems increases, manual threshold maintenance becomes a difficult task. This may result from a) a large number of system components and their operational metrics, b) dynamically changing workloads, and c) complex dependencies between system components. To alleviate this problem, we advocate that component level thresholds should be computed, managed and optimized automatically and autonomously. To this end, we have designed and implemented a performance threshold management sub-system that automatically and dynamically computes two separate component level thresholds: one for controlling Type I errors and another for controlling Type II errors. We present the theoretical foundation for this autonomic threshold management system, describe a specific algorithm and its implementation, and evaluate it using real-life scenarios and production data sets. As our present study shows, with proper parameter tuning, our on-line dynamic solution is capable of nearly optimal performance thresholds calculation.

Provides notice of upcoming conference events of interest to practitioners and researchers.

Domain engineering can simplify the development of software systems in specific domains. During domain analysis, the first step of domain engineering, the domain is modeled at an abstract level, providing guidelines for modeling applications within that domain. Drawbacks of existing domain analysis approaches include poor guidelines for domain-specific application modeling, insufficient validations capability, and limited usability. In this paper we apply the Application-based Domain Modeling (ADOM) to the Object-Process Methodology (OPM). This application requires the extension of OPM with a classification mechanism. Showing that the ADOM-OPM approach overcomes limitations of existing approaches, we further verify experimentally that the level of correctness of an ADOM extended OPM model is higher than that achieved without the extension. Finally, we ensure that the proposed extension does not degrade the generic vanilla form of OPM.

Self-healing capabilities allow software systems to overcome problems occurring during testing and run time, and thus improve overall system behavior. The PANACEA framework introduced in this paper provides a design methodology as well as ready-to-use healing elements aimed at enhancing software systems with self-healing capabilities both at design time and at run time. The PANACEA approach is based on inserting self- healing elements into the system at design and coding time, to be used later for healing at testing and run time. Specifically, the Panacea framework is based on inserting annotations into the system code at design and coding time, to later on serve as an interface for runtime monitoring, managing, configuring and healing of the annotated system components. The current embodiment of PANACEA includes several generic components that provide self-healing capabilities suited for a variety of application types. The PANACEA runtime environment automatically activates and invokes these components in order to optimize and heal the application. The PANACEA framework provides an innovative programming model that enables development of advanced self-healing applications. PANACEA introduces a paradigm shift in which software is made self-healing by design. This paradigm shift, however, is graceful since developers are not required to master neither new programming skills, nor languages. As our initial experiments demonstrate, PANACEA introduces a very small performance overhead, and scales well.

SOQUA 2007 aims to bring together researchers, engineers, and practitioners to discuss and evaluate latest challenges, breakthroughs and experiences in the field of software quality assurance, and to identify open issues and future trends in this area. Among the many quality assurance topics, SOQUA 2007 puts special focus on the role that emerging self adaptive and self-healing solutions can play in quality assurance. The program committee had the difficult task to select 17 papers out of 27 high-quality submissions from all over the world. The selected papers cover 11 countries and 5 continents, and many aspects of software quality assurance, including: self-healing and self-adaptive solutions, testing, quality assurance processes, process modeling, failure analysis and anticipation, quality of requirements, and variability modeling. These papers represent a significant contribution to the state of the art in the field. The workshop program consists of 1 keynote address given by Wilhelm Schäfer, 5 paper sessions hosting the authors' presentations, and 2 discussion sessions on hot-topics in the field.

We present a novel algorithm, called IPASS, for root cause analysis of performance problems in storage area networks (SANs). The algorithm uses configuration information available in a typical SAN to construct I/O paths, that connect between consumers and providers of the storage resources. When a performance problem is reported for a storage consumer in the SAN, IPASS uses the configuration information in an on-line manner to construct an I/O path for this consumer. As the path construction advances, IPASS performs an informed search for the root cause of the problem. The underlying rationale is that if the performance problem registered at the storage consumer is indeed related to the SAN itself, the root causes of the problem are more likely to be found on the relevant I/O paths within the SAN. We evaluate the performance of IPASS analytically and empirically, comparing it to known, informed and uninformed search algorithms. Our simulations suggest that IPASS scales 7 to 10 times better than the reference algorithms. Although our primary target domain is SAN, IPASS is a generic algorithm. Therefore, we believe that IPASS can be efficiently used as a building block for performance management solutions in other contexts as well.

In the face of multiple electronic sales sites, buyers can benefit from considering multiple opportunities and devising their purchase strategy to reduce risk and increase expected utility. However, human users cannot approach and rapidly monitor multiple sites. In particular, sites where prices change dynamically such as auction sites pose a major difficulty for human concurrent activity. Even without concurrency, the majority of human users do not have the ability or the resources to compute optimal purchase decisions. Such activities can be performed by computational agents. In this paper, we present mechanisms that allow agents to perform purchases on behalf of users. In particular, we devised methods that allow an agent that faces multiple dynamic sales sites to compute bids that optimize the expected utility of the user, or instead manage the winning probability of the purchase.

Cooperating and sharing resources by creating coalitions of agents are important ways for autonomous agents to execute tasks and to maximize payoff. Such coalitions will form only if each member of a coalition gains more by joining the coalition than it could gain otherwise. There are several ways of creating such coalitions and dividing the joint payoff among the members. In this paper we present algorithms for coalition formation and payoff distribution in nonsuperadditive environments. We focus on a low‐complexity kernel‐oriented coalition formation algorithm. The properties of this algorithm were examined via simulations. These have shown that the model increases the benefits of the agents within a reasonable time period, and more coalition formations provide more benefits to the agents.