Intelligent Distributed Computing, Systems and Applications

The gossip paradigm made its first appearance in distributed systems in 1987, when it was applied to disseminate updates in replicated databases. Two decades later, gossip-based protocols have gone far beyond dissemination, solving a large and diverse collection of problems. We believe that the story is not over: while gossip is not the panacea for distributed systems, there are still virgin research areas where it could be profitably exploited. In this paper, we briefly discuss a gossip-based “construction set” for distributed systems and we illustrate how intelligent distributed computing could benefit by the application of its building blocks. Simple examples are provided to back up our claim.

In our earlier work we have outlined general approach to ontological matchmaking in an agent-based virtual organization. The aim of this paper is to describe in details how matchmaking is to take place within the system under construction. The Grant Announcement application is used to illustrate the proposed approach. Questions concerning efficiency of matchmaking will be addressed and in this context a distinction between asynchronous and synchronous matchmaking will be proposed.

In this paper, we first motivate the need for innovative open service frameworks that ensure capability of self-adaptability and long-lasting evolvability (i.e., eternity). On this basis, we discuss how such frameworks should get inspiration from natural ecosystems, by enabling modelling and deployment of services as autonomous individuals in an ecosystem of other services, data sources, and pervasive devices. A reference architecture is presented to clarify the concepts expressed, and then several possible approaches to realise the idea are surveyed and critically analyzed.

It is our understanding that a selection algorithm in Case Based Reasoning (CBR) must not only apply the principles of evolution found in nature, to the predicament of finding an optimal solution, but to be assisted by a methodology for problem solving based on the concept of agent. On the other hand, a drawback of any evolutionary algorithm is that a solution is better only in comparison to other(s), presently known solutions; such an algorithm actually has no concept of an optimal solution, or any way to test whether a solution is optimal. In this paper it is addressed the problem of

The Selection Dilemma

in CBR, where the candidate solutions are seen as evolutionary logic programs or theories, here understood as making the core of computational entities or agents, being the test whether a solution is optimal based on a measure of the quality-of-information that stems out of them.

Creation of dynamic, non-trivial business relationships in agent-based trading environments requires the use of different types of middle-agents including matchmakers and arbitrators. In this note we apply the formal framework of

finite state process algebra

for modeling and analysis of complex interactions occurring in agent-based English auctions combined with matchmaking activities. In our model: i) several auctions initiated by different seller agents are carried out in parallel; ii) buyer agents have the option to register for participation only in auctions that match their goals and iii) buyers decision to what active auction to register for participation is taken dynamically.

When a XML document is stored in a relational or native database, its tree structure is usually dissolved into various forms of interval or Dewey indexes. Besides other advantages, these loosely-coupled structures allow parallel or distributed evaluation of XPath queries. However, when a XQuery or XSLT program produces a new XML document, its construction forms a hardly parallelizable bottleneck. In this paper, we present a method of XQuery/XSLT evaluation that directly generates Dewey-like structures representing the output of the transformation. This approach forms an output-side counterpart of Dewey-based XPath evaluation methods and makes parallel evaluation of XQuery/XSLT programs easier.

All-to-all broadcast is a communication pattern in which every node initiates a broadcast request. In this paper we investigate the problem of building a unique cast tree, that is unoriented (unrooted) tree and has minimal total power – minimal unique cast (MUC) tree – to be used for all-to-all broadcast. We propose a polynomial-time approximation algorithm for MUC problem. The power level of a node is selected to ensure bidirectional communication with its siblings, thus broadcast and convergecast can be performed in the tree starting at any node.

The increasing use of Internet for human real world activities such as e-commerce, exchange of information, advertising and several other service make the question of trust a critical issue. Today, everyone pushes information inside the net so is not easy to base trust on some, centralized authorities. many people is investigating how trust can be obtained - in some cases inspiring their investigation on social behavior - starting from some judges one may have on some others. This paper analyzes this matter, modelling trust relationship by a oriented graph and discussing some metrics useful to calculate

reputation

of a node based on others trust him/her.

Bottleneck for semantic web services is lack of semantically annotated information. We deal with linguistic information extraction from Czech texts from the Web for semantic annotation. The method described in the paper exploits existing linguistic tools created originally for a syntactically annotated corpus, Prague Dependency Treebank (PDT 2.0). We propose a system which captures text of web-pages, annotates it linguistically by PDT tools, extracts data and stores the data in an ontology. We focus on the third phase – data extraction – and present methods for learning queries over linguistically annotated data. Our experiments in the domain of reports of traffic accidents enable e.g. summarization of the number of injured people. This serves as a proof of concept of our solution. More experiments, for different queries and different domain are planned in the future. This will improve third party semantic annotation of web resources.

We introduce an implementation of Xord - an XSLT processing framework which enables us to design and implement efficient algorithms for clearly characterized classes of XSLT transformations with known memory requirements. Within the framework, we design and implement a streaming algorithm using stack of the size proportional to the depth of the input document and associate it with the class of simple order-preserving and branch-disjoint transformations. The framework provides an unified interface to the underlying algorithms and acts as a standard XSLT processor.

In a mobile ad-hoc network, nodes cannot rely on any fixed infrastructure for routing purposes. Rather, they have to cooperate to achieve this objective. However, the absence of any trusted third party in such networks may result in nodes deviating from the routing protocol for selfish or malicious reasons. The concept of trusted routing has been promoted to handle the problems selfish and malicious nodes cause to the network. In this paper, we focus on using trust in routing, and show how trust can mitigate against malicious behaviour.

Grid environments, providing distributed infrastructures, computing resources and data storage, usually show a high degree of heterogeneity in their metadata. We propose a platform for collaborative management and maintenance of common metadata for grids. As the conceptual foundation of this platform, a meta model is presented which distinguishes structured descriptions and classification structures. On this basis, the system allows for the user-friendly creation and editing of grid relevant metadata and provides various search and navigation facilities for grid participants. We applied the platform to the German D-Grid initiative by establishing the D-Grid Ontology (DGO).

Distributed computing attempts to aggregate different computing resources available in enterprises and in the Internet for computation intensive applications in a transparent and scalable way. Digital test generation aims to find minimal set of test vectors to obtain maximum fault coverage for digital electronic circuits. In this paper we focus on distributed environment and parallelization of the computationally intensive genetic algorithm based test generation for sequential circuits. We discuss the concept and implementation of our system infrastructure, task partitioning, allocation, test generation algorithm and results.

The goal of this research was to identify the suitable technologies for enacting the World Wide Argument Web (WWAW) in the context of newly arisen Pragmatic Web paradigm. The vision is to develop the WWAW based on the Argument Interchange Format (AIF) ontology. On the one hand, we propose concept maps for presenting AIF-based arguments to the human agents. On the other hand, the argumentation schemes are formalized as planning operators in order to provide software agents with the ability to build argumentation plans.

The mammal immune system is a distributed multiagent system. Its properties of distributive control and self organization have created interest in using immune principles to solve complex engineering tasks such as decentralized robot control, pattern recognition, multimodal and combinatorial optimization. In this paper a new immunity-based algorithm for solving optimization problems is proposed. The algorithm differs from the representative immune algorithm CLONALG. The agents participating in distributed problem solving enrich their knowledge about the solution via communication with other agents. Moreover they are decomposed into groups of specialists that can modify only some decision variables and/or use their own method of local improvement of the solution. The empirical results confirming usability of the algorithm and its advantage over CLONALG are presented. Obtained estimates of the global optima of multimodal test functions and traveling salesperson problem (TSP) are closer to the theoretical solutions and require fewer tentative computations.

The increased demand and complexity of the services operating within open distributed environments has emphasized the need for more robust, adaptive and self-organizing solutions. To address these problems some agent oriented approaches, like the Bio-Networking architecture, have adopted ideas from large scale biological collectives as a solution. However the introduction of biological properties, like birth and death events, generates an extremely dynamic system, making it difficult to maintain the overall connectivity of the agent network and discovery of resources within the system. Towards this end, in this paper the performance of a selective discovery mechanism is evaluated through multi-agent simulation studies. The primary focus of this study is on the impacts which death and (sexual/asexual) reproduction events have on the effectiveness of the discovery process in different overlay networks.

This paper describes a distributed collaborative wiki-based platform that has been designed to facilitate the development of Semantic Web applications. The applications designed using this platform are able to build semantic data through the cooperation of different developers and to exploit that semantic data. The paper shows a practical case study on the application VPOET, and how an application based on Google Gadgets has been designed to test VPOET and let human users exploit the semantic data created. This practical example can be used to show how different Semantic Web technologies can be integrated into a particular Web application, and how the knowledge can be cooperatively improved.

In this paper we look into three approaches, based on:

Game Theory, Auction

and

Consensus

methods, to combine information from multiple sources. As originally introduced, they are conceptualized using an agent metaphor and implemented using a JADE agent platform. Preliminary performance comparison completes the presentation.

Multi Agent Systems represent a new approach for modeling complex and distributed systems. Many efforts of software engineering aim at providing methodologies and tools for designing and developing MAS. However formal verification of MAS dependability is still an open issue. Here we focus on modeling, design and verification of real-time properties in MASs. We propose a methodology that supports developers in different phases of MAS developing cycle. We also present an integrated environment that allows for UML design, code generation, time constraints verification and testing of soft-real time MASs. A case of study is described to demonstrate an application of such methodology and the utilization of developed tools.

Corporate governance and legislative regulations are forcing companies to extend their IT infrastructure by Email Archive and Discovery (EAD) systems for compliance reasons. Praxis shows that every installation is different from another; not only in terms of the execution infrastructure, but also in terms of e.g. document and archiving procedures that map a company’s own business rules. As a consequence, EAD systems have to be highly customizable to their intended usages.

For this purpose, we propose a service-oriented approach at various levels of detail that, on one hand, allows for describing EAD properties at the abstract (service) level and, on the other hand, supports the appropriate mapping of these services to the existing execution infrastructure. In this paper, we focus on the development and (architectural) design of an EAD system, which is well suited to fulfill these requirements. On the long run, we consider this solution as an important step on the way to an effective distributed and scalable approach, which, as we think, can be achieved by appropriate mechanisms of automatic workload management and dynamic provisioning of EAD services based on e.g. grid technology.

In this paper we propose a technique for evaluating similarity of XML schema fragments. Contrary to existing works we focus on structural level in combination with semantic similarity of the data. For this purpose we exploit the idea of edit distance utilized to constructs of DTDs which enables to express the structural differences of the given data more precisely. In addition, in combination with the semantic similarity it provides more realistic results. Using various experiments we show the behavior and advantages of the proposed approach.

Self-stabilizing protocols provide autonomous recovery from finite number of transient faults. Fault-containing self-stabilizing protocols promise not only self-stabilization but also quick recovery and small effect from small scale of faults. In this paper, we introduce a timer-based composition of fault-containing self-stabilizing protocols that preserves the fault-containment property of source protocols. Our framework can be applied to a larger subclass of fault-containing self-stabilizing protocols than existing compositions [1].

Embedding is a method to obtain new distributed protocols for other topologies from existing protocols designed for specific topologies. But the fault tolerance of the original protocol is rarely preserved in the protocol embedded in the target topology, called

embedded protocol

. Specifically, transient faults can affect intermediate processes along the path in the target topology that corresponds to a link in the original topology.

In this paper, we propose to analyze and model the communication of the embedded protocol as unreliable communication along the links of the original protocol. We propose a particular type of unreliable channel called

almost reliable

channel and we show an implementation of these channels for embedding a protocol into another topology.

Nowadays mobile and fixed networks are trusted with highly sensitive information, which must be protected by security protocols. However, security protocols are vulnerable to a host of subtle attacks, such as replay, parallel session and type-flaw attacks. Designing protocols to be impervious to these attacks has been proven to be extremely challenging and error prone.

This paper discusses various attacks against security protocols. As an example, the security of the Wide-Mouthed Frog key distribution protocol when subjected to known attacks is discussed. Significantly, a hitherto unknown attack on Lowe’s modified version of the Wide-Mouthed Frog protocol is presented. Finally, a correction for the protocol to prevent this attack is proposed and discussed.

In order to integrate new security protocols, existing systems must be modified accordingly, which often means interrupting system activity. We propose a solution to this problem by developing an ontology model which provides semantic to security protocol operations. The proposed model is based on a formal specification model and is integrated in existing Web service description technologies.

In the last eight years, registries for e-business, such as ebXML or UDDI, enabling enterprise of any size and in any geographical location to conduct their businesses on the World Wide Web, were developed. Applications in domains such as insurance (for example, insurance rating), financial services (loans, claims routing and management, fraud detection), government (tax calculations), telecom customer (care and billing), e-commerce (personalizing the user’s experience, recommender systems, auctions), and so on benefit greatly from using rule engines. Therefore, sharing rulesets becomes a necessity for many B2B businesses. This work presents a basic architecture of building a Web-based registry for rules. The main goal of the registry is to allow rulesets discovery. Registry entries contain both required ruleset related data (such as ruleset URI or properties describing their intended scope) and optional metadata covering additional properties such as

last modified date

.

Data dictionaries allow efficient transformation of repeating input values. The attention is focused on the analysis of voluminous lookup tables that store up to a few tens of millions of key-value pairs. Because of their compactness and search efficiency, hash tables turn out to provide the best solutions in such cases. This paper deals with performance issues of such structures and its main contribution is to take into consideration the effect of the multi-level memory hierarchies present in all the current computers. The paper enumerates and compares various choices and methods in order to give an indication how to choose the structure and the parameters of hash tables in case of large-scale, in-memory data dictionaries.

A comprehensive approach to the design of Ubiquitous Computing systems must deal with the issues related to the restoration of an earlier or acceptable state of the system, if possible, when users intentionally want to undo some previous actions. Systems supporting collaborative Ubiquitous Computing environments should provide a default undo function, but also provide users and applications with awareness information to correctly decide which (compensative) actions should be undertaken. In this paper we describe how to achieve undo in distributed, dynamic, context-aware systems. We present a general approach to undo in collaborative Ubiquitous Computing environments in terms of the CASMAS model: part of the approach relies on the notion of active coordination artifacts, as defined also in CSCW literature.

Events in a distributed global computation framework, unlike those in a sequential local computation, form a partially ordered set with respect to the causality relation revealed by timestamps. This paper describes a new logical timestamping mechanism based on multicasting, called

Collective Logical Time

, and compares it with other known schemes that have been developed in the domain mainly to help in detecting undesired (global) properties of distributed computations (such as deadlock). Unfortunately, due to excessive complexity and some unrealistic restrictions (such as a fixed number of processes), these schemes have produced limited results. Some of the benefits in using our scheme are revealed, together with the possibilities for direct applications in the development of low-level communication protocols.

Software agents that operate on the Semantic Web have to deal with scenarios where the discovery and combination of the relevant information from a variety of heterogeneous sources becomes contradicting. One such application area of the Semantic Web is ontology mapping where different similarities have to be combined into a more reliable and coherent view, which might easily become unreliable if trust is not managed effectively between the different sources. In this paper we propose a solution for managing trust between contradicting beliefs in similarities for ontology mapping based on the fuzzy voting model.

This work introduces algorithmic trading on artificial stock markets and describes past and existing approaches. A proposed framework of the artificial stock market approach is presented, together with the used agent types. Then the simulation results’ analyses are discussed. Conclusions and future work directions are presented, showing where the MACD algorithm and some rules can be used. The human behavior influence over the market is highlighted.

Workers, Inc., a workflow management system implemented using the technology of mobile agents, is especially suited for highly distributed and heterogeneous environments. This paper discusses the issues related to visual definitions of new processes, and their translation into execution contexts of the system.

E-Commerce recommender systems provide customers with useful suggestions about available products. However, in presence of a high number of interactions between customers and Web sites, the generation of recommendations could become a heavy task. Moreover, customers often navigate on the Web using different devices whose different characteristics may influence customer’s preferences. In this paper we propose a new multi-agent system in which each device exploited by a customer is associated with a software agent which autonomously monitors the customer’s behaviour. The use of device agents leads to generate recommendations taking into account the exploited device, while the fully decentralized architecture introduces a strong reduction of the time costs.

The importance of mutual monitoring in recommender systems based on learning agents derives from the consideration that a learning agent needs to interact with other agents in its environment in order to improve its individual performances. In this paper we present a novel framework, called EVA, that introduces a strategy to improve the performances of recommender agents based on a dynamic computation of the agent’s reputation. Some preliminary experiments show that our approach, implemented on the top of some well-known recommender systems, introduces significant improvements in terms of effectiveness.

The paper presents original ways of using a modern concept - topic map - in medical e-learning. The topic map is mainly used for visualizing a thesaurus containing medical terms. The topic map is built and populated in an original manner, mapping an xml file that can be downloaded free, to an xtm file that contains the structure of the topic map. Only a part of the MeSH thesaurus was used, namely the part that includes the medical diagnosis’s names. The student can navigate through topic map depending on its interest subject, having in this way big advantages. The paper presents also how to use the topic map for semantic querying of a multimedia database with medical information and images. For retrieving the interest information this access path can be combined with another modern solution: the content-based visual query on the multimedia medical database. Combining these possibilities to access a database with medical data and images, allows students to see images and associated information in a simple and direct manner. The students are stimulated to learn, by comparing similar cases or by comparing cases that are visually similar, but with different diagnoses.