Vol. 34 · No. 1

Temporal reasoning and strategic behaviour are important abilities of multiagent systems. We introduce a game-theoretic framework suitable for modelling selfish and rational agents which can store and reason about the evolution of an environment, and act according to their interests. Our aim is to identify stable interactions: those where no agent has a benefit from changing his behaviour to another. For this reason we deploy the game-theoretic concept of Nash equilibrium and strong Nash equilibrium. We show that not all agent interactions can be stable. Also, we investigate the computational complexity for verifying and checking the existence of stable agent interactions. This paves the way for developing agents which can take appropriate decisions in competitive and strategic situations.

It is imperative to accept that failures can and will occur even in meticulously designed distributed systems and to design proper measures to counter those failures. Passive replication minimizes resource consumption by only activating redundant replicas in case of failures, as typically, providing and applying state updates is less resource demanding than requesting execution. However, most existing solutions for passive fault tolerance are usually designed and configured at design time, explicitly and statically identifying the most critical components and their number of replicas, lacking the needed flexibility to handle the runtime dynamics of distributed component-based embedded systems. This paper proposes a cost-effective adaptive fault tolerance solution with a significant lower overhead compared to a strict active redundancy-based approach, achieving a high error coverage with a minimum amount of redundancy. The activation of passive replicas is coordinated through a feedback-based coordination model that reduces the complexity of the needed interactions among components until a new collective global service solution is determined, hence improving the overall maintainability and robustness of the system.

In this paper, we address problems of efficient computing in distributed systems with non-dedicated resources including utility grid. There are global job flows from external users along with resource owner's local tasks upon the resource non-dedication condition. Competition for resource reservation between independent users, local and global job flows substantially complicates scheduling and the requirement to provide the necessary quality of service. A metascheduling concept, justified in this work, assumes a complex combination of job flow dispatching and application-level scheduling methods for parallel jobs, as well as resource sharing and consumption policies established in virtual organizations and based on economic principles. We introduce heuristic slot selection and co-allocation strategies for parallel jobs. They are formalized by given criteria and implemented by algorithms of linear complexity on an available slots number.

In this paper we present the study on the usage of distributed version of the algorithm for generalized one-sided concept lattices (GOSCL), which provides a special case for fuzzy version of data analysis approach called formal concept analysis (FCA). The methods of this type create the conceptual model of the input data based on the theory of concept lattices and were successfully applied in several domains. GOSCL is able to create one-sided concept lattices for data tables with different attribute types processed as fuzzy sets. One of the problems with the creation of FCA-based models is their computational complexity. In order to reduce the computation times, we have designed the distributed version of the algorithm for GOSCL. The algorithm is able to work well especially for data where the number of newly generated concepts is reduced, i.e., for sparse input data tables which are often used in domains like text-mining and information retrieval. Therefore, we present the experimental results on sparse data tables in order to show the applicability of the algorithm on the generated data and the selected text-mining datasets.

The most common applications of the today's IT world are information systems. The problems related to their design and implementation have sufficiently been solved. However, the true problems occur when an IS is already deployed and user requirements change. In this paper we introduce DaemonX – an evolution management framework which enables to manage evolution of complex applications efficiently and correctly. Using the idea of plug-ins, it enables to model almost any kind of a data format (currently XML, UML, ER, and BPMN). Since it preserves also mapping among modeled constructs of modeled formats via a common platform-independent model, it naturally supports propagation of changes to all related and affected parts.

Agent technology is in principle well suited for realizing various kinds of distributed systems, but in practice agents are seldomly chosen for realizing real-world applications. One reason hindering agents being used in practice is their cumbersome communication mechanism focused on speech act based message exchange which makes them hard for practitioners used to work in an object oriented way. To broaden the application spectrum of agent technology in practice and make them more accessible for object-oriented developers, this paper presents additional communication means for agents. First, it will be shown how agents can interact using strongly typed service interfaces resorting to asynchronous future based methods. These allow keeping agents autonomous and further support several recurrent interaction patterns within one method call, i.e. without having to use complex message protocols. Second, an extension for binary data streaming via virtual connections will be presented. Its usage resembles established input and output streaming APIs and lets developers transfer data between agents in the same simple way as e.g. a file is written to hard disk. Furthermore, virtual connections allow failure tolerant transmission by multiplexing data across different physical connections. Usefulness of the extensions will be further explained with a real-word example application from the area of business intelligence workflows.

The need of trust is growing in several contexts as e-commerce, virtual communities, distributed on-line services and many others as an essential precautionary component for users during interactions with strangers, either other people or virtual agents. Generally trust metrics endorse the principle ``the higher the trust, the more legitimate that user will be''; a consequence is that getting trusted must require some effort, otherwise all participants would easily achieve high trustworthiness. In this work we study how a user can achieve and preserve a good trust and what costs it requires over time; we also investigate some heuristics that allow reducing the complexity in exploring the rank-effort space especially for large networks.

SAPERE (``Self-Aware Pervasive Service Ecosystems'') is a general framework to support the decentralized execution of self-organizing pervasive computing services. In this paper we present the rationale underlying SAPERE and its reference conceptual architecture. Following, we sketch the middleware infrastructure of SAPERE and detail the interaction model implemented by it, based on a limited set of ``eco-laws'' allowing general-purpose distributed self-organizing schemes. Finally, we show how a social application can be easily implemented exploiting such an infrastructure and report on performances.

The consequence finding problem consists in producing all the consequences of a logical theory or, depending on the application context, in a restricted subset of these consequences. When the available knowledge is naturally scattered among different sources of information, computing such consequences with respect to the global theory in a decentralized way is a challenging problem. This paper presents swtwo, a multilayered architecture that may be used to solve such consequence finding problems in peer-to-peer networks of collaborating entities, that may evolve over time. The general layout of this architecture is described as well as the roles of its main components. Thanks to a careful and modular design, the resulting framework is very generic. This facilitates alternative implementations of specific components as well as its extension with additional features. First experimental results are presented, illustrating the scalability and robustness of this architecture. This framework may be used as a robust building block for more advanced distributed applications, such as Peer Data Management Systems.

Computational intelligence (CI), such as evolutionary computation or swarm intelligence methods, is a set of bio-inspired algorithms that have been widely used to solve problems in areas like planning, scheduling or constraint satisfaction problems. Constrained satisfaction problems (CSP) have taken an important attention from the research community due to their applicability to real problems. Any CSP problem is usually modelled as a constrained graph where the edges represent a set of restrictions that must be verified by the variables (represented as nodes in the graph) which will define the solution of the problem. This paper studies the performance of two particular CI algorithms, ant colony optimization (ACO) and genetic algorithms (GA), when dealing with graph-constrained models in video games problems. As an application domain, the ``Lemmings'' video game has been selected, where a set of lemmings must reach the exit point of each level. In order to do that, each level is represented as a graph where the edges store the allowed movements inside the world. The goal of the algorithms is to assign the best skills in each position on a particular level, to guide the lemmings to reach the exit. The paper describes how the ACO and GA algorithms have been modelled and applied to the selected video game. Finally, a complete experimental comparison between both algorithms, based on the number of solutions found and the levels solved, is analysed to study the behaviour of those algorithms in the proposed domain.

The scale-free graphs were proposed as a generic and universal model of network topologies that exhibit power-law distributions in the connectivity of network nodes. In recent years various complex networks were identified as having a scale-free structure. Little research was done concerning the network structure for DisCSP, and in particular, for scale-free networks. The asynchronous searching techniques are characterized by the occurrence of nogood values during the search for a solution. In this article we analyze the distribution of nogood values to agents and the way how to use the information from the nogood; that is called the nogood processor technique. We examine the effect of nogood processor for networks that have a scale-free structure aiming to develop search algorithms specialized for scale-free networks of constraints, algorithms that require minimum costs for obtaining the solution. We develop a novel way for distributing nogood values to agents, thus obtaining a new hybrid search technique that uses the information from the stored nogoods. The experiments show that it is more effective for several families of asynchronous techniques; we perform tests with the model running on a cluster of computers. Also, we examine the effect of synchronization of agents' execution and of processing messages by packets in scale-free networks.