to appear

Accepted/In press

Self-adaptive systems alter their behavior in response to environmental changes to continually satisfy their requirements. Self-adaptive systems employ an environment model, which should be updated during runtime to maintain consistency with the real environment. Although some techniques have been proposed to learn environment model based on execution traces at the design time, these techniques are time consuming and consequently inappropriate for runtime learning. Herein, a technique using a stochastic gradient descent and the difference in the data acquired during the run-time is proposed as an efficient learning environment model. The computational time and accuracy of our technique are verified through a case study.

Live migration plays an important role on improving efficiency of cloud data centers by enabling dynamically replacing virtual machines (VMs) without disrupting services running on them. Although many studies have proposed acceleration mechanisms of live migration, IO-intensive VMs still suffer from long total migration time due to a large amount of page cache. Existing studies for this problem either force the guest OS to delete the page cache before a migration, or they do not consider dynamic characteristics of cloud data centers. We propose a parallel and adaptive transfer of page cache for migrating IO-intensive VMs which (1) does not delete the page cache and is still fast by utilizing the storage area network of a data center, and (2) achieves the shortest total migration time without tuning hand-crafted parameters. Experiments showed that our method reduces total migration time of IO-intensive VMs up to 33.9%.

Service composition provides a means of customized and flexible integration of service functionalities. Quality-of-service (QoS) optimization algorithms select services to adapt workflows to the non-functional requirements of the user. With increasing number of services in a workflow, previous approaches fail to achieve a sufficient reliability. Moreover, expensive ad-hoc replanning is required to deal with service failures. The major problem with such sequential application of planning and replanning is that it ignores the potential costs during the initial planning and they consequently are hidden from the decision maker. Our idea to overcome this problem is to compute a QoS optimized selection of service clusters that includes a sufficient number of backup services for each service employed. These backup services should be sufficiently distributed to prevent a task failure in case of, e.g., a network failure. To support the decision maker in the selection task, our multi-objective approach considers the possible repair costs directly in the initial composition. Our graphical user interface visualizes the resulting QoS of the workflow and the location of the services to enable the decision maker to select compositions in line with risk preferences. We prove the benefits of our approach in our detailed evaluation.

Mutation analysis is a method for evaluating the effectiveness of a test suite by seeding faults artificially and measuring the fraction of seeded faults detected by the test suite. The major limitation of mutation analysis is its lengthy execution time because it involves generating, compiling and running large numbers of mutated programs, called mutants. Our tool MuVM achieves a significant runtime improvement by performing higher order mutation analysis using four techniques, metamutation, mutation on virtual machine, higher order split-stream execution, and online adaptation technique. In order to obtain the same behavior as mutating the source code directly, metamutation preserves the mutation location information which may potentially be lost during bitcode compilation and optimization. Mutation on a virtual machine reduces the compilation and testing cost by compiling a program once and invoking a process once. Higher order split-stream execution also reduces the testing cost by executing common parts of the mutants together and splitting the execution at a seeded fault. Online adaptation technique reduces the number of generated mutants by omitting infeasible mutants. Our comparative experiments indicate that our tool is significantly superior to an existing tool, an existing technique (mutation schema generation), and no-split-stream execution in higher order mutation.

Refinement in formal specifications has received significant attention as a method to gradually construct a rigorous model. Although refactoring methods for formal specifications have been proposed, there are no methods for refactoring of refinement structures in formal specifications. In this paper, we describe a method to restructure refinements in specifications of Event-B, a formal specification method with supports for refinement. The core of our method is decomposition of refinements. Namely, when an abstract Event-B machine A, a concrete machine C refining A, and a slicing strategy are provided, our method constructs a consistent intermediate machine B, which refines A and is refined by C. We show effectiveness of our methods through two case studies on representative usages of our method: decomposition of large-scale refinements and extraction of reusable parts of specifications.

Alloy is a formal specification language that is widely used to verify software systems. However, while users can verify the properties of a specification with Alloy, it is not so easy for them to validate the specification, that is, to check that the specification is written just as the users intended. Alloy Analyzer, a tool supporting Alloy, has a feature to show concrete instances satisfying specifications that can be help in validation, but it does not control the order in which the instances are shown. Many studies have been conducted on ordering to help users explore instances in structured ways. However, not much prior research has focused on proper ways to explore instances for validating specifications. In this paper, we propose a method to assist users in validating specifications by displaying a set of instances that tend to include problems when their specifications have defects. In particular, the method applies pairwise testing to relations of Alloy specifications. We show effectiveness of the method in experiments using mutation analysis.

The Problem Frames approach has attracted attention because it enables developers to carefully analyze problems in a reasonable manner. Despite that this approach decomposes a problem into subproblems before the analysis is conducted, developers are still faced with a complex analysis when they consider interactions between the various subproblems. Moreover, progressive evolution of requirements is important for flexible development. In this paper, we propose methods to analyze multiple abstraction layers of a problem. Our methods help developers to construct abstract versions of a problem and find relationships between abstract problems and concrete problems. Moreover, our methods support refinement of arguments such that the properties of the abstract problem are preserved in the concrete problem. Therefore, our methods enable developers to divide up arguments into multiple abstraction layers and thus mitigate the complexity of argumentation. We carried out preliminary experiments on abstracting problems and constructing reasonable arguments. Our methods are expected to enable developers to analyze problems in a reasonable manner with less complexity and thus make problem analysis easier.

In many application domains, continuous operation is a desirable attribute for software-intensive systems. As the environment or system requirements change, so the system should change and adapt without stopping or unduly disturbing its operation. There is, therefore, a need for sound engineering techniques that can cope with dynamic change. In this paper we address the problem of dynamic update of controllers in reactive systems when the specification (environment assumptions, requirements and interface) of the current system changes. We present a general approach to specifying correctness criteria for dynamic update and a technique for automatically computing a controller that handles the transition from the old to the new specification, assuring that the system will reach a state in which such a transition can correctly occur. Indeed, using controller synthesis we show how to automatically build a controller that guarantees both progress towards update and safe update. Seven case studies have been implemented to validate the approach.

Over the past decade, we have seen a resurgence in the Datalog language in different computing areas for solving a number of nontrivial problems. In this paper we introduce a novel resolution approach to solve Datalog programs. We present a version of the technique that works on plain Datalog programs. We have developed an abstract rewriting formalism to create a functional resolution process for Datalog. The resolution approach translates the Datalog resolution strategy into a fix-point abstract rewriting equation system. Being an abstract rewriting formalism, every equation of the system can be viewed as a function. Based on this fact, we also developed an optimization process that improves the initial rewriting equation system. The optimization process generates an equation system that computes the solutions much more efficiently. Well known optimizations such as strength reduction or memoization have been used. We also developed a prototype compiler that encodes the optimized equation system into a solver. Experimental results obtained with the solver suggest execution times several orders of magnitude better than modern Prolog solvers like YAP or XSB and usually one order of magnitude faster than state-of-the-art Datalog solvers such as BDDBDDB and DLV.

Feedback-directed random test generation is a widely used technique to generate random method sequences. It leverages feedback to guide generation. However, the validity of feedback guidance has not been challenged yet. In this paper, we investigate the characteristics of feedback-directed random test generation and propose a method that exploits the obtained knowledge that excessive feedback limits the diversity of tests. First, we show that the feedback loop of feedback-directed generation algorithm is a positive feedback loop and amplifies the bias that emerges in the candidate value pool. This over-directs the generation and limits the diversity of generated tests. Thus, limiting the amount of feedback can improve diversity and effectiveness of generated tests. Second, we propose a method named feedbackcontrolled random test generation, which aggressively controls the feedback in order to promote diversity of generated tests. Experiments on eight different, real-world application libraries indicate that our method increases branch coverage by 78% to 204% over the original feedback-directed algorithm on large-scale utility libraries. Copyright is held by the owner/author(s).

One of the applications of Cyber-Physical Systems (CPSs) is the Smart Homes. In Smart Homes, multiple apps operate the sensors and actuators to provide rich user experience in a living environment. Because actuators are entities that affect the surrounding environment, conflicts may occur if two or more apps are running simultaneously, especially when they try to use a single actuator or when they use different actuators causing different effects. There have been attempts to resolve these conflicts at app installation time. However the state-of-the-art solutions can detect conflicts only if the apps actuate on devices with conditions based on time, and resolute conflicts by creating a total order between all apps, regardless of the situations of the conflicts. In this paper, we create a Kripke structure to detect conflicts by model-checking the assertion "no two apps use actuators to create different effects at the same location". Our proposed system, which provides install-time conflict detection, enables detection of application conflicts triggered by conditions based on events. In addition, it supports users in prioritising apps by reducing the number of conflicts by dividing them into groups of the same situation which are meaningful to the users. By prioritising apps for each situation, rather than creating a total order, our system allows the apps to run in a more flexible way.

Mobile applications (apps) are software developed for use on mobile devices and made available through app stores. App stores are highly competitive markets where developers need to cater to a large number of users spanning multiple countries. This work hypothesizes that there exist country differences in mobile app user behavior and conducts one of the largest surveys to date of app users across the world, in order to identify the precise nature of those differences. The survey investigated user adoption of the app store concept, app needs, and rationale for selecting or abandoning an app. We collected data from more than 15 countries, including USA, China, Japan, Germany, France, Brazil, United Kingdom, Italy, Russia, India, Canada, Spain, Australia, Mexico, and South Korea. Analysis of data provided by 4,824 participants showed significant differences in app user behaviors across countries, for example users from USA are more likely to download medical apps, users from the United Kingdom and Canada are more likely to be influenced by price, users from Japan and Australia are less likely to rate apps. Analysis of the results revealed new challenges to market-driven software engineering related to packaging requirements, feature space, quality expectations, app store dependency, price sensitivity, and ecosystem effect.

Service-Oriented Computing enables the composition of loosely coupled services provided with varying Quality of Service (QoS) levels. Selecting a near-optimal set of services for a composition in terms of QoS is crucial when many functionally equivalent services are available. As the number of distributed services, particularly in the cloud, is rising rapidly, the impact of the network on the QoS keeps increasing. Despite this, current approaches do not differentiate between the QoS of services themselves and the network. Therefore, the computed latency differs from the actual latency, resulting in suboptimal QoS. Thus, we propose a network-aware approach that handles the QoS of services and the QoS of the network independently. First, we build a network model in order to estimate the network latency between arbitrary services and potential users. Our selection algorithm then leverages this model to find compositions with a low latency for a given execution policy. We employ a self-adaptive genetic algorithm which balances the optimization of latency and other QoS as needed and improves the convergence speed. In our evaluation, we show that our approach works under realistic network conditions, efficiently computing compositions with much lower latency and otherwise equivalent QoS compared to current approaches.

Method names are important for the software development process. It has been shown by some studies that the quality of method names affects software comprehension. In response, some approaches that evaluate comprehensibility of method names have been proposed. However, the effectiveness of existing approaches is limited because they focus on part of names. To deal with the limitation, we propose a novel approach for evaluating comprehensibility of method names and suggesting comprehensible method names using n-gram models. We implemented a prototype tool and conducted two experiments as a case study. Our experiments show that our approach can correctly evaluate 75% method names and successfully suggest 92% actual third words of method names.

Energy efficiency of cloud data centers is of great concern today and has been tackled by many researchers. Dynamic VM placement is a well-known strategy to improve energy efficiency of a data center. Virtual machines (VMs) under light load are consolidated into a small number of physical machines (PMs) to turn idle PMs into low-power states. Although live migration is essential for dynamic VM placement, former studies have not yet revealed how energy overhead of live migration has impact on energy efficiency of dynamic VM placement. To tackle this problem, we conducted integrated simulation of energy overhead of live migration and dynamic VM placement using SimGrid. We used three dynamic VM placement policies and two live migration mechanisms (existing pre-copy and an accelerated mechanism invented by us) to thoroughly evaluate the energy overhead. The results showed that in the worst case energy overhead of live migration occupies 5.8% of total energy consumption of a data center.

Wireless sensor networks (WSNs) play important roles in systems that interact with the real world (e.g., cyber-physical systems and internet of things). To mitigate the complex nature of WSNs, many platforms at different abstraction levels (e.g., abstraction of hardware, communications, and individual nodes) have been proposed in the last decade. WSNs in different environments might employ different platforms to satisfy nonfunctional requirements (NFRs) because the diversity of platforms results in trade-offs of NFRs and the quality of WSN heavily depends on the environment it runs. Although WSN software should be highly portable, existing approaches only support porting between operating systems and not more abstract middleware. Herein we propose a methodology with a framework to capture various platforms in the WSN domain with platform-independent multi-level models. A case study demonstrates that our framework can port WSN software to platforms at different abstraction levels and adapt the software to the new platform to improve performance.

The challenge of validating Asynchronous JavaScript and XML (Ajax) applications lies in actual errors exposed in a user environment. Several studies have proposed effective and efficient testing techniques to identify executable faults. However, the applications might have faults that are not executed during testing, but might cause actual errors in a user environment. Although we have investigated static methods for finding "potential faults" that seem to cause actual errors if executed, developers need to confirm whether or not the potential faults are actually executable. Herein, we propose a mutation-based testing method implemented in a tool called JSPreventer. Even if the potential faults are not easily executable in a given environment, our method mutates the applications until they are executable using two delay-based mutation operators to manipulate the timing of the applications handling interactions. Thus, JSPreventer provides executable evidences of the not-easily-executable faults for developers, if it reveals actual errors by testing the mutated applications. We applied our method to real-world applications and found actual errors that developers could debug to improve their reliability. Therefore, JSPreventer can help developers validate reliable real-world Ajax applications.

Virtualization techniques greatly benefit cloud computing. Live migration enables a datacenter to dynamically replace virtual machines (VMs) without disrupting services running on them. Efficient live migration is the key to improve the energy efficiency and resource utilization of a datacenter through dynamic placement of VMs. Recent studies have achieved efficient live migration by deleting the page cache of the guest OS to shrink the memory size of it before a migration. However, these studies do not solve the problem of IO performance penalty after a migration due to the loss of page cache. We propose an advanced memory transfer mechanism for live migration, which skips transferring the page cache to shorten total migration time while restoring it transparently from the guest OS via the SAN to prevent IO performance penalty. To start a migration, our mechanism collects the mapping information between page cache and disk blocks. During a migration, the source host skips transferring the page cache but transfers other memory content, while the destination host transfers the same data as the page cache from the disk blocks via the SAN. Experiments with web server and database workloads showed that our mechanism reduced total migration time with significantly small IO performance penalty.

Event-B provides a promising feature of refinement to gradually construct a comprehensive specification of a complex system including various aspects. It has unique difficulties to design complexity mitigation, while obeying Event-B consistency rules, among the potentially large possibilities of refinement plans. However, despite of the difficulties, existing studies on specific examples or high-level and intuitive guidelines are missing clear rationales, as well as principles, guidelines or methods supported by the rationales. In response to this problem, this paper presents a method for refinement planning from an informal/semiformal specification. By defining primitive rationales, the method can eliminate undesirable plans such as the ones failing to mitigate the complexity. In a case study on a popular example from a book, we derived an enough small number of valid plans only by using the general and essential rationales while explaining the one presented in the book.

Lightweight property-based testing tools are becoming popular these days. With property-based testing, developers can test properties of the system under test against large varieties of randomly generated inputs without writing test cases. Despite the advantages of property-based testing, current property-based testing tools have a major drawback: they require developers to write generator functions for user-defined types. This is because it is difficult for a tool to infer the possible values for the type. However, user-defined generators sometimes fail to find faults by only producing overly limited varieties of values. In this paper, we present a new property-based testing tool, called ArbitCheck, which automates object generation by adapting the feedback-directed random test generation technique. With the help of feedback-directed random test generation, ArbitCheck exhaustively generates possible values of user-defined types and tests properties with them, so that it can reveal faults that are hard to find with either manually written tests or existing property-based testing tools.

Primary task of wireless sensor networks is to deliver reliable and accurate information about the phenomena of interest. However, faults are a frequent occurrence and their accumulation affects the quality of service significantly. This leads to a shorter effective lifetime of the network. In this work, we propose a framework for the fault tolerance in sensory readings. The main concept is based on the observation of the pattern that faults leave in data behavior. Based on the duration, continuity and the impact, we propose a complete and consistent classification of faults as they can be observed in sensory readings independently of the underlying cause. Further, we propose that network learns a model of a fault for each faulty node from the past behavior. Each phase of the framework can be implemented with the use of different algorithms appropriate for the task. In this paper we present an instance that relies on neighborhood vote, time series analysis and statistical pattern recognition. Results so far confirm that the scheme works well for dense data-centric wireless sensor networks.

Live migration of virtual machines over a wide area network has many use cases such as cross-datacenter load balancing, low carbon virtual private clouds, and disaster recovery of IT systems. An efficient wide area live migration method is required because cross-datacenter connections have a narrow bandwidth. Page cache occupies a large portion of the memory of a Virtual Machine (VM) when it executes data-intensive workloads. We propose a new live migration technique, page cache teleportation, which reduces the total migration time of wide area live migration and has a low overhead. It detects the restorable page cache in the guest memory that has the same contents as the corresponding disk blocks. The restorable page cache is not transferred via the WAN but is restored from the disk image before the VM resumes. In this way, the IO performance degradation reduces after the migration. Evaluations show that page cache teleportation reduces the total migration time of wide area live migration and has a lower performance overhead than existing approaches.

In reinforcement learning tasks with continuous state-action, parameterized policy search has been known to be a powerful method. Applying NeuroEvolution (NE) to optimizing the policy represented by artificial neural network (ANN) is a particularly active research field. In most cases, NE algorithms cost a large amount of trial-and-error (episode) to optimize policies. However, due to time and cost constraints, researchers and practitioners cannot repeat a number of episodes on physical robots. Thus, choosing an efficient NE algorithm is a key to optimize policies with limited time and cost. In this work, our goal is to help users to choose an efficient NE algorithm. We compare and analyze sample efficiency of two successful state-of-the-art NE algorithms: CMA-NeuroES and NEAT in a gait generation task of a quadruped robot. Moreover, we run both algorithms with various initial topologies in order to analyze the performance difference between each topology. From experimental results, we show CMA-NeuroES outperforms NEAT regardless of initial topologies when the limited number of episodes can be executed. Additional experiments conclude that the optimization method for connection weights in NEAT results in its inferior performance to CMA-NeuroES, while a probability weighted averaging characteristic and self-adaptive factors make CMA-NeuroES to be advantageous.

Automatic image description is one of the challenging tasks of image recognitions. However, there are image descriptions that contain some too specific phrases that cannot be judged only from appearance of images. In this paper, we propose a novel approach to collect general phrases for generating image descriptions. On the assumption that there are high frequency phrases related to an query image in the image descriptions of similar images, we select nouns and their attribute phrases from the image descriptions of similar images based on their frequency. In order to evaluate the relevance of our image description, we conduct comparative experiments with existing approaches. Our experimental results show that our image descriptions are short, concise and visually relevant to query images. © 2013 ACM.

When developing asynchronous JavaScript and XML (Ajax) applications, developers implement Ajax design patterns for increasing the usability of the applications. However, unpredictable contexts of running applications might conceal faults that will break the design patterns, which decreases usability. We propose a support tool called JSVerifier that automatically verifies interaction invariants; the applications handle their interactions in invariant occurrence and order. We also present a selective set of interaction invariants derived from Ajax design patterns, as input. If the application behavior breaks the design patterns, JSVerifier automatically outputs faulty execution paths for debugging. The results of our case studies show that JSVerifier can verify the interaction invariants in a feasible amount of time, and we conclude that it can help developers increase the usability of Ajax applications.

Persistent trends like quickly changing production programs, increasing customer individual manufacturing and Sustainable Manufacturing create complex systems of objectives in manufacturing control. Service-oriented manufacturing systems and self-optimizing manufacturing resources offer the required flexibility to consider these objectives in accordance with the current organizational and economical situation. On the downside, this increase in flexibility make the control of manufacturing systems more difficult and presents new challenges regarding the scheduling. To meet these challenges, we developed scheduling framework that supports alternative process plans and considers the internal states trajectories of resources. In order to support the user in a complex decision-making environment, evolutionary multi-objective optimization is used to generate a set of relevant schedules and an interface to select the most appropriate schedule is provided. © 2011 Springer-Verlag.

Multi-agent systems (MASs) are one of the effective approaches for dealing with the recent increase in software complexity and their autonomy. In the MAS research community, there has recently been increasing interest in the adoption of requirements engineering techniques to bridge the gap between the system requirements and the system design. One of the most important tasks based on the requirements description in the MAS design activity is the extraction of roles, which are the fundamental components of multi-agent systems, from it. It is also important to comprehend the relative degree of responsibility of the individual roles. The comprehension helps the developer decide the system architecture and discuss the performance and stability of the system. We introduce the concept of importance as a quantitative metric and an evaluation framework for the extraction of a suitable role set for the system and the task assignment to these roles. The importance is propagated from the requirements to the roles through their assigned tasks. We demonstrate the effectiveness of our framework through a case study and show that our metric and evaluation framework help not only to identify the importance of each role, but also to determine the system architecture.

This paper introduces a declarative agent-oriented language for Ambient Intelligence - S-CLAIM - that allows programming reactive or cognitive mobile agents in a simple, easy-to-use manner while meeting AmI requirements. Based on a hierarchical representation of the agents, the language offers a natural solution to achieve context-sensitivity. S-CLAIM is light-weight and, being transparently underpinned by the JADE framework, allows deployment on mobile devices and easy interoperation with other components by means of web services. The usefulness of the proposed language for AmI is illustrated through a scenario and a demo featuring an AmI application in a Smart Room. (C) 2011 Published by Elsevier Ltd.

This paper introduces a declarative agent-oriented language for Ambient Intelligence - S-CLAIM - that allows programming reactive or cognitive mobile agents in a simple, easy-to-use manner while meeting AmI requirements. Based on a hierarchical representation of the agents, the language offers a natural solution to achieve context-sensitivity. S-CLAIM is light-weight and, being transparently underpinned by the JADE framework, allows deployment on mobile devices and easy interoperation with other components by means of web services. The usefulness of the proposed language for AmI is illustrated through a scenario and a demo featuring an AmI application in a Smart Room. (C) 2011 Published by Elsevier Ltd.

In this research, we investigate whether CoSyNE and CMA-NeuroES algorithms can efficiently optimize neural policy of a quadruped robot. Both of these algorithms are proven to optimize connection weights efficiently on Pole Balancing benchmark. Due to their good results on that benchmark, they are expected to be efficient on other control problems like gait generation. In this research we experimentally show that CMA-NeuroES have higher scalability to optimize Artificial Neural Networks for generating gaits of quadruped robots in comparison with CoSyNE. The results can be helpful for researchers and practitioners to choose the optimal Neuroevolution algorithm for generating gaits. © 2012 Springer-Verlag.

Self-Adaptive systems, which enable runtime adaptation, are promising ways of dealing with environmental changes, including system intrusions or faults. Such software systems must modify themselves to better fit their environment. One of the main approaches to constructing such systems is to introduce multiple control loops. Software evolution is an essential activity for expanding this adaptation capability, and dynamic evolution has been envisaged as a way of systems adapting themselves at runtime. In this paper, we establish a development process to deal with dynamic evolution. We devise a goal model compiler to generate models for designing dynamic evolutions and a programming framework that supports dynamic deployment of control loops. We experimentally applied our approach to a system and discuss how our compiler and framework support dynamic evolution of self-Adaptive systems. © 2012 IEEE.

In Infrastructure-as-a-Service datacenters, the placement of Virtual Machines (VMs) on physical hosts are dynamically optimized in response to resource utilization of the hosts. However, existing live migration techniques, used to move VMs between hosts, need to involve large data transfer and prevents dynamic consolidation systems from optimizing VM placements efficiently. In this paper, we propose a technique called "memory reusing" that reduces the amount of transferred memory of live migration. When a VM migrates to another host, the memory image of the VM is kept in the source host. When the VM migrates back to the original host later, the kept memory image will be "reused", i.e. memory pages which are identical to the kept pages will not be transferred. We implemented a system named MiyakoDori that uses memory reusing in live migrations. Evaluations show that MiyakoDori significantly reduced the amount of transferred memory of live migrations and reduced 87% of unnecessary energy consumption when integrated with our dynamic VM consolidation system. © 2012 IEEE.

Optimizing the Quality-of-Service (QoS) levels of a service workflow is essential for the user satisfaction in Service-oriented Computing. For that purpose, QoS computation models are applied to reflect the actual QoS experienced by the user during service execution. Current QoS models ignore the possible dependencies of QoS attributes, such as the dependency on the time of the execution or on the input data supplied to the service. Apart from that, composition approaches consider only single workflows during service selection, narrowing the number of possible compositions. Thus, we introduce a novel QoS model that covers QoS dependencies and discuss how this model can be used to consider multiple workflows at the same time. Moreover, we adopt a multi-objective optimization approach to offer solutions varying in QoS such as finishing time and price, allowing the user to make fine-grained decisions. © 2012 IEEE.

Service composition algorithms are used for realizing loosely coupled interactions in Service-Oriented Computing. Starting from an abstract workflow, concrete services are matched, based on their QoS, with the preferences and constraints of users. Current approaches usually only consider static QoS values and find a single solution consisting of one concrete service for each workflow task. In a business-to-business (B2B) environment, though, there are additional requirements for service compositions: 1) a high number of invocations, and 2) a high reliability. Thus, we introduce a probabilistic approach on the basis of a new QoS model to solve the composition problem for such long-term B2B service compositions. For each task and for every point in time, we determine the most appropriate services and backup services for a specific user. Thus, the selection depends on the actual response time and reliability, or recent invocation failures or timeouts. For that purpose, we propose an adaptive genetic algorithm that employs our QoS model and determines backup services dynamically based on the required reliability. Our evaluations show that our approach significantly increases the utility of long-term compositions compared with standard approaches in the envisioned B2B environments. © 2012 IEEE.

The technology for web services has facilitated composition of a new service by combining existing services. The resulting composite service is required to guarantee Quality of Service (QoS), such as price, in addition to the demanded function. Each composite service faces computationally-expensive service selection by exploring enormous service combinations for optimization of a utility function and satisfaction of global constraints. In addition, each concrete service has difficulties in determining QoS that is profitable while attractive for customers, or composite services. Specifically, information on rival services is generally secret and changeable, which is required for the optimal decision. In response to these problems, this paper proposes an algorithm for service selection using Vickrey auction. In the first phase of the proposed algorithm, the composite service selects some best concrete services through the reverse Vickrey auction, only considering the utility function. In the second phase, the global constraints are satisfied through adjustments based on the Vickrey auction. The proposed algorithm avoids full exploration of services combinations for efficient computation, while encouraging providers to declare their best QoS without caring about extra profit. © 2012 IEEE.

The concept of trust in web services mainly deals with the degree of belief that a client or a group of clients have over services functioning satisfactorily and providing the expected results. With services being invoked in composition with each other, computing the trust of the composition and selecting services that deliver the highest trust for it becomes a desired goal. In this paper we demonstrate how using Bayesian networks and its supporting queries, we can select the set of services among all candidates that would provide highest global trust. © 2012 IEEE.

Many developers have implemented native smartphone applications (NSAs) that have the same functionalities as those of existing web applications (WAs). They need to redesign web pages as views of NSAs owing to their constraints, such as compact displays. However, it can produce a NSA with low global navigability. We propose a framework that can support developers in designing view transitions of NSAs on the basis of WAs. We focus on web templates to leverage well-designed web page transitions. Our framework 1) extracts a page transition model from a WA to create candidate view transitions of a NSA, 2) provides an interface where developers design these views to solve the constraints, and 3) suggests design modifications to increase global navigability calculated by proposed criteria of navigation costs for users. After examining case studies, we concluded that our framework could support developers to design easy-to-navigate NSAs. © 2012 Springer-Verlag.

Model-driven development (MDD) facilitates the development of wireless sensor network (WSN) applications because MDD can deal with models at the abstraction level to the concrete level. In the MDD for WSN applications, the developers model the dataflow at the abstract level and model the designs of a communication and task assignment at the concrete level. In our previous work we proposed a MDD process for WSN applications with three domain specific languages (DSLs). However, we did not sufficiently evaluate the description capabilities of our DSLs. For that reason, we report case studies on real-world applications to prove the feasibility of our approach. Our DSL can be used to describe both the application logic and design decisions concerning the quality of data, which are adopted in target applications. Additionally, we demonstrate the effectiveness of the DSLs at multiple abstraction levels. © 2012 IEEE.

Web service composition provides a means of customized and flexible integration of service functionalities. Qualityof- Service (QoS) optimization algorithms select services in order to adapt workflows to the non-functional requirements of the user. With increasing number of services in a workflow, previous approaches fail to achieve a sufficient reliability. Moreover, expensive ad-hoc replanning is required to deal with service failures. The major problem with such sequential application of planning and replanning is that it ignores the potential costs during the initial planning and they consequently are hidden from the decision maker. Our basic idea to overcome this substantial problem is to compute a QoS optimized selection of service clusters that includes a sufficient number of backup services for each service employed. To support the human decision maker in the service selection task, our approach considers the possible repair costs directly in the initial composition. On the basis of a multi-objective approach and using a suitable service selection interface, the decision maker can select compositions in line with his/her personal risk preferences.

Service-Oriented Computing (SOC) enables the composition of loosely coupled services provided with varying Quality of Service (QoS) levels. Selecting a (near-)optimal set of services for a composition in terms of QoS is crucial when many functionally equivalent services are available. With the advent of Cloud Computing, both the number of such services and their distribution across the network are rising rapidly, increasing the impact of the network on the QoS of such compositions. Despite this, current approaches do not differentiate between the QoS of services themselves and the QoS of the network. Therefore, the computed latency differs substantially from the actual latency, resulting in suboptimal QoS for service compositions in the cloud. Thus, we propose a network-aware approach that handles the QoS of services and the QoS of the network independently. First, we build a network model in order to estimate the network latency between arbitrary services and potential users. Our selection algorithm then leverages this model to find compositions that will result in a low latency given an employed execution policy. In our evaluation, we show that our approach eficiently computes compositions with much lower latency than current approaches.

Although asynchronous technologies such as Ajax make Rich Internet Applications (RIAs) responsive, they can result in unexpected behavior due to nondeterministic client-side processing and asynchronous communication. One difficulty in understanding such erroneous behavior lies in the unpredictable contexts of the running system. Dynamic behavior analysis techniques do not help to verify the correctness of certain "blind spots" in the execution path. In this work, we present a static approach for extracting all possible state transitions described in source code from the RIAs. Our approach is based on the assumption that user, server and self interactions with the RIAs can change the states of the application. Our method consists of four steps: 1) using given specifications of Ajax relevant to interactions as rules, 2) creating a call graph, annotating interactions on it and extracting interaction controls, 3) abstracting the call graph to extract relationships among the interactions, and 4) refining the relationships with the interaction controls. By extracting the state machines of test scenarios of the correct and wrong behavior, it can help developers to pinpoint the statements in the source code that lead to the erroneous behavior. Our approach has been evaluated against a few experimental cases and we conclude that it can extract comprehensible state machines in a reasonable time. © 2012 IEEE.

Neuroevolutionary algorithms are successful methods for optimizing neural networks, especially for learning a neural policy (controller) in reinforcement learning tasks. Their significant advantage over gradient-based algorithms is the capability to search network topology as well as connection weights. However, state-of-the-art topology evolving methods are known to be inefficient compared to weight evolving methods with an appropriately hand-tuned topology. This paper introduces a novel efficient algorithm called CMA-TWEANN for evolving both topology and weights. Its high efficiency is achieved by introducing efficient topological mutation operators and integrating a state-of-the-art function optimization algorithm for weight optimization. Experiments on benchmark reinforcement learning tasks demonstrate that CMA-TWEANN solves tasks significantly faster than existing topology evolving methods. Furthermore, it outperforms weight evolving techniques even when they are equipped with a hand-tuned topology. Additional experiments reveal how and why CMA-TWEANN is the best performing weight evolving method.

Geographic information systems use databases to map keywords to locations. Currently, these databases are mostly created by a top-down approach based on geographic definitions. Problems are that (1) these databases only have information about addresses, location names, landmarks, and stores, and (2) if there are multiple candidate locations for a keyword, these databases do not have the information about which location is popular. A bottom-up approach which targets actual usage of keywords can address these problems. We propose a method to aggregate tagging data and extract locations related to a tag by using pairs of a tag and a geotagged resource. We use cooccurrence of a tag and a location and represent the locations related to a tag as a probability distribution over longitudes and latitudes. We apply our method to data on the photo sharing service Flickr. We experimentally confirm that our method can extract locations related to tags with high accuracy. Our bottom-up approach enables the extraction of location information that is unavailable using traditional top-down approaches.

Although asynchronous technologies such as Ajax make Rich Internet Applications (RIAs) responsive, they can result in unexpected behavior due to nondeterministic client-side processing and asynchronous communication. One difficulty in understanding such erroneous behavior lies in the unpredictable contexts of the running system. Dynamic behavior analysis techniques do not help to verify the correctness of certain "blind spots" in the execution path. In this work, we present a static approach for extracting all possible state transitions described in source code from the RIAs. Our approach is based on the assumption that user, server and self interactions with the RIAs can change the states of the application. Our method consists of four steps: 1) using given specifications of Ajax relevant to interactions as rules, 2) creating a call graph, annotating interactions on it and extracting interaction controls, 3) abstracting the call graph to extract relationships among the interactions, and 4) refining the relationships with the interaction controls. By extracting the state machines of test scenarios of the correct and wrong behavior, it can help developers to pinpoint the statements in the source code that lead to the erroneous behavior. Our approach has been evaluated against a few experimental cases and we conclude that it can extract comprehensible state machines in a reasonable time.

The concept of trust in web services mainly deals with the degree of belief that a client or a group of clients have over services functioning satisfactorily and providing the expected results. With services being invoked in composition with each other, computing the trust of the composition and selecting services that deliver the highest trust for it becomes a desired goal. In this paper we demonstrate how using Bayesian networks and its supporting queries, we can select the set of services among all candidates that would provide highest global trust. © 2012 IEEE.

The purpose of this study is to reduce the difficulties encountered when designing multi-agent systems (MAS). Although MAS are one of the more effective approaches for dealing with the recent increase in software complexity, they are themselves difficult to develop. We believe the difficulties in determining agent responsibilities and the organizational structure as the most significant obstacles to MAS development. In this paper, we propose a design framework for MAS, which includes restriction rules in the goal-oriented requirements description and a generator that transforms the restricted requirements description into a general MAS design model. We demonstrate the effectiveness of our framework through a case study and show how the framework can be used to construct MAS design models more precisely than conventional methods permit. © 2011 ACM.

The complexity of current software systems requires the ability to adapt at run-time, and the development of self-adaptive systems is one of the recent challenges for realizing dynamic adaptation. In this paper, we focus on the adaptation based on the components connection as a fundamental adaptation, and present our implementation framework for constructing self-adaptive systems on the basis of an agent platform. We reinforce the agent platform by adding some application program interface for behavior cooperation and its autonomic activation, and connect the behaviors with components in self-adaptive systems. We also introduce an implementation guideline: a way to identify the responsibilities for control loops and implementation patterns for these responsibilities. We also demonstrate the effectiveness of our framework and guideline through the results from our implementation experiments and show how they can be used to construct self-adaptive systems by using agent platforms.

Class evolution in object-oriented programming often causes so-called breaking changes, largely because of the rigidity of component interconnections in the form of explicit method calls and field accesses. We present a Java extension, Poplar, which we are currently developing. In Poplar, inter-component dependencies are expressed using declarative queries
concrete linking code, generated using a planning algorithm, replaces these at compile time. We show how Poplar can enable fully automatic integration of Java components through evolvable and statically checkable integration links, pointing the way to a new general composition method for object-oriented languages. © 2011 ACM.

An agile software development team relies on communication and collaboration to perform requirements engineering activities, rather than on dedicated analysis tools or documentation. Evidence from practice indicates that two simple physical artefacts (story cards and the wall), used in a particular and disciplined manner, and supported by appropriate social activity, are key to the success of co-located agile teams. However, little is known about this social activity or how communication and collaboration supports requirements activities in this setting. This paper reports an empirical study of a commercial agile team to investigate this issue. Using a combination of qualitative data collection and cognitive analysis techniques, we found evidence of gathering, evolving and clarifying requirements that are managed through patterns of communication. These patterns suggest that a form of situated conceptualization, which we have termed 'shared conceptualization', underpins the team's requirements engineering activities. © 2011 ACM.

Facing to the great number of wireless sensor/actuator devices, smart applications have an increasingly important requirement: autonomy. Besides autonomy in terms of energy, these devices have also to be functionally autonomous: they have to be self-discovered, self-(re-)configured and selfhealed. This paper presents a self-manageable autonomic platform for heterogeneous sensing systems. Based on a service oriented architecture and an Event-Condition-Action model, management services collect information from managed elements (e.g., sensors, proxies, gateways) and perform management actions according to user defined ECA rules. We define a generic event model that allows us covering a large set of events. Events are captured and processed by rule evaluators which then perform corresponding management actions on the sensors. We show with experimental results that the mechanism brings little overhead in terms of energy consumption and execution time. © 2011 IEEE.

Adaptive and service-oriented manufacturing proposes manufacturing systems which can be rapidly changed in accordance to changing production programs and customer individual production. Increasing customer specific manufacturing and new trends such as Sustainable Manufacturing create a complex system of objectives. Human dispatcher controlling these manufacturing systems must be properly supported to consider all required objectives. Due to the reduced insight into the adapting manufacturing systems, classical single optimization approaches with a rigid definition of a single objective function and hard optimization constraints are not appropriate any more. This paper introduces a decision making framework based on multi-objective scheduling. The decision making process consists of a multi-objective scheduling process and an interface for schedule selection. The interface combines the decision making approaches outranking and preference elicitation. © 2011 IEEE.

Self-optimizing mechatronic systems are a new class of technical system promising new levels of flexibility and utility in electro-mechanical systems. Planning is an important method to realize self-optimization, although today hardly used in mechatronics. In this context, planning is understood as search for a feasible sequence of operations which implements the execution of specific job assigned to a system. This search is a complex and time-consuming task. Hence, it is desirable to decompose the planning task into smaller sub problems according to paradigm of divide &amp
conquer and use problem specific solution methods. Unfortunately, possible planning sub problems in mechatronic systems cannot be considered isolated since sub modules influence each other. This paper introduces the application of a multi-agent-planning model based on cooperative objective functions that enable the coordinated solution of sub problems. © 2011 IEEE.

In order to develop Wireless Sensor Network (WSN) applications, it is necessary to develop prototypes in a low-cost way and to optimize application performance. Existing development approaches enable to develop a low-cost prototype by concealing the detail of WSN from the developers. However, there is a trade-off between the development cost of prototype and the description capability needed to optimize the application performance. We propose a Model-Driven Development (MDD) process to enable a low-cost prototyping and detailed optimization. To enable such a development process, we define modeling languages, which describe an application at three abstraction levels, and transformation rules, which transform models described by our modeling language to concrete one. Using our process, in prototyping, the developer describes a model by using the modeling language at the highest abstraction level and automatically obtains an executable model by using transformation rules. In addition, in optimizing, the developer can automatically obtain the models at more concrete abstraction level than the prototype by using transformation rules and modifies them in greater detail by using each modeling language. © 2011 ACM.

Education for cloud engineers is crucial in terms of innovation in the development of cloud technologies. We propose a new cloud platform based on open-source software that uses multi-clouds for the education. © 2011 Authors.

Self-adaptive systems have recently attracted attention because of their ability to cope with changing environments, including system intrusions or faults. Such software must modify itself to better fit its environment, and one of the approaches by which we expect this capability to be achieved is the introduction of multiple control loops to assess the situation and to determine whether a change in behaviors or configurations is necessary and how to implement the change. Development of such systems with multiple control loops complicates the task of identifying components, and could be greatly aided by appropriate tool support. In this paper, we propose an architectural compiler for self-adaptive systems, which generates architectural configurations from the goal-oriented requirements descriptions. We also present a framework for generating such configurations with this compiler and a pattern in the requirements description. We evaluate the framework experimentally and show that it helps to generate suitable configurations that have high performance, and that the compiler scales well to large input models. © 2011 ACM.

Separation of concerns is an important aspect of component-based development (CBD), and managing data is a primary concern in enterprise systems. In CBD methods, such as Catalysis and UML components, this concern is addressed by business components. Although a business component is self-contained, having no direct dependency on any of the other components, the data propagation between components may lead to indirect data dependencies across the business components, and grasping such dependencies at design-time is crucial to maintaining data consistency. In this paper we propose a method for data-flow analysis (DFA) of the business component model, in which the operational behavior is described using the Object Constraint Language (OCL) pre-postconditions. Traditional DFA techniques are aimed at procedural descriptions, while OCL is a declarative language whose essential properties include nondeterminism and incompleteness. In order to extract a data-flow from the OCL descriptions taking account of their semantics, our proposed method applies the idea of abstract interpretation. We also analyze the safety of our abstract interpretation technique, and discuss the usefulness and scalability of the method from a practical viewpoint. The proposed method, when used in conjunction with the inter-procedural DFA techniques, would allow us to extract the propagation and dependency of data across the business components automatically. © 2011 ACM.

Due to the increase in Web services, many recent studies have been addressing the service selection problem based on non-functional or quality aspects. Our study incorporates combinational use of functionally-equivalent services into the problem to compose an application of higher quality or with additional value. However, when such combinational use is introduced, computational cost for the service selection becomes much higher. In this work, we propose a set of methods that reduce the additional cost for the QoS (Quality of Service)-based service selection considering combinational use. This approach achieves low cost by considering only effective combinations. The experimental results show that it can reduce computational cost regardless of the number of services and whatever their QoS values are while keeping the effectiveness of combinational use. © 2011 IEEE.

With the steadily growing number of service providers the competition becomes more and more intense. In order to find a distinctive edge over other competitors, automatic service composition can be applied to further adapt to the requirements of the users. Most of the current composition approaches can be categorized as either planning or selection algorithms. The former automatically create workflows and tend to neglect Quality-of-Service (QoS) concerns, drawing compositions useless if user constraints are violated. Selection algorithms on the other hand optimize the QoS but provide no functional flexibility. In this paper we show how the strengths of both approaches can be combined by leveraging common characteristics of service registries. Therefore we utilize a data structure which arranges functionally similar services in clusters and computes the QoS of each cluster. Our planning tool composes workflows consisting of these clusters, taking the QoS of the clusters into account. This way, the utility in general and the reliability of the composed workflows are significantly increased. We prove the feasibility and the benefits of our functional clustering in our detailed evaluation. © 2011 IEEE.

Service-Oriented Architecture enables the composition of loosely coupled services provided with varying Quality of Service (QoS) levels. Given a composition, finding the set of services that optimizes some QoS attributes under given QoS constraints has been shown to be NP-hard. Therefore, heuristic algorithms are widely used, finding acceptable solutions in polynomial time. Still the time complexity of such algorithms can be prohibitive for real-time use, especially if the algorithms are required to run until they find near-optimal solutions. Thus, we propose a heuristic approach based on Hill-Climbing that makes effective use of an initial bias computed with Linear Programming, and works on a reduced search space. In our evaluation, we show that our approach finds near-optimal solutions and achieves a low time complexity. © 2011 IEEE.

Semantic web techniques have been leveraged in planning methods for automated service composition. Typically, inputs and outputs of services are described in abstract concepts for efficient and meaningful matching between output of one service and input of another. However, existing methods have not examined concrete data structures, which are essential for successful service interaction in common implementation architectures. To address the problem, this paper proposes a matching method that can be incorporated into existing planning methods to ensure consistency in concrete data structures. The proposed method applies a two-phase matching process to efficiently filter out services that do not match at the abstract level. It also applies a data structure to organize similar services according to their relationships for efficient matching during the planning process. © 2011 IEEE.

Pervasive applications incorporate physical components that are exposed to everyday use and a large number of conditions and external factors that can lead to faults and failures. It is also possible that application requirements change during deployment and the network needs to adapt to a new context. Consequently, pervasive systems must be capable to autonomically adapt to changing conditions without involving users becoming a transparent asset in the environment. In this paper, we present an autonomic mechanism for initial task assignment in sensor networks, an NP-hard problem. We also study on-line adaptation of the original deployment which considers real-time metrics for maximising utility and lifetime of applications and smooth service degradation in the face of component failures. © 2011 IEEE.

In order to adjust to changing environments and internal states, self-adaptive systems are enabled to autonomously adjust their behaviour. The motive is to achieve better performance while minimising human effort in setting up and maintaining these systems. Ensuring correct functionality across a system's lifetime has been largely addressed. Optimisation of their performance, however, has received little attention. This paper presents an approach that applies goal modelling and decision making theory to calculate the quality of a system's performance in terms of a given configuration's utility with respect to its current environment. Thereby functionally valid configurations can be evaluated within the self-adaptive loop. The approach increased human players' performances in experiments based on a computer game. These results suggests that utility modelling is a promising approach for optimising the quality of behaviour in self-adaptive system.

A "shared" wireless sensor network (WSN) where multiple users deploy multiple tasks requires a mechanism for resource arbitration. This arbitration can be viewed as a problem with determining how best to assign sensors to tasks. The previous approaches only dealt with energy used for sensing
however, experiments have shown that the energy used for communication must be dealt with within the context of a WSN. In this paper, we propose a novel formulation of this problem and a distributed assignment algorithm based on heuristics that takes into account path information between the assigned node and the base station. We take advantage of the "reactive" nature of the system and piggyback path information on task queries. We can expect higher utilization of the network in comparison with previous approaches by preserving routes through which sensing data run. The results of software simulations revealed that our assignment algorithm is more energy-efficient than the previous one that does not exploit information about the path. © 2011 IEEE.

Over the past years service-oriented architectures have been widely adopted by stakeholders from research and industry. Since the number of services increases rapidly, effective methods are required to automatically discover and compose services according to user requirements. For this purpose, machine-understandable semantic annotations have to be applied in order to enable logical reasoning on the functional aspects of services. However, current approaches are not capable of composing workflows in reasonable time, except for planning tools that require domain-dependent heuristics or constrain the expressiveness of the description language. In addition to that, these tools neglect alternative plans, concealing the danger of creating a workflow having insufficient reliability. Therefore, we propose an approach to efficiently pre-cluster similar services according to their parameters. This way the search space is limited and vulnerable intermediate steps in the workflow can be effectively avoided.

Quality of Services (QoS) plays an essential role in realizing user tasks by service composition. Most QoS-aware service composition approaches have ignored the fact that QoS values can depend on the time of execution. Common QoS attributes such as response time may depend for instance on daytime, due to access tendency or conditional Service of Level Agreements. Application-specific QoS attributes often have tight relationships with the current state of resources, such as availability of hotel rooms. In response to these problems, this paper proposes an integrated multi-objective approach to QoS-aware service composition and selection.

Service-Oriented Architecture enables the composition of loosely coupled services provided with varying Quality of Service (QoS) levels. Given a composition, finding the set of services that optimizes some QoS attributes under given QoS constraints has been shown to be NP-hard. Until now the problem has been considered only for a single execution, choosing a single service for each workflow element. This contrasts with reality where services often are executed hundreds and thousands of times. Therefore, we modify the problem to consider repeated executions of services in the long-term. We also allow to choose multiple services for the same workflow element according to a probabilistic selection policy. We model this modified problem with Linear Programming, allowing us to solve it optimally in polynomial time. We discuss and evaluate the different applications of our approach, show in which cases it yields the biggest utility gains, and compare it to the original problem.

Geographic routing protocols exploit node positions on the Euclidean plane to route packets in multi-hop networks. Their potential lies in forgoing the overhead of building routing structures for instance in the form of link-state tables. At the same time their performance suffers from local dead ends and missing or inaccurate node coordinates. These issues have been addressed by various means, most notably by falling back to face routing on a planarized network graph or to a backup routing infrastructure such as a minimum spanning tree. Existing solutions however are not geared towards finding efficient paths or result in a considerable often upfront and global - communication overhead.
We propose assisting geographic routing adaptively by resorting to an on-demand route discovery only when and where it becomes necessary to sustain its greedy forwarding functionality. Simulating practically relevant qualities of dead ends and location inaccuracies, we show how the overhead of our method to deal with such cases remains localized and limited. We claim that our results make geographic routing more practicable particularly in wireless sensor networks that are deployed in immobile large-scale meshes and characterized by locally varying network conditions.

Planning is an important method in self-adaptive systems. Existing approaches emphasize the functional properties of the systems but do not consider possible alternative adaptations resulting in system functionality with different grades of quality. In compositional adaptation, the adaptation process should identify not only a feasible system configuration, but a good one. In safety-critical systems such as cars, the adaptation process has to fulfill special requirements. The sequence of reconfiguration activities has to maintain constraints over the entire state trajectory defined by the adaptation process, e.g., that certain processes are always running or even a minimal number of redundant instances. At the same time, in modern cars, many optional processes, such as learning of the engine model or optimization of control processes, improve the performance of the car. Possible optimization objectives are fuel consumption, driving comfort, and wear. Thus, this paper introduces a model of a self-adaptation process by reconfiguration, which considers the quality of alternative configurations. Furthermore, a planning process is introduced that generates a sequence of reconfiguration activities, which result in good configuration. The introduced process can be used to maintain the basic system functionality and also to select the currently most appropriate task implementations and optional tasks to run in a recovered system, e.g. after hardware failures. © 2010 IEEE.

The Business Process Execution Language (BPEL) has become the standard in web service composition, so that been adopted by industries to create mission critical services. The business process reliability especially business process consistency when some services failed is critical to composite services especially involving various organizations. However, it is difficult to conduct business process reliability testing for composite services due to complex business process in service composition, remote deployed services and long time testing duration. Little research is done to test fault tolerance capabilities of composite services only from low level. This paper proposes a technique on how to test the reliability of composite service defined in BPEL from the view of business semantics with little cost using fault injection. We present an approach for reliability testing of web services by using service stubs with semantic faults instead of real services which can be placed at service provider side or service consumer side. Dislike existing studies, we focus on how to find the reliability problems associating with business process - called semantics as the problems are not pure coding error but faults related to business process. In addition, the behavior of composite services in BPEL is analyzed when there are faults in orchestrated services invoked. Finally, a case study is given to show the whole process of reliability testing for composite web service. © 2010 IEEE.

Geographic information systems use databases to map keywords to places. These databases are currently most often created by using a top-down approach based on the geographic definitions. However, there is a problem with this approach in that these databases only contain location definitions such as addresses and place names, which does not allow for searches using keywords other than these words. Additionally, they do not give any information on the popularity, e. g., which is more popular among the places indexed by the same keyword. A bottom-up approach, based on the actual usage of words, can address these problems. We propose a method to aggregate tagging data and extract places related to a tag using the pair of a tag and a geo-tagged photo. We target the co-occurrence of a tag and the geolocation and represent the places related to a tag as a probability distribution over the longitudes and latitudes. We applied our method to data on the photo sharing service Flickr and experimentally confirmed that our method made it possible to highly-accurately extract places related to tags. Our direct bottom-up approach enables the extraction of place information that is not obtained by using traditional top-down approaches.

We propose an approximation method to answer point-to-point shortest path queries in undirected edge-weighted graphs, based on random sampling and Voronoi duals. We compute a simplification of the graph by selecting nodes independently at random with probability p. Edges are generated as the Voronoi dual of the original graph, using the selected nodes as Voronoi sites. This overlay graph allows for fast computation of approximate shortest paths for general, undirected graphs. The time-quality tradeoff decision can be made at query time. We provide bounds on the approximation ratio of the path lengths as well as experimental results. The theoretical worst-case approximation ratio is bounded by a logarithmic factor. Experiments show that our approximation method based on Voronoi duals has extremely fast preprocessing time and efficiently computes reasonably short paths.

Efficient object searching mechanisms are essential in large-scale networks. Many studies have been done on distributed hash tables (DHTs), which are a kind of peer-to-peer system. In DHT networks, we can certainly get the desired objects if they exist. However, multi-word searches generate much communication traffic. Many studies have tried to reduce this traffic by using bloom filters, which are space-efficient probabilistic data structures. In using such filters, all nodes in a DHT must share their false positive rate parameter. However, the best false positive rate differs from one node to another. In this paper, we provide a method of determining the best false positive rate, and we use a new filter called a flexible bloom filter, to which each node can set the approximately best false positive rate. Experiments showed that the flexible bloom filter was able to greatly reduce the traffic.

This paper presents a middleware that aims to respond to the increasing management needs of networked sensing devices, such as remote software deployment, dynamic configuration and real-time performance monitoring and tuning. These are essential functions for building adaptable systems providing high quality of service. Furthermore, autonomic management bears particular importance for large scale systems having timely response requirements. Our middleware allows creating high-level policies that describe the actions to be autonomously performed when interesting events occur in the system. The policies are formulated as Event-Condition-Action (ECA) rules. They are created by using UML-like diagrams and can be deployed at any level of the distributed architecture of the system.

Redundancy suppression is a network traffic compression technique that, by caching recurring transmission contents at receiving nodes, avoids repeatedly sending duplicate data. Existing implementations require abundant; memory both to analyze recent traffic for redundancy and to maintain the cache. Wireless sensor nodes at the same time cannot provide such resources due to hardware constraints. The diversity of protocols and traffic patterns in sensor networks furthermore makes the frequencies and proportions of redundancy in traffic unpredictable. The common practice of narrowing down search parameters based on characteristics of representative packet traces when dissecting data for redundancy thus becomes inappropriate. Such difficulties made us devise a novel protocol that conducts a probabilistic traffic analysis to identify and cache only the subset of redundant transfers that yields most traffic savings. We verified this approach to perform close enough to a solution built on exhaustive analysis and unconstrained caching to be practicable.

Agent platforms have recently attracted attention for use as a basis for self-* systems development because it provides a mechanism for autonomous functionalities. From among these platforms, JADE allows developers to describe concurrent behaviors on it, and this can be a foundation of constructing the multi-processes on self-* systems. This paper shows an overview of our approach for implementing highly collaborative behaviors by introducing a component style behavior model and its life cycle on the basis of the agent platform.

Previous research has indicated that work artefacts commonly used by agile teams capture progress information, while functional aspects such as requirements are developed and sustained through the team's social interactions and communication channels. This paper reports an initial empirical study to investigate the relationship between agile work artefacts and communication during stand-up meetings and pair programming sessions, specifically focusing on gathering and clarifying requirements. Using Bateson's communication theory, we found that the work artefacts, and other individuals form an external event system which supports Agile teams during the gathering and clarifying of requirements. Using this communication theory together with Clancey's situated cognition, we predict that if the two do not exist together throughout the interactions, then teams members will form discoordinated actions together.

Niching schemes, which sustains population diversity and let an evolutionary population avoid premature convergence, have been extensively studied in the research field of evolutionary algorithms. Neuroevolutionary (NE) algorithms, such as NEAT, have also benefitted from niching. However, the latest research indicates that the use of genotypeor phenotype-similarity-based niching schemes in NE algorithms is not highly effective because these schemes have difficulty sustaining the behavioral diversity in the environment. In this paper, we propose a novel niching scheme that takes into consideration both the phenotypic and behavioral diversity, and then integrate it with NEAT. An experimental analysis revealed that the proposed algorithm outperforms the original NEAT for various problem settings. More interestingly, it performs especially well for problems with a high noise level and large state space. Since these features are common in problems to which NEAT is applied, the proposed algorithm should be effective in practice. Copyright 2010 ACM.

Since the emergence of sensor oriented applications, sensor data management has become a very active research domain. We can distinguish three classes of solutions in this area, which we will explore in this chapter. The first is sensor networks which provide distributed processing of sensor data. The second is data stream management systems which are centralized systems that deal with stream data flowing from sensors. And finally, some hybrid approaches have also recently appeared which aim to integrate these two different types of solutions. This chapter provides an overviewof these three groups of proposals and discusses their approach to deal with issues such as scalability of sensing systems, heterogeneity of sensors and processing complex operations on sensor data stream. © 2010 Springer-Verlag Berlin Heidelberg.

Over the past years service-oriented architectures have been widely adopted by stakeholders from research and industry. Since the number of services increases rapidly, effective methods are required to automatically discover and compose services according to user requirements. For this purpose, machine-understandable semantic annotations have to be applied in order to enable logical reasoning on the functional aspects of services. However, current approaches are not capable of composing workflows in reasonable time, except for planning tools that require domain-dependent heuristics or constrain the expressiveness of the description language. In addition to that, these tools neglect alternative plans, concealing the danger of creating a workflow having insufficient reliability. Therefore, we propose an approach to efficiently pre-cluster similar services according to their parameters. This way the search space is limited and vulnerable intermediate steps in the workflow can be effectively avoided.

Wireless sensor networks (WSN) consist of spatially distributed nodes that monitor physical conditions. In the past, most WSNs have been designed with a single specific application in mind. Recent developments however are expanding the applicability of WSNs and are increasing the demand for deploying multiple applications simultaneously. To host multiple applications in a single WSN, current solutions provide mechanisms for components to be dynamically deployed to nodes. However, two issues make the present form of dynamic deployment impractical for applications involving distributed collaboration and the redeployment of multiple distributed components. For one, existing works lack a suitable architecture for cooperation and interaction between components in WSNs. Another problematic aspect is the insufficiency of current methods in efficiently deploying multiple components throughout the network. To address these issues, we propose an architecture based on multiple components that have specific responsibilities in regard to deployment and a generative approach for dynamic deployment of such components.

In large-scale sensor networks, sensor nodes are at high risk of being captured and compromised. Once a sensor node is compromised, all the secret keys, data, and code stored on it are exposed to the attacker. The attacker can insert arbitrary malicious code in the compromised node. Moreover, he can easily replicate such code in a large number of clones and deploy them on the network. This node replication attack can form the basis of a variety of attacks such as DoS attacks and Sybil attacks. In the related studies, as a means of detecting compromised nodes, each node reports its neighbor's ID and location to a witness node with some probability p. The value of p is determined beforehand or from only the number of neighbor nodes. In this paper, we change p according to the locations of nodes. We aim to increase the detection rate of replicated node attacks and decrease the amount of messages. Our analysis and simulations demonstrate that using our protocol in combination with the methods of other studies is more effective than using the methods of the related studies by themselves. Copyright 2009 ACM.

As a variety of digital services are provided through networks, more and more efforts are made to ensure dependability of software behavior implementing set-vices. Formal methods and tools have been considered as promising means to support dependability in complex software systems during the development. On the other hand, there have been serious doubts on practical applicability of formal methods. This paper overviews the present state of formal methods and discusses their applicability, especially focusing on two representative methods (SPIN and B Method) and their recent industrial applications. This paper also discusses applications of formal methods to dependable networked software.

With the emergence of sensors in applications in which the quality of service requirements are high (e.g., industrial, medical, domotic), management of these sensing devices gains an increasing importance. However, management issues are still little explored in this context. This demonstration presents our solution for dynamically managing networked heterogeneous sensing devices. The solution is based on a service oriented middleware that provides generic management operations for configuration, software management and performance monitoring of sensing devices. Copyright © 2009 ACM.

As many laws are concerned with information systems, each organization needs to carefully examine a law and determine technical requirements as well as its operational policies with sufficient concreteness. Legal interpretations essentially affect decisions made in refining goals, or making goals more concrete, that are directly or indirectly established by the law. As common and conventional interpretations are gradually identified and become widespread through appearances of cases and guidelines, goal refinement relationships need to be constantly managed and adjusted to the latest legal interpretations. This paper discusses an initial approach to management of legal interpretations together with goal-oriented requirements engineering, through a motivating example of a Japanese law on trade secrets. Specifically, this study proposes a metamodel for legal interpretation. In the metamodel, legal interpretations are modeled as refinement relationships between defi-nitions of concepts or terms and then analyzed by matching with instances. Legal interpretations can then be woven into goal trees as criteria of goal refinement.

In order to make practical use of formal methods, it is not sufficient for engineers to obtain general, fundamental knowledge of the methods and tools. Actually, it is also necessary for them to carefully consider their own contexts and determine adequate approaches to their own problems. Specifically, engineers need to choose adequate methods and tools, determine their usage strategies, and even customize or extend them for their effective and efficient use. Regarding the point, this paper reports and discusses experiences on education of formal methods in the Top SE program targeting software engineers in the industry. The program involves education of a variety of scientific methods and tools with group exercises on practical problems, allowing students to compare different approaches while understanding common principles. In addition, the program involves graduation studies where each student identifies and tackles their own problems. Statistics on problem settings in the graduation studies provide interesting insights into what top-level engineers tackles after learning formal methods.

Formal methods allow to verify several properties of specifications and implementations. Intra-specification consistency means that a specification does not contradict itself. When specifications evolve over time, one also wants to check inter-specification consistencies, which mean that specifications defined earlier in the development cycle also hold at a later point in time.
VDM++ is a popular and easy-to-use formal specification language. It uses testing instead of formal proofs to validate the consistency of specifications. The strictness of validations thus depends on the completeness of the corresponding test suites. Unfortunately, VDM++ does not support the verification of inter-specification consistencies. We define VDM-R, an extension of VDM++, which allows to annotate relationships between specifications. We also provide the tool VR2EvtB to translate from VDM-R to Event-B. Using an Event-B verifier, we can then formally validate intra- and inter-specification consistencies in an almost fully-automated process.

Many facility location problems are concerned with minimizing operation and transportation costs by partitioning territory into regions of similar size, each of which is served by a facility. For many optimization problems, the overall cost can be reduced by means of a partitioning into balanced subsets, especially in those cases where the cost associated with a subset is superlinear in its size. In this paper, we consider the problem of generating a Voronoi partition of a discrete graph so as to achieve balance conditions on the region sizes. Through experimentation, we first establish that the region sizes of randomly-generated graph Voronoi diagrams vary greatly in practice. We then show how to achieve a balanced partition of a graph via Voronoi site resampling. For bounded-degree graphs, where each of the n nodes has degree at most d, and for an initial randomly-chosen set of s Voronoi nodes, we prove that, by extending the set of Voronoi nodes using an algorithm by Thorup and Zwick, each Voronoi region has size at most 4dn/s+1 nodes, and that the expected size of the extended set of Voronoi nodes is at most 2s log n.

We propose an approximation method to answer point-to-point shortest path queries in undirected graphs, based on random sampling and Voronoi duals. We compute a simplification of the graph by selecting nodes independently at random with probability p. Edges are generated as the Voronoi dual of the original graph, using the selected nodes as Voronoi sites. This overlay graph allows for fast computation of approximate shortest paths for general, undirected graphs. The time-quality tradeoff decision can be made at query time. We provide bounds on the approximation ratio of the path lengths as well as experimental results. The theoretical worst-case approximation ratio is bounded by a logarithmic factor. Experiments show that our approximation method based on Voronoi duals has extremely fast preprocessing time and efficiently computes reasonably short paths.

Application software in pervasive computing is required to control devices embedded in the environment by being aware of the contexts on which effectiveness of the devices depend. Developers face difficulties to enumerate involved physical prerequisites for effective use of devices and undesirable situations to be avoided, as well as define consistent behaviors of the application software. This study provides a theoretical framework for formal modeling of requirements, assumptions and behaviors for application software in pervasive computing. This study specifically focuses on prerequisites for physical (visual, audio, etc.) interactions, which are defined and examined in terms of scopes and their relationships not limited to tree structures. This study also explores analysis and verification based on the formal modeling, using of an existing reasoner.

Considerable research has been done on different aspects of sensor networks. However management issues for these devices are still little explored. Nonetheless, with the increasing number of heterogeneous distributed sensors in various application domains, their management gains more and more importance, in particular for domains where requirements in terms of quality service, reliability, security and integrity are high, e.g., industrial, medical and domotics. This paper promotes an integrated management solution that covers domains such as network, system, application and device management. It first gives a brief state of the art of management solutions for traditional computer systems and sensor networks, then from a device management point of view, it presents challenges and possible solutions for generic networked sensing device management.

Distributed hash tables (DHT) are used for data management in P2P environments. However, since most hash functions ignore relations between items, DHTs are not efficient for operations on related items. In this paper, we modify a DHT into a distributed array (DA) that enables efficient operations on logical arrays. The array elements of a DA are placed in a P2P overlay network according to a simple rule such that the load is balanced and the number of messages required to access elements sequentially is reduced. The number of messages required for array operations is much smaller than that for operations on DHTs. We demonstrate this theoretically and experimentally.

This paper proposes 2G, a flexible and energy-efficient data collection protocol for sensor networks for increasing network lifetime. To this end, it integrates self-organizing data aggregation mechanisms based on geographical and cluster-based routing, and transaction cluster-head (TCH). A TCH is a location-based role, dynamically assigned to a node for the duration of handling a request-response transaction that targets its region of the network. TCH nodes collect raw sensor readings from their local regions and forward the answers containing aggregated data using geographical routing. A prototype of 2G was implemented on MICAz motes, and experimental results in realistic conditions proved that data collection reaches significantly higher delivery rates than with GEAR, the geographical routing protocol leveraged by 2G. Additionally, simulation results for larger scale networks demonstrate that 2G outperforms GEAR in terms of network lifetime. Copyright 2009 ACM.

The development of wireless sensor networks deals with several difficulties, including time, cost and complexity of testing. In particular, indoor environment poses several specific constraints on radio wave propagation due to density of obstacles. This must be taken into account if we want to discover and validate network configurations and communication paths. We suggest the use of virtual worlds, exploiting their inherent features for modeling of 3D environment, to simulate wireless sensor networks in order to deal with this problem. We have created an initial version of one such tool, which supports discovery and testing of configurations and communication paths within indoor wireless sensor networks. The validity of our approach was confirmed through experiments performed in this tool, in parallel with real-world experiments in a similar setting.

Multi-agent systems need protocols to coordinate among agents implemented by different owners. However specifying coordination protocols for many participating agents is a complex task. A protocol composition approach, which can reduce the complexity of specifying such a coordination protocol, must specify how to compose coordination protocols in a composition configuration. Current protocol compositions cannot sufficiently reduce the complexity because composing a protocol several times requires the specification of too many configurations. We propose a protocol composition approach that can specify composition configurations in an abstract way. We assign metadata to the messages in a coordination protocol and use the metadata to specify the configuration. An abstract configuration using metadata can be applied to various protocol compositions and can reduce the number of specifications required for configuration composition.

Event detection techniques are crucial for environmental monitoring and object tracking applications in wireless sensor networks. Event detection requires sensor readings to he collected from multiple sensors, and as sensors have limited resources, their readings should he retrieved efficiently. Existing aggregation-based event detection methods, however, require all sensors in the network to transmit their readings, which results in high energy consumption for the network. We propose an energy-efficient event detection technique for estimating the state of the whole environment based on only some of the sensor readings and use a contour map to represent the outline of the environment. To detect events in 3D environments, we modify an existing 2D contour mapping algorithm, extending it for 3D environments. By simulation, we show how our event detection technique is more energy-efficient than existing solutions that take readings from all sensors. We evaluated our method from the point of energy efficiency and found that it improves the energy efficiency of event detection in 3D wireless sensor networks.

Model checking is a powerful technique for verifying the correctness of a system's specification. But even when the specification has beet? verified to he correct, there is still the question of whether the specification covers all the expected behaviors. One of the most important issues for verification is the sufficiency Of verification items. In model checking, specification-level properties such as reachability are well-studied, but the sufficiency of a specification against the preceding requirements still remains a challenge. In this paper, we propose a model-checking process with goal oriented requirements analysis, in which goal descriptions in a natural language are systematically refined into linear temporal logic formulae. Furthermore, the covet-age of the verification result can be evaluated against the goal model. We developed a tool that supports the process, and applied it to an example. This process lowers the technical barriers to model checking and improves the sufficiency of system verification.

In e-Business, agents need to coordinate with each other Coordination protocols that specify the defining orders of message passing are very important. The scale of e-Business grows with the advancement of technology, and the number of agents involved continues to increase. Specifying the coordination protocols for so many participating agents is a complex task. A coordination protocol composition approach reduces the complexity of specifying such a coordination protocol. It treats coordination protocols as individual parts and composes them to construct the intended protocols. However existing approaches do not sufficiently reduce the complexity when a coordination protocol is composed several times, because too many configurations are required to specify a composition. A new approach is proposed that uses metadata to specify the compositions by specifying only one configuration. It can reduce the number of configurations when a coordination protocol is composed several times.

In a sensor network, the technique that limits the number of sensors used for observation is effective to reduce the energy consumption of each sensor. To limit the number of sensors without sacrificing observation accuracy, an appropriate sensor combination must be selected by evaluating the observation effectiveness of various combinations. However, the computational workload for evaluating all the sensor combinations is quite large. We can define a parameter related to the optimal size of a region around an observation target by making a trade-off between accuracy and the computational workload. In region-based sensor selection, a combination of sensors is selected from that is near the observation target. Accuracy is better in a larger region with a lot of sensors, but the computational workload is heavier. In contrast, a smaller region with fewer sensors has poorer accuracy, but a lighter workload. The size of the region controls the trade-off between accuracy and the computational workload. We define a parameter related to the optimal size of a region, and use it to dynamically adjust the region's size. Our simulations confirmed that region-based sensor selection reduces the computational workload and improves accuracy in comparison to existing techniques. © 2008 IEEE.

Model checking is a powerful technique for verifying the correctness of a system's specification. But even when the specification has been verified to be correct, there is still the question of whether the specification covers all the expected behaviors. One of the most important issues for verification is the sufficiency of verification items. In model checking, specification-level properties such as reachability are well-studied, but the sufficiency of a specification against the preceding requirements still remains a challenge. In this paper, we propose a model-checking process with goal oriented requirements analysis, in which goal descriptions in a natural language are systematically refined into linear temporal logic formulae. Furthermore, the coverage of the verification result can be evaluated against the goal model. We developed a tool that supports the process, and applied it to an example. This process lowers the technical barriers to model checking and improves the sufficiency of system verification. © 2008 IEEE.

Multiagent Systems (MAS) are open, heterogeneous and distributed software systems of autonomous agents. The management of exception differs in MAS from what is known in usual engineering approaches, owing to specific situations to handle, such as the agent death, knowledge inconsistencies or collaborative handling. Existing work does not fully address the properties of MAS, notably agent autonomy, and the mechanisms related to exceptions are often ad hoc. In this article, we define the concept of agent exception so as to satisfy the characteristics of the agent paradigm, and we propose a MAS architecture to support design and development of agent systems with exception management facilities. This architecture provides designers with an exception mechanism integrated into usual agent models, so that the work left to the designer is the definition of application-dependent handlers that are automatically invoked by the architecture when required. © 2008, Inderscience Publishers.

A mobile agent is an important platform for applications for the coining ubiquitous society. Many different kinds of mobile agent platforms have been developed. However, agents from one agent platform are generally not able to migrate into another agent platform. As a solution to this problem, we propose an interoperability concept using an incarnation agent. The concept realizes logical mobility within different kinds of agent platforms. The incarnation agent extracts an agent's procedures and status, compiling them into agent platform independent format and then re-compiling them to target agent platform format, thus enabling the process to continue. The incarnation agent also has autonomy for interoperability. It manages complex migration for interoperability, so agent's procedure can be described in simple mobile model. Moreover, the incarnation agent modifies agent's procedures as applicable to facilities of target agent platform. This paper also reports an interoperability middle-ware and its examination. The middle-ware is a foundation of realizing the Incarnation Agent, and the response time and network traffic overheads by the interoperability rniddle-ware has been measured.

Recommender System (RS) predicts user's ratings towards items, and then recommends highly-predicted items to user. In recent years, RS has been playing more and more important role in the agent research field. There have been a great deal of researches trying to apply agent technology to RS. Collaborative Filtering, one of the most widely used approach to predict user's ratings in Recommender System, predicts a user's rating towards an item by aggregating ratings given by users who have similar preference to that user. In existing approaches, user similarity is often computed on the whole set of items. However, because the number of items is often very large and so is the diversity among items, users who have similar preference in one category may have totally different judgement on items of another kind. In order to deal with this problem, we propose a method to cluster items, so that inside a cluster, similarity between users does not change significantly from item to item. After the item clustering phase, when predicting rating of a user towards an item, we only aggregate ratings of users who have similarity preference to that user inside the cluster of that item. Experiments evaluating our approach are carried out on the real dataset taken from MovieLens, a movies recommendation web site. Experiment results suggest that our approach can improve prediction accuracy compared to existing approaches.

The environment has been recognized as an explicit and exploitable element to design multi-agent systems (MAS). It can be assigned a number of responsibilities that would be more difficult to design with the sole notion of agents. To support the engineering of these responsibilities, we identify a set of mechanisms that offer solutions to software designers. We describe the mechanisms, their usage in representative projects, and potential opportunities for further research and applications. The purpose of this article is to clarify the notion of environment in terms of mechanisms, from their abstract description to their practical exploitation. Mechanisms are expected to provide agent-based software designers with a set of design elements to build MAS that take advantage of the environment.

In this paper, we present participatory experiments in economics and role-playing games from an agent-based simulations perspective. In particular, we try to compare these two traditions of participatory approaches to stress identities and differences. After having outlined the lessons of these traditions, we describe multi-agent participatory simulations as a new kind of participatory experiments combining agents and participation more closely, using as an example the methodology we developed to conduct experiments of this new kind.
Multi-agent participatory simulations are described as simulations where agents and players have similar roles and we propose to use assistant agents within these simulations for the purpose of participatory design of protocols or multi-agent systems.

In the near future, applications with location-aware capabilities could be major development targets in the software industry. The current development frameworks rarely pay attention to developing applications for multiple ubiquitous environments. From the perspective of porting or updating applications, there are two dependencies: spatial and localized. These are dependencies on a single environment in which an application is deployed. We propose a new framework that uses a spatio-temporal scope (STS) model to ease deployment of location-aware applications by lessening these dependencies. We describe our model and explain the roles of the STS in the development stages of an application.

Prolonging a network lifetime is one of crucial issues of message routing protocol in mobile ad-hoc networks (MANETs), because MANETs consist of mobile devices powered by batteries. Previous routing protocols focus on route selection by a message sender to balance message forwarding load. However, in this approach, message routes determined by different senders cannot be coordinated, because each sender selects its message route independently. In this paper, we propose an auction-based route allocation scheme where message routes are determined by auctions between message senders and forwarders, and apply the route allocation scheme to the Dynamic Source Routing protocol. Simulation results show the DSR protocol with our allocation scheme can prolong the network lifetime comparing with the routing protocol proposed in the previous works. © 2006 IEEE.

Wireless sensor networks (WSNs) have attracted attention in recent years. Many sensors will be equipped in buildings and provide data about the context of buildings in the future. We can provide many kinds of services that use various context information acquired from wireless sensor networks. However, sensing programs may not be able to be executed concurrently on the same sensor node because of sensors' resource restrictions. So, sensing programs sometimes have to relocate to other sensors if necessary. In this paper, we suggest a middleware for the relocation of a sensing program. Considering severe resource restrictions in a wireless sensor network, we can make a sensing program with a small code footprint. © 2006 IEEE.

Dynamic coverage is a problem of multi-robot systems based on wireless ad-hoc networks. The issue of dynamic coverage occurs notably in post-disaster survivor rescue, search operation, and planet exploration. In this paper, we introduce a novel algorithm of dynamic coverage in a realistically restricted environment for robots. This approach improves efficiency of moving around and amount of communication in a simulation environment. The paper presents comprehensive experimental results and discusses future research directions related to dynamic coverage. © 2006 IEEE.

This work considers encapsulation of multimedia contents as services, and their autonomous provision and distribution by agents. This approach enables content providers to have their contents provided and distributed together with their own business logics regarding interaction with other services and contents, control logic for various options upon provision, and value-added services. This paper proposes a framework for development of agents that provide and distribute such content services. In the framework, the interaction logic of agents is first developed in the same way as in development of ordinary Web services. Control descriptions are then given for each aspect, such as selection of partner agents, negotiation on service options, and migration. The separated descriptions for each aspect facilitate incremental development and test, as well as later modification, of agents with complex behaviors. © 2006 IEEE.

The research on exception handling in Multi-Agent Systems has produced some advanced models to deal with 'exceptional situations'. The expression 'agent exception' is however unclear across the literature, as it sometimes refers to extensions of traditional exception models in programming languages, and sometimes to organizational management mechanisms with distinct semantics. In this paper, we propose a definition of 'agent exception' to clarify the notion and justify that specific research is necessary on this theme. We detail properties of this definition, revisit the traditional vocabulary related to exception in software design, propose an adequate agent architecture, and identify some research issues. This work is aimed at federating the endeavors on the question of exception management for Agent-Oriented Computing.

The notion of contracts (or agreements) has been considered useful to promote mutual understanding and configuration in service provision between its consumer and provider However, it has not been discussed how consistency can be ensured in multiple contracts that a composite service establishes with its component service providers and its consumers. In response to the problem, this study provides a theoretical foundation, based on Event Calculus, for expressing and reasoning about various constraints on contracts as well as consistency properties. On the basis of the proposed foundation, this study also discusses how an existing reasoner on Event Calculus can be used to help development of consistent contractual policies, or constraints on contracts. A tool is developed that wraps the reasoner and facilitates consistency checking and testing.

P2P systems are currently being used all over the world. However, existing P2P technology is not able to modify shared objects efficiently. Naive approaches to support modification result in large amounts of traffic and load concentrations. In our study, this issue is being addressed by representing shared objects by their differences. These are stored in a sub-network that is generated for each object. The object is accessed by retrieving and adding the differences stored in the sub-network. A simple simulation demonstrates the effectiveness of this technique in regard to traffic amount and load balancing properties.

Organization of mobile agents into a group has appeared as a new paradigm for dynamic deployment of composite services. However, it has not been discussed how multiple mobile agents cooperate with each other, handling conflicts in their requirements. In response to this problem, this study proposes a model for cooperative mobility based on the notion of agreements. Agent behavior defined in the proposed model involves agreement establishment and enforcement for cooperative mobility. Such behavior can be customized only by specifying requirements/ constraints of each agent, eliminating the necessity to write down the whole behavior to handle agreements. The model is described in a formal way, using Event Calculus, and it is proved the model leads to no occurrence of defined inconsistency. The model has been implemented on an existing agent framework, Freedia, combined with its dynamic partner management mechanism.

When large-scale wireless sensor networks are deployed in hostile environments, the adversary may compromise some sensor nodes and use them to generate false sensing reports or to modify the reports sent by other nodes. Such false events can cause the user to make bad decisions. They can also waste a significant amount of network resources. Unfortunately, most current security designs have drawbacks; they either require their own routing protocols to be used, or lose legitimate events stochastically and completely break down when more than a fixed threshold number of nodes are compromised. We propose a new method for detecting false events that does not suffer from these problems. When we set the probability of losing legitimate events to 1%, our proposal method can detect more false events than related method can. We demonstrate this by mathematical analysis and simulation.

Formal methods and requirements analysis are techniques for developing complex systems. However, there is little research on reconciling the requirements phase with the formal specification phase. To bridge this gap, we propose a formal specification generator based on model transformation techniques. This tool transforms KAOS models (requirements specifications) into VDM++ formal specifications. Our generator enables consistent and effective software development activities.

Current trend in scientific collaboration focuses on developing effective communication Web media. One of its objectives is to provide informal communication opportunities for collaborating scientists. This paper focuses on analyzing conversation structures of actual collaboration scenarios on the Web. The conversations analyzed model context using hierarchy of learning and communication tied to situated cognition to help understand how users induce communication protocols on the Web. The paper focuses on the analysis of the conversation structures that uses context to identify what could possibly make up a context and to help understand how contexts are punctuated.

Middleware for wireless sensor network (WSN) abstracts a network as an entity and hides programming difficulties from programmers. Many middlewares have been proposed, but they use different programming languages to manipulate functions in WSNs. This inhibits usability when manipulating multiple WSNs managed by different middlewares, because the primitives of each language have different descriptive capabilities. In this paper, we propose and apply design patterns in WSN programming to complement the capabilities of language primitives, and discuss the effectiveness of these design patterns. First, we discuss major middleware languages and compare the capabilities of their primitives. Second, we extract design patterns from the representative middlewares to cover the missing capabilities identified in the comparison. Finally, we discuss the effectiveness of design patterns for WSN programming. The discussion indicates that design patterns improve the usability of manipulating multiple WSNs.

We present a formal approach to conception of a dedicated security infrastructure based on the exception handling in the protected agents. Security-related exceptions are identified and handled by a dedicated reflective layer of the protected agent, or delegated to specialized intrusion management agents in the system if the local reflective layer fails to address the problem. Incidents are handled either directly, if a known remedy exists or indirectly, when an appropriate solution must be identified before response execution. The cooperation between the intrusion management agents and aggregation of their observations can make the system more resilient to misclassification than a solution based purely on signature matching.

Distributed hash tables (DHTs) are a class of decentralized distributed systems that can efficiently search for objects desired by the user. However, a lot of communication traffic comes from multi-word searches. A lot of work has been done to reduce this traffic by using bloom filters, which are space-efficient probabilistic data structures. There are two kinds of bloom filters: fixed-size and variable-size bloom filters. We cannot use variable-size bloom filters because doing so would mean wasting time to calculating hash values. On the other hand, when using fixed-size bloom filters, all the nodes in a DHT are unable to adjust their false positive rate parameters. Therefore, the reduction of traffic is limited because the best false positive rate differs from one node to another. Moreover, in related works, the authors took only two-word searches into consideration. In this paper, we present a method for determining the best false positive rate for three- or more word searches. We also used a new filter called a ringed filter, in which each node can set the approximately best false positive rate. Experiments showed that the ringed filter was able to greatly reduce the traffic.

Various program analysis techniques are efficient at discovering failures and properties. However it is often difficult to evaluate results, such as program traces. This calls for abstraction and visualization tools. We propose an approach based on UML sequence diagrams, addressing shortcomings of such diagrams for concurrency. The resulting visualization is expressive and provides all the necessary information at a glance.

Despite the availability of a variety of program analysis tools, evaluation of these tools is difficult, as only few benchmark suites exist. Existing benchmark suites lack the uniformity needed for automation of experiments. We introduce the design of a uniform build/installation platform, which constitutes an important part of the solution.
This platform is used to manage the build and test process, which is enhanced by a tool that analyzes the structure of unit tests. Benchmark applications lack detailed information about unit tests. Such knowledge is useful: For analysis algorithms that target specific program features, it is desirable to analyze only relevant tests. Using aspect-oriented programming, we wrap test execution and implement a tool providing coverage data of individual unit tests. Furthermore, the wrapper provides a front-end for the selection of subsets of a test suite. We successfully applied our tool to several large programs. This evaluation also gave us interesting insights about the quality of different test suites.

BPEL and similar languages have been provided a foundation for process-based implementation of composite Web services. These languages allow definition of orchestration processes without concrete binding information of involved partners. Although this approach facilitates customization of service discovery and selection before process execution, partner management during process execution has not been considered, such as rebinding of service providers upon events. In response to this problem, this study proposes a description model that facilitates runtime partner management in process-based services. The proposed model includes policy descriptions that allow insertion and customization of binding behavior according to surrounding environments and user preferences. The model also includes extensions in the standard process notation in order to allow process developers to give constraints to avoid adoption of inadequate policies as well as to define handlers to have common rebinding behavior reused. The proposed descriptions have been implemented and used in an agent framework for multimedia services.

This paper addresses the issue of coordination mechanism selection in agent based service oriented computing systems. We aim to strengthen the current research on service selection and composition with a dynamic choice of the underlying coordination mechanisms. Indeed, since the environment in such systems might dynamically change, and the agents can have several protocols at their disposal, they need to select the most adequate one for service provision/request upon the prevailing circumstances. In this paper, we present a joint protocol selection mechanism, which enables agents to decide together the protocols they will use to coordinate each other during a service provision.

Software model checkers work directly on single-process programs, but not on multiple processes. Conversion of processes into threads, combined with a network model, allows for model checking distributed applications, but does not cover potential communication failures. This paper contributes a fault model for model checking networked programs. If a naive fault model is used, spurious deadlocks may appear because certain processes are terminated before they can complete a necessary action. Such spurious deadlocks have to be suppressed, as implemented in our model checker extension. Our approach found several faults in existing applications, and scales well because exceptions generated by our tool can be checked individually.

This paper discusses the Top SE program established to bridge the industry-academia gap. The program features extensive use of software engineering tools, not only to introduce students to the tools, but also as a conduit for learning the techniques and guidelines needed to apply the tools to practical software development situations. The curriculum is organized around practical problems mainly from the area of digital home appliances and focuses on upper stream software development processes.
The Top SE program is developed and operated by a close collaboration between industry and academia. We illustrate our discussion with examples from one of the courses, Verification of Design Models, which takes up model checking technologies, including three specific tools: SPIN, SMV, and LTSA.

Agent-based participatory simulations are laboratory experiments designed like agent-based simulations and where humans access the simulation as software agents. This paper describes the outcomes of six experiments lasting up to two hours each, where human players took part in an iterated game derived from the El Farol bar problem. Agents decide synchronously to go to the bar or to stay home and the benefit depends on the bar attendance, with a threshold effect: it is better to stay home if more than 60% of the agents go. Contrasting with the original version of this problem, we allowed agents, and therefore humans, to communicate before they took their decision. The first two experiments allowed us to train participants and to introduce the notion of teams. Teams represented coalitions within the game and positively affected scoring, but they were not part of an obvious solution to the problem and they did not enforce cooperative behavior in the game. Drawing from these experiments, we designed autonomous agents reproducing strategies of the participants. These agents took part in the last four participatory experiments and we observed the formation of coalitions between agents, between humans and between agents and humans. © 2007 IFAAMAS.

A hierarchical mobile agent is a model that extends the standard mobile agent. In this model it is possible for an agent to migrate inside another agent and parent-child relations can be constructed (the host agent being the parent). By means of such agent synthesis, it is possible to integrate different functionality and have agents interact with one another with no need for remote communications. Even when an agent migrates, it is possible to maintain the relations between parent and child stably over a long period of time. In this paper we focus on the task of controlling these parent-child relations and propose the MAFEH framework designed to simplify related tasks. This frame-work has two special characteristics. One consists of the parent-child agreement specification that expresses the agreement regarding the behavior between parent and child. The other consists of the interaction behavior description specification that facilitates the description of the processes by which individual interactive partners can be searched for, enter into combinations, and disassociate themselves from each other. In this paper we also present an application of the MAFEH framework demonstrating how an agent that encapsulates mobile contents can combine with other agents that provide different contents and services. © 2006 Wiley Periodicals, Inc.

Tag interactions axe agent interactions that complement and differ from speech act communication models. Tags are public information that agents expose to others in the system to allow two types of interactions. Tag monitoring interactions let agents observe the tags of others actively. Tag fortuitous interactions make agents realize the tag of others with unrequested and application-dependent messages. In this paper we model tag interactions based on the agent environment and computational bodies to enact, maintain, and regulate their execution. We discuss the model and we identify further issues in the current state of the research. An example application is described in detail to show the potential of introducing tag interactions.

Exception handling has a commonly agreed semantics in many programming languages. When an operation is called with inappropriate conditions, the control flow of the program is reversed back to the caller to trigger some handling mechanisms. In Multi-Agent Systems (MAS), this semantics applies to the code of agents, but it does not cover the kind of exceptions that occur at the agent level. For instance, the usual handling semantics does not address the cases where the plan of an agent fails and re-planning is required. In fact, the agent code does not necessarily encounter a programming fault or a 'catch' clause in such a case, but the agent has yet to deal with an exceptional situation. In this paper, we survey the literature on exception handling with the aim to demonstrate that research needs to be conducted in the case of MAS due to their openness, heterogeneity, and the encapsulation of agents. We identify research directions from the survey, and we present a simulation scenario to illustrate the occurrence of agent-level exceptions in a simple case. The current result of the survey analysis is that agent exceptions mechanisms should rely on the proactivity of agents, on exploiting the agent environment, on collaborative handling mechanisms, and on the potential links between code-level and agent-level exceptions.

Most non-trivial applications use some form of input/output (I/O), such as network communication. When model checking such an application, a simple state space exploration scheme is not applicable, as the process being model checked would replay I/O operations when revisiting a given state. Thus software model checking needs to encapsulate such operations in a caching layer that is capable of hiding redundant executions of I/O operations from the environment.

In 2001, Olivier Barreteau proposed to jointly use multi-agent systems and role-playing games for purposes of research, training and negotiation support in the field of renewable resource management. This joint use was later labeled the "MAS/RPG methodology" and this approach is one of the foundation stones of the ComMod movement. In this article, we present an alternative method called "agent-based participatory simulations". These simulations are multi-agent systems where human participants control some of the agents. The experiments we conducted prove that it is possible to successfully merge multi-agent systems and role-playing games. We argue that agent-based participatory simulations are also a significant improvement over the MAS/RPG approach, opening new perspectives and solving some of the problems generated by the joint use of role-playing games and multi-agent systems. The advantages are at least threefold. Because all interactions are computer mediated, they can be recorded and this record can be processed and used to improve the understanding of participants and organizers alike. Because of the merge, agent-based participatory simulations decrease the distance between the agent-based model and the behavior of participants. Agent-based participatory simulations allow for computer-based improvements such as the introduction of eliciting assistant agents with learning capabilities.

To achieve flexibility in Service-Oriented Computing, applied values of service options, such as required payment and application-specific quality values, should be determined and agreed for every pair of a service provider and a consumer, by Matching both requirements or negotiating with each other This work proposes a framework for development of agents that provide Web services with service agreements determined for every unit Of service provision. The proposed framework supports lifecycle management of service agreements, namely, implementation of the preliminary process to build agreements. It also supports implementation of service processes that change its behavior according to the established agreements. The framework makes use of BPEL, a standard language to specify a process that implements Web services, and thus facilitate to incorporate additional mechanisms regarding service options into a common approach for development of Web services.

Overhearing has been proposed recently as a model of indirect interactions in Multi-Agent Systems. Overhearer agents receive messages that were not primarily sent to them, as when someone hears a conversation among others. Overhearing has been modeled essentially as message broadcasting, but this approach raises several issues of scalability and appropriateness of the mental state of overheard agents.
In this paper, we motivate and propose a model of overhearing that copes with these issues by introducing an explicit environment entity to handle overbearing. We define key notions with focus on the environment perspective, model them and their relations, and detail an algorithm that describes the environmental process for agent interactions. We finally illustrate our approach with an electronic market scenario.

Web services technology provides the basis for interoperability, dynamic discovery and integration of distributed components. On the other hand, mobile agents have been utilised for achievement of local interactions with distributed components or selection of resources to use, with their ability to migrate from one host to another. This work presents a general framework for 'Mobile Web Services' (MWSs), which is a web service with migration ability. In our framework, a MWS is composed of a combination of (1) Business Process Execution Language for Web Services (BPEL4WS) process description as interaction flow, (2) service components to carry and (3) rules for migration behaviours. This paper focuses on a formal model of our framework, which helps us discuss whether our introduction of migration behaviours meets desirable properties. In this paper, we show that our framework preserves the original semantics of BPEL4WS. We also discuss extension of our framework for fault tolerance of hosts and its satisfaction of desirable properties. Copyright © 2006 Inderscience Enterprises Ltd.

This paper addresses the problem of dynamic protocol selection in open and heterogeneous multi-agent systems (MAS) for collaborative task Performance. Protocols are interaction patterns which help agents coordinate their activities. Usually, agent designers select the protocols to be used for collaborative task performance. In open and heterogeneous MAS, such selection may lead to protocol mismatch at run time. Protocol selection mismatch may in turn result in a collaborative task not being performed, although it could have been performed had the protocols been selected properly. Our solution to this problem is to enable agents to dynamically select protocols. We first study the characteristics of protocols and the descriptions of collaborative tasks. Using these characteristics and descriptions, we devise mechanisms that enable agents to dynamically select protocols when they have to perform a task in collaboration. In this work we relax some restrictive assumptions made in prior work on protocol selection, and which may hinder collaborative task performance. In particular we do not assume that agents trust one another Additionally, because there is no protocol specification standard, we allow several protocol specification formalisms to coexist. Our method allows agents to select their protocols locally and individually, yet coordinate their selection with other agents' selections based on message exchange flows. Since the selection is performed locally, some errors may occur in the process. Our mechanisms provide means for detecting such errors and overcoming them. As we show, the complexity of our solution is empirically sufficiently low for practical use, and the level of success in coordinated protocol selection is very high.

With the spread of mobile phones, the use of Mobile Adhoc NETworks (MANETs) for disaster recovery finally becomes feasible. Information retrieval from the catastrophic place is attended in an energy-efficient manner using the Geographically Bound Mobile Agent (GBMA) model. The GBMA, which is a mobile agent on MANETs that retrieves geographically bound data, migrates to remain in a designated region to maintain low energy consumption for data retrieval, and provides location based migration scheme to eliminate needless migration to reduce energy consumption. In the data retrieval using the GBMA model, survivability of the agent is important. In a MANET, a GBMA with retrieved data may be lost due to its host's death. The lost of the agent causes re-execution of the retrieval process, which depraves energy efficiency. We propose migration strategies of the GBMA to improve its survivability. In the migration strategies, the selection of the next host node is parameterized by node location, speed, connectivity, and battery level. Moreover, in the strategies, multiple migration trigger policies are defined to escape from a dying node. We present the implementation of migration strategies and confirm the achievements with several simulations. This finally leads to the adaptive Geographically Bound Mobile Agent model, which consumes even less energy.

Negotiation between robots is often needed in wireless ad-hoc robot network. In dynamic coverage problem, wireless ad-hoc robots move in the field negotiating with other robots frequently. Robots are tied with P2P network and determine their actions autonomously by negotiations with other robots. The topic of this paper is a negotiation for Multi-Agent-System (MAS) in the problem of robots activity in dynamic coverage, which is the problem of robots to cover all the areas of a tee space by their sensors in the shortest possible time. This paper introduce a novel algorithm for robots' negotiation for MAS in the dynamic coverage problem by using PID-filter. This algorithm reduced useless motion of robots and decreased the time concerning the convergence of a robot's action for dynamic coverage problem. The claim made in this paper for new negotiation algorithm for MAS are supported by comprehensive experimental results and discusses future research directions.

Non-determinism of the thread schedule is a well-known problem in concurrent programming. However, other sources of non-determinism exist which cannot be controlled by an application, such as network availability. Testing a program with its communication resources being unavailable is difficult, as it requires a change on the host system, which has to be coordinated with the test suite. Essentially, each interaction of the application with the environment can result in a failure. Only some of these failures can be tested. Our work identifies such potential failures and develops a strategy for testing all relevant outcomes of such actions. Our tool, Enforcer, combines the structure of unit tests, coverage information, and fault injection. By taking advantage of a unit test infrastructure, performance can be improved by orders of magnitude compared to previous approaches. Our tool has been tested on several real-world programs, where it found faults without requiring extra test code.

Exception handling has received little interest in the agent community despite its challenges to build more reliable agent systems. In this paper, we survey existing work on exception handling for Multi-Agent Systems. We tried to identify in the present literature what research directions are required and likely to improve current techniques. In particular, we think that the agent proactivity and context in the systems are potential characteristics to exploit for agent-level exception handling. Copyright 2006 ACM.

In distributed hash tables, much communication traffic comes from multi-word searches. The aim of this work is to reduce the amount of traffic by using a bloom filter, which is a space-efficient probabilistic data structure used to test whether or not an element is a member of a set. However, bloom filters have a limited role if several sets have different numbers of elements. In the proposed method, extra data storage is generated when contents' keys are registered in a distributed hash table system. Accordingly, we propose a "divided bloom filter" to Solve the problem of a normal bloom filter. Using the divided bloom filter, we aim to reduce both the amount of communication traffic and the amount of data storage.

Agent-UML (AUML) extended UML in order to facilitate the modeling process for agent based systems. It offers several graphical notations, including protocol diagrams which represent agent interaction protocols. In this paper, we describe an AUML-based framework to specify generic protocols. We call generic protocols, agent interaction protocols where only a general behavior of the interacting entities can be described. From AUML protocol diagrams, we identified five fundamental concepts on top of which we defined formal specifications of generic protocols. Through our specifications, we addressed a lack in generic protocol representation by emphasizing the description of actions performed in the course of interactions based on such protocols. The framework we developed is formal, expressive and of practical use. It helps decouple interaction concerns from the rest of an agent's architecture. As an application, we used this framework to publish the specifications of generic protocols for agent interactions in several multi-agent system applications we developed. Additionally, the framework helped us address two issues faced in the design of agent interactions based on generic protocols, protocol configuration and their dynamic selection.

This work considers encapsulation of multimedia contents as services, and their autonomous provision and distribution by agents. This approach enables content providers to have their contents provided and distributed together with their own business logics regarding interaction with other services and contents, control logic for various options upon provision, and value-added services. This paper proposes a framework for development of agents that provide and distribute such content services. In the framework, the interaction logic of agents is first developed in the same way as in development of ordinary Web services. Control descriptions are then given for each aspect, such as selection of partner agents, negotiation on service options, and migration. The separated descriptions for each aspect facilitate incremental development and test, as well as later modification, of agents with complex behaviors. Copyright 2006 ACM.

Participatory simulations are conducted to improve our knowledge of human behaviors, to help in solving conflicts, to shape interaction protocols between humans and to teach some aspects of collective management. Agent-based participatory simulations differ from other kinds of participatory simulations including role playing games and experimental economics simulations. The control architecture of the agents, in these simulations, is more or less integrally replaced by a human player and the interactions between players are limited by the communication protocols designed for the agents, usually the exchange of electronic messages logged for further analysis. Such systems can be considered as ideal multi-agent systems featuring cognitive and intelligent agents. Previous work demonstrated that running this kind of simulations helps to design and improve multi-agent simulations. In this paper, we present a series of agent-based participatory experiments studying negotiation in an abstract case of common resource pool management. The roles were designed in such a way that conflicts should emerge during the negotiations. Observing the behavior of human players, we noticed the apparition of power relations between players. We observed that this power in negotiations was unrelated to any a priori dependence between agents or between roles but was instead drawn from strategies and, more surprisingly, this power was built on an emerging ontology. Copyright 2006 ACM.

Social insects perform complex tasks without top-down-style control, by sensing and depositing chemical markers called "pheromone". We have examined applications of this pheromone paradigm towards realizing intelligent transportation systems (ITS). Many of the current traffic management approaches require central processing with the usual risks of overload, bottlenecks and delay. Our work points towards a more decentralized approach that may overcome those risks. We use new category of the ITS infrastructure called the probe-car system. The probe-car system is an emerging data collection method, in which a number of vehicles are used as moving sensors to detect actual traffic situations. In this paper, a car is regarded as a social insect that deposits multi-semantics of (digital) pheromone on the basis of sensed traffic information. We have developed a basic model for predicting traffic congestion in the immediate future using pheromone. In the course of our experimentation, we have identified the need to properly tune the model to achieve acceptable performance. Therefore, we refined the model for practical use. We evaluate our method using real-world traffic data and results indicate applicability to prediction. Furthermore, we describe the practical implications of this method in the real world. Copyright 2006 ACM.

There have been many attempts to construct web page recommender systems using collaborative filtering. But the domains these systems can cover are very restricted because it is very difficult to assemble user preference data to web pages, and the number of web pages on the Internet is too large. In this paper we propose the way to construct a new type of web page recommender system covering all over the Internet, by using Folksonomy and Social Bookmark which are getting very popular in these days.

A sensor network attracts much attention in recent years. We expect that many services using sensors are to be provided in various places in the future. However, it is difficult to use a sensor simultaneously by many sensing programs because of the poorness of the computational performance of a sensor. So, in this research, we propose a sensor middleware named "SemiFloA" that supports evacuation of sensing programs. This middleware enables the sensing programs to continue its own work in the application specific manner.

Efforts to realize Web service technology for dynamic integration of distributed components have been started. There is also a proposal for a language that describes the integration flow in a platform-independent form. It is expected that Web service integration will be applied not only to the Internet, but also to various environments such as pervasive networks composed of mobile devices with wireless connections. In the latter case, it is necessary to deal with resource saving problems such as those that arise in a relatively low speed and unstable wireless channel. This study applies the mobile agent technique to the above problem and proposes a mobile agent system for Web service integration. In the proposed system, the physical actions of the mobile agents, that is, migration and cloning, are separated from the integration logic, and are represented as rules to be added to the integration flow description. By this separation, the physical behavior can be added or modified according to environmental conditions without modifying the integration flow. © 2005 Wiley Periodicals, Inc.

Overhearing is an indirect interaction type that enacts agents to listen to direct interactions among other agents without taking explicit part in the exchanges. In this paper, we propose a formal model of overhearing named T-compound and a methodology to describe generalised interaction networks in Multi-Agent Systems. The compound is defined with the pi-calculus as an interaction composite. It is handled as an interaction primitive distinct from the traditional point-to-point one, so that our methodology can treat both cases homogeneously.

This paper introduces teams of personal agents that support users individually in electronic negotiations. These agents listen to the running negotiation and to each other to point out relevant information and compile advice for the user. In this frame, we first describe the architecture of this system and propose assistance interaction protocols to specify agent external behaviours in performing their tasks. Then, we discuss the semantic representation of agent communication and describe an abstraction layer to let agents understand user message issues. Our future work aims at improving these mechanisms and enriching them toward a full-fledged implementation.

Multi-agent systems are attractive means for developing complex software systems. However, multi-agent systems themselves tend to be complex, and certain difficulties exist in developing them. One of the difficulties is the gap between design and implementation especially for interaction protocols. In this paper, we propose a new interaction protocol description language called IOM/T. Interaction protocols described using IOM/T have clear correspondence with AUML sequence diagrams and the description can be consolidated into a single unit of IOM/T code. Then, we show how the process of implementing Java-based agent-platform code from AUML design can be carried out, and how IOM/T effectively bridges the gap between design and implementation.

In future ubiquitous environments, contents (data, movie, text, graphics, etc.) will be more sophisticated and context-aware so that they can enrich user experience. We have proposed the Active Contents (AC) framework, which is based on contents encapsulation with program and aspect definition to allow contents to behave actively. AC can be seen as a software component with several viewpoints of contributors (planner, designer, programmer, etc.). The problem is about maintainability of AC which is modified by the contributors based on their own viewpoints.
In this position paper, we propose a mechanism to allow such contributors to modify AC with context-aware aspect. In our mechanism, based on location binding analysis for AC, parallel executions to be performed at a sepaxate location axe detected and automatically executed using workflow-aware communication.

Location-specific data retrieval is an attractive application in a Mobile Ad-hoc Network (MANET). Simple solution for it is that an observer retrieves the data by geocasting from an observer node, but its overhead highly depends on location of the observer and the designated region. We propose a mobile agent approach. A mobile agent migrates from the observer node to a node in the designated region, retrieves data from there, and summarizes, filters, and compresses the retrieved data, This data is sent back to the observer, when the observer request. Since the data is retrieved by the mobile agent located near the data Sources, the data retrieval in the mobile agent approach would involve low overhead, even if the observer is far from the target region or moves around. In the MANET, however, even after the first migration; to stay near data Sources, a mobile agent should migrate to another node in response to node movements.. In this paper, we propose the Geographically Bound Mobile Agent (GBMA) which is a mobile agent that migrates to always be located in a designated region. Moreover, to clarify where the GBMA should be located and when the GBMA starts to migrate, we introduce two geographic zones: required zone and expected zone, Compared with the conventional methods with geocast or with a conventional mobile agent, the GBMA with these zones for retrieving location-specific data can reduce the total number of messages.

In recent years, the rapid development of network infrastructure and the spread of terminals capable of network access have made it possible to access networks at any place and at any time. Ubiquitous information systems, in which necessary information can be accessed easily and safely at any place, are becoming an important issue. It is, however, hard to design such distributed systems when the user uses many kinds of terminals and migrates with these. That is, traditional approaches to development of distributed systems have problems when the systems are used in a ubiquitous environment. This paper proposes a new framework for ubiquitous information systems. The framework includes three kinds of agents: User Interface Agents, Programmable Agents and Service Mediation Agents. We can easily design ubiquitous information systems by ensuring that these agents collaborate. In addition, in cases where distributed systems must be implemented on various networks and terminals, it gives a high degree of flexibility to the systems. We also evaluate the framework's flexibility.

This paper proposes a design method for agent, interaction protocols (AIPs) in multi-agent systems. The method starts a design process with informal and ambiguous requirements in English, and according to the clearly defined development stages the method. gradually converts them into clear specifications expressed in augmented UML. Similar to the object-oriented development, the early stages include extractions of agents, roles of agents, actions, goals, and several types of logical constraints. Based on these information, the successive stages generate skeletons of scenarios, which specify the necessary conditions to achieve a goal. Completing the skeleton with added information from the designer, the skeletons become the final AIP designs. We also show a reuse of design knowledge is possible in each step of the method.

Social insects perform complex tasks without top-down style control, by sensing and depositing chemical markers called "pheromone" We have examined applications of this pheromone paradigm towards intelligent transportation systems (ITS). Many of the current traffic management approaches require central processing with the usual risk for overload, bottlenecks and delays. Our work points towards a more decentralized approach that may overcome those risks. In this paper, a car is regarded as a social insect that deposits (electronic) pheromone on the road network. The pheromone represents density of traffic. We propose a method to predict traffic congestion of the immediate future through a pheromone mechanism without resorting to the use of a traffic control center. We evaluate our method using a simulation based on real-world traffic data and the results indicate applicability to prediction of immediate future traffic congestion. Furthermore, we describe the relationship between pheromone parameters and accuracy of prediction.

A location-specific data retrieval, which is data retrieval from nodes in a designated region at the time, is an attractive application in a Mobile Ad-hon Network (MANET). However, almost all nodes in a MANET are powered by batteries, the location-specific data retrieval should involve a small number of messages. In this paper, we use a mobile agent to retrieve the location-specific data. A mobile agent migrates to a node in a designated region, and retrieves data from nodes in this region. Since, after migration, the agent can communicate with nodes in the designated region through low overhead short length hops, the mobile agent can retrieve data at low message cost for long periods, even if the owner of this agent moves around. However, even after migrating to node in the designated region, in order to stay near this region, a mobile agent should migrate to other nodes in response to the movement of the node hosting this agent. In this paper, we propose the Geographically Bound Mobile Agent (GBMA) which is a mobile agent that periodically migrates in order to always be located in a designated region. In order to clarify where the GBMA should be located and when the GBMA starts to migrate, two geographic zones are set to the GBMA: required zone and expected zone. The required zone ease tracking of the GBMA, and the expected zone ease adjustment of the GBMA migration timing.

This work proposes a novel model where multimedia contents with their related services (business processes and functions) are packaged together as mobile agents. This is intended to enable content providers both to encapsulate their contents and to provide value-added services, for flexible content editing, delivery, and presentation. In addition, agents encapsulating contents/services can contain other agents in themselves (synthesis of agents). A mobile agent compound integrating multiple contents/services can be thus dynamically formed, in which multiple agents work cooperatively and migrate together as a unit. This paper also describes our proposed MAFEH/WS framework for the model. Agents in the model can be developed by incorporating simple parameter settings for synthesis control into business process descriptions in BPEL4WS.

Social insects perform complex tasks without top-down style control, by sensing and depositing chemical markers called "pheromone" We have examined applications of this pheromone paradigm towards intelligent transportation systems (ITS). Many of the current traffic management approaches require central processing with the usual risk for overload, bottlenecks and delays. Our work points towards a more decentralized approach that may overcome those risks. In this paper, a car is regarded as a social insect that deposits (electronic) pheromone on the road network. The pheromone represents density of traffic. We propose a method to predict traffic congestion of the immediate future through a pheromone mechanism without resorting to the use of a traffic control center. We evaluate our method using a simulation based on real-world traffic data and the results indicate applicability to prediction of immediate future traffic congestion. Furthermore, we describe the relationship between pheromone parameters and accuracy of prediction.

Assistant teams extend the present view on personal assistance software. Instead of a single assistant, a team devotes an ensemble of agents to the private use of each user It can provide a new variety of functionalities relying on the composition of individual services for the owner benefit.
In this paper we present a model of assistant teams based on the exploitation of extended agent interactions. In addition to the usual direct interactions among individuals, we introduce the concept of 'overhearing' to let agent react to indirect events. We describe an architecture of such systems, address the concern of modeling their interaction infrastructures with a construction methodology, and detail an example scenario.

A general framework for mobile Web services - which are Web services with the ability to migrate from one host to another - is proposed. In this framework, a mobile Web service is composed of a combination of a BPEL process description, service components to be carried, and migration behavior descriptions using simple but expressive rules. The semantics of the descriptions are defined using Mobile Ambients, namely, a formal model of concurrent mobile processes. With this framework, it is thus possible to add or change migration behaviors without having to modify the BPEL process. © Emerald Group Publishing Limited.

A mobile agent is a one of important platform for applications for coming ubiquitous world. Many different kinds of mobile agent platforms have been developed. However, agents from one agent platform are generally not able to migrate into another agent platform. As a solution to this problem, we propose an interoperability concept using an Incarnation agent. The concept realizes logical mobility within different kinds of agent platforms. The Incarnation agent extracts an agent's procedures and status, compiling them into agent platform independent format and then re-compiling them to target agent platform format, thus enabling the process to continue. The Incarnation agent also has autonomy for interoperability. It manages complex migration for interoperability, so agent's procedure can be described in simple mobile model. Moreover, the Incarnation Agent modifies agent's procedures as applicable to facilities of target agent platform. This paper also reports an interoperability middle-wa e and its examination. The middle-ware is a foundation of realizing the Incarnation Agent, and the response time and network traffic overheads by the interoperability middle-ware has been measured. © 2005, The Institute of Electrical Engineers of Japan. All rights reserved.

In this paper, we propose constraint-based modeling using constraint patterns, which can utilize information of constraint effectively, reuse the structure of efficient and executable software, and construct constraint representation and constraint solvers suitable to domains easily. In order to construct domain-specific constraint solvers, we define the new pattern realized by combining extended patterns and existing patterns as constraint pattern. We show that by sub-classing and refining components of constraint patterns, object-oriented software development using constraint solvers which maintain consistency of relationships among domain-specific objects and among attributes on an object leads to easy construction of applications. We select two problems: GUI system for information control system and design system for mechanical engineering as application, and apply constraint-based modeling to these problems. Furthermore, typical problems of constraint satisfaction problem are also selected and applied as applications. The result of these applications shows that our development method using constraint-based modeling leads to easy development of object-oriented systems that include constraint solver systems facilitating declarative description of relations among objects and flexible control of behavior of these objects, by regarding these relations as constraint.

Pervasive computing is becoming a more important issue for open distributed systems. It is, however, hard to design such distributed systems when the user uses many kinds of terminals and migrates with these. This paper has proposed a new framework for pervasive computing. The framework includes three kinds of agents: User Interface Agents, Programmable Agents, and Service Mediation Agents. We can easily design a flexible distributed system by collaborating these agents. We also evaluate the framework from the flexibility point of view. (C) 2004 Wiley Periodicals, Inc.

This paper proposes a design method for agent interaction protocols (AIP) in multi-agent systems. The method starts a design process with informal and ambiguous requirements in English, and according to the clearly defined development stages the method gradually converts them into consolidate specifications described in UML. Similar to the object-oriented development, the early stages include extractions of agents, roles of agents, actions, goals, and several types of logical constraints. Based on these information, the successive stages generate skeletons of scenarios, which specify the necessary conditions to achieve a goal. Completing the skeleton with added information from the designer, the skeletons become the final AIP designs in UML.

We propose a system architecture for mobile agents to improve their security in the environments of insecure networks and non-sophisticated terminals such as PDAs. As mobile agents freely migrate onto their favorite terminals through insecure networks or terminals, it is not appropriate for them to store some secret information for authentication and encryption/decryption. We introduce one and more secure nodes(OASIS NODE) for securely generating and verifying authentication codes. The each agent's data are encrypted by a pseudo-chaos cipher mechanism which doesn't need any floating processing co-processor. We've constructed a prototype system on a Java mobile agent framework, “Bee-gent” which implements the proposed authentication and cipher mechanisms, and evaluated their performances and their applicability to business fields such as an auction system by mobile agents. © 2004, The Institute of Electrical Engineers of Japan. All rights reserved.

As a consequence of the increasing role of computers throughout society, computers, especially mobile devices, are used in diverse situations. Additionally, the computing environment is becoming more changeable. A network application coordinating mobile devices needs to be able to adapt to changes in the environments. In this paper, we propose a new architecture for mobile computing, which uses a mobile agent technology and adapts to changes flexibly. The framework splits the specification of an application into network environments, coordination logic and patterns. Patterns are applied to the coordination logic in order to derive appropriate behaviors automatically.

As the Internet, intranets and other wide-area open networks grow, novel techniques for building distributed systems, notably mobile agents, are attracting increasing attention. This is particularly the case for inter-company system coordination applications. A key difficulty in constructing such systems is to meet the security requirements while at the same time respecting the requirements for efficient implementation. In this paper we propose a method that addresses this problem and show an application of the method to a real implemented system, the Environmentally Conscious Product (ECP) design support system. Our approach enables developers to specify several candidate system behaviors that satisfy the security requirements. We use patterns for this purpose. Patterns are abstract templates of system behavior fragments. The patterns include agent migrations, communications between applications and security procedures. We model the performance data associated with each pattern. Developers can then select an efficient implementation using this model to compare the performance data of the candidates. We evaluate our approach with a significant real-world example, the ECP design support system that essentially requires inter-company system coordination.

Enterprise information systems are currently developed as Web-based applications in the service-oriented architecture style, which is implied by the stack of Web services standards. One of the most critical aspects in enterprise information systems is to maintain their continuous operation as long as possible. Conventional service invocation mechanism identifies Web services with similar signatures found by a service discovery as distinctively different ones, resulting in the suspension of a service requester and the modification of its invocation procedures. In this paper we propose a reasonable solution to realize runtime invocation of Web services, regarding structural similarities in service signatures as subsumption relations of XML scheme. Given Web services with subsumed signatures, this solution enables a service requester to invoke the Web services by translating the scheme types of the invocation parameters.

Web Services technology for interoperability, dynamic discovery and integration of distributed components is to be applied in various environments, such as networks of relatively narrow and unstable wireless connections. However, in such environments it is necessary to deal with resource limitation. Our work adopts mobile agent technology in response to this problem and presents a mobile agent frame work for Web Services integration. This framework utilizes BPEL (Business Process Execution Language for Web Services) for description of the integration logic, and provides declarative descriptions for physical behaviors (migration and cloning). This facilitates addition or change of physical behaviors according to the environmental conditions while preserving the integration logic. This paper especially focuses on formal definition and discussion of our framework.

This paper proposes an authentication architecture for collaboration among agents in a network environment without security assurance. The architecture requires that there should exist at least one secure node (oasis node). The oasis node generates the same number of authentication codes as the number of objects of authentication, using random numbers and agent information, and distributes the codes among the agents. The agents gather at the specified oasis node and obtain verification by the oasis node, based on the distributed random value and the authentication code. In the authentication architecture proposed in this paper, the random number and the authentication code are publicized information which can be compromised by eavesdropping. But the algorithm for generation and verification of the authentication code is not publicized. The architecture is suited for handling authentication processing in ad hoc collaboration among an unspecified number of agents. (C) 2004 Wiley Periodicals, Inc. Electron Comm Jpn Pt 1, 87(5): 11-19, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ ecja.10165.

A methodology which enables a flexible and reusable development of mobile agent application to a mobility aware indoor environment is provided in this study. The methodology is named Workflow-awareness model based on a concept of a pair of mobile agents cooperating to perform a given task. A monolithic mobile agent application with numerous concerns in a mobility aware setting is divided into a master agent (MA) and a shadow agent (SA) according to a type of tasks. The MA executes a main application logic which includes monitoring a user's physical movement and coordinating various services. The SA performs additional tasks depending on environments to aid the MA in achieving efficient execution without losing application logic. "Workflow-awareness (WFA) " means that the SA knows the MA's execution state transition so that the SA can provide a proper task at a proper timing. A prototype implementation of the methodology is done with a practical use of AspectJ. AspectJ is used to automate WFA by weaving communication modules to both MA and SA. Usefulness of this methodology concerning its efficiency and software engineering aspects are analyzed. As for the effectiveness, the overhead of WFA is relatively small to the whole expenditure time. And from the view of the software engineering, WFA is possible to provide a mechanism to deploy one application in various situations.

This paper deals with "Ubiquitous personal agent" that distinctively provides information services to the individual user depending on his/her personal contexts. In this paper, details about this agent technology as well as its effectiveness are discussed. The latter has been confirmed by verification tests using home information appliances already available in the domestic market.

As mobile computing becomes common, the battery issue of mobile computing devices has become increasingly notable. To this end, research and development of various power-conservation devices and methods are actively taking place. However, the conventional method of extending the battery life through power-conservation can never prevent the unintentional shutdowns of applications due to the dead battery. This research aims to realize the evacuation of applications on a mobile computing device to another device before the battery runs out by creating the application as a mobile agent Particularly, by introducing the concept of the Crisis Management Center dynamic and smooth evacuation of multiple application agents will become possible. This paper explains and verifies the effectiveness of the EASTER (Escape Agent System from dying batTERy), a system developed for the purpose of recovering the applications when a battery is running out through the use of mobile agent system.

This paper deals with "Ubiquitous personal agent" that distinctively provides information services to the individual user depending on his/her personal contexts. In this paper, details about this agent technology as well as its effectiveness are discussed. The latter has been confirmed by verification tests using home information appliances already available in the domestic market.

The recent innovation of telecommunication and networking technology is enabling easy and flexible distribution of digital multimedia contents. However, such rapid progress has brought about various problems on intellectual properties and security. We are investigating a technique to solve the problem called active contents based on hierarchical structures of mobile agents. The agents work as wrappers of contents and can easily manage the policies for contents distribution. In this paper, we give a formal model of active contents in order to establish rigorous foundations for the active contents technique, especially the system of the policy control mechanisms. Using the model, we can verify if the behaviors of the active contents satisfy the given policies or not. An example of the redistribution prohibition policy illustrates how the verification works.

This paper describes a planning mobile agent architecture proposed for mobile and ubiquitous network environments. Mobile agents in this architecture have mobile, planning, and meta-level control functionality, which can make mobile agents intelligent. The architecture addresses the problems of open network environments and adapts to unreliable networks. Stationary agents maintain distributed knowledge that is provided to the mobile agents.

This paper describes a “Ubiquitous Personalize Agent” and it's application: “Shopping assistance service” for ubiquitous environments. Ubiquitous personalize agent is realized based on context reasoning technology. It can determine contexts of users by referring a lot of data which can be retrieved from devices in ubiquitous environments. We also have had an experimental trial of this service. In this paper, we state the technology, service, and evaluation on the experimental trial. © 2003, The Institute of Electrical Engineers of Japan. All rights reserved.

Pervasive computing is becoming a more important issue for open distributed systems. It is, however, hard to design such distributed systems when the user uses many kinds of terminals and migrates with these. This paper has proposed a new framework for pervasive computing. The framework includes three kinds of agents: User Interface Agents, Programmable Agents and Service Mediation Agents. We can easily design a flexible distributed system by collaborating these agents. We also evaluate the framework from flexibility point of view. © 2003, The Institute of Electrical Engineers of Japan. All rights reserved.

We propose a fault-tolerant mechanism based on message integrity code (MIC) method for mobile agent authentication under non-secured network environment. We introduce one or more secured nodes (OASIS NODE) and a mobile agent (FT_Agent) having a replica management mechanism. We assume that the candidate agents for authentication are safely stored in an OASIS NODE and a shared secret key is safely distributed to user terminals from the OASIS NODE at the beginning. When the replica agents on user terminals need their authentication, they calculate MIC by using the shared secret key and move themselves having the MIC to the OASIS NODE, which verifies the MIC. The FT_Agents which are also verified by an OASIS NODE are distributed to the each agent and dynamically manage active replicas and passive replicas. By introducing the MIC method and the replica management mechanism, a secured fault-tolerant system suitable for mobile agents under non-secured network environment can be constructed. © 2003, The Institute of Electrical Engineers of Japan. All rights reserved.

The recent innovation of telecommunication and networking technology is enabling easy and flexible distribution of digital multimedia contents. However, such rapid progress has brought about various problems on intellectual properties and security. We are investigating a technique to solve the problem called active contents based on hierarchical structures of mobile agents. The agents work as wrappers of contents and can easily manage the policies for contents distribution. In this paper, we give a formal model of active contents in order to establish rigorous foundations for the active contents technique, especially the system of the policy control mechanisms. Using the model, we can verify if the behaviors of the active contents satisfy the given policies or not. An example of the redistribution prohibition policy illustrates how the verification works.

This paper describes a planning mobile agent architecture proposed for mobile and ubiquitous network environments. Mobile agents in this architecture have mobile, planning, and meta-level control functionality, which can make mobile agents intelligent. The architecture addresses the problems of open network environments and adapts to unreliable networks. Stationary agents maintain distributed knowledge that is provided to the mobile agents.

This paper describes a “Ubiquitous Personalize Agent” and it's application: “Shopping assistance service” for ubiquitous environments. Ubiquitous personalize agent is realized based on context reasoning technology. It can determine contexts of users by referring a lot of data which can be retrieved from devices in ubiquitous environments. We also have had an experimental trial of this service. In this paper, we state the technology, service, and evaluation on the experimental trial. © 2003, The Institute of Electrical Engineers of Japan. All rights reserved.

Interoperability between different systems is becoming a more important issue for open distributed systems. In this paper, we investigate what kind of framework we need for constructing open distributed systems. Firstly, we enumerate the features and functions which the framework should have. We then evaluate a proposed multi-agent framework, Bee-gent, by using a typical example of open distributed systems. Lastly, we show clearly what is required for such a framework.

With the rapid advances of information technology, we are acquiring much information than ever before. As a result, we need tools for organizing this data. Concept hierarchies such as ontologies and information categorizations are powerful and convenient methods for accomplishing this goal, which have gained wide spread acceptance. Although each concept hierarchy is useful, it is difficult to employ multiple concept hierarchies at the same time because it is hard to align their conceptual structures. This paper proposes a rule learning method that inputs information from a source concept hierarchy and finds suitable location for them in a target hierarchy. The key idea is to find the most similar categories in each hierarchy, where similarity is measured by the K(kappa) statistic that counts instances belonging to both categories. In order to evaluate our method, we conducted experiments using two internet directories: Yahoo! and LYCOS. We map information instances from the source directory into the target directory, and show that our learned rules agree with a human-generated assignment 76% of the time.

（和文論文の英訳版）

With the rapid advances of information technology, we are acquiring much information than ever before. As a result, we need tools for organizing this data. Concept hierarchies such as ontologies and information categorizations are powerful and convenient methods for accomplishing this goal, which have gained wide spread acceptance. Although each concept hierarchy is useful, it is difficult to employ multiple concept hierarchies at the same time because it is hard to align their conceptual structures. This paper proposes a rule learning method that inputs information from a source concept hierarchy and finds suitable location for them in a target hierarchy. The key idea is to find the most similar categories in each hierarchy, where similarity is measured by the K(kappa) statistic that counts instances belonging to both categories. In order to evaluate our method, we conducted experiments using two internet directories: Yahoo! and LYCOS. We map information instances from the source directory into the target directory, and show that our learned rules agree with a human-generated assignment 76% of the time.

Systems comprised of multiple interacting mobile agents provide an alternate network computing paradigm that integrates remote data access, message exchange and migration; which up until now have largely been considered independently. On the surface distributed systems design could be helped by a complete specification of the different interaction patterns, however the number of possible designs in any large scale system undergoes a combinatorial explosion. As a consequence this paper focuses on basic one-to-one agent interactions, or paradigms, which can be used as building blocks; allowing larger system characteristics and performance to be understood in terms of their combination. This paper defines three basic agent paradigms and presents associated performance models. The paradigms are evaluated quantitatively in terms of network traffic, overall processing time and size of memory used, in the context of a distributed DB system developed using the Bee-gent Agent Framework. Comparison of the results and models illustrates the performance trade-off for each paradigm, which axe not represented in the models, and some implementation issues of agent frameworks. The paper ends with a case study of how to select an appropriate paradigm.

As wide-area open networks like the Internet and intranets grow larger mobile agent technology is attracting more attention. Agents are units of software that can deal with environmental changes and the various requirements of open networks through features such as autonomy: mobility: intelligence, cooperation, and reactivity? However; since the usual development methods of the agent systems are not sufficiently investigated, the technology is not yet widespread. In the previous papers, we introduced behavior patterns for mobile agent systems and the development method The behavior patterns represent typical and recurring structures and behaviors of agents. The patterns are classified according to their appropriate architectural levels and the degree to which they depend on specific agent platforms. In this paper we evaluate the advantages of our method from the development process viewpoints. Our evaluation focuses on the development efficiency: the applicability, the extensibility and the understandability of our method.

In view of the proliferation and expansion of wide-area open networks such as the intranets and extra-nets, agent technology is attracting greater attention. However, as yet there is well-established and widely used method of developing safe and secure agent systems. In this paper, we propose a methodology that supports the step-by-step development of mobile agent systems while ensuring consideration of security issues. This approach results in a robust infrastructure for practical system development, and by supporting calculation of various costs allows efficiency and security tradeoffs to be objectively evaluated. © 2001 Springer Berlin Heidelberg.

As wide-area open networks like the Internet and intranets grow larger, mobile agent technology is attracting more attention. Agents are units of software that can deal with environmental changes and the various requirements of open networks through features such as autonomy, mobility, intelligence, cooperation, and reactivity. However, since the usual development methods of the agent systems are not sufficiently investigated, the technology is not yet widespread. In previous papers, we introduced behavior patterns for mobile agent systems and the development method. The behavior patterns represent typical and recurring structures and behaviors of agents. The patterns are classified according to their appropriate architectural levels and the degree to which they depend on specific agent platforms. We evaluate the advantages of our method from the development process viewpoints. Our evaluation focuses on the development efficiency, the applicability, the extensibility and the understandability of our method.

This paper describes the architecture to implement an application in network environments, which adapts to unexpected change in the development phase. In this architecture, an application is expressed as an agent which consists of two layers: base level and meta level. The base level program is an application program and the meta level program is the program that controls the execution of the base level and changes the base level program. Virtual places are also provided in the network. They are used for the release of programs and information which agents retrieve to change their own base level program. An application (or an agent), when a change is required, moves from places to places far the retrieval of programs to adapt to the change. A program search strategy is introduced to adapt to changes by using distributed thesauri of released programs, which realizes an agent's program retrieval method in network environments.

We propose a new concept called Rental Service. Recently, Rental Application has been applied as ASP (Application Service Provider). For the next step in advancing ASP, we would prefer to provide Service which creates new functions, coordinating and facilitating already-existing functions, provided by many applications in the network. In this paper, we firstly made a list of problems for adding such Service into the current ASP systems. Then, we developed a framework as a solution to the problems, in which the Service itself is regarded as an agent. Moreover, we introduced a practical system developed by the framework and finally examined its effectiveness for the above problems through that practical case.

（和文論文の英訳版）

"Drivers' Information Assistance System (DIA system)" is an ITS (Intelligent Transport Systems) application framework that provides agent-based information assistance to drivers through car navigation systems or on-board PCs.
DIA system enables flexible information retrieval over the Internet using intelligent mobile agent, and incorporates a high-speed event delivery facility that makes real-time information service possible. The goal of the system is to provide up to the minute information and services related to driver needs, such as parking lot vacancy information. Crucial to making this a practical operation is the agent-based ability to access the network while the vehicle is in motion.

We propose a programming language, Flage, for building software systems which dynamically adapt to changing local situations. In our language, we construct applications by agents; concurrent mobile objects with the metalevel architecture. Metalevel programming facilities realize a self-control of an agent's actions and an autonomous adaptation to changes. We also introduce another kind of program element called field. A field represents a local situation around agents. For example, one field represents a virtual place to get local information in a network environment and another represents a virtual place where agents do cooperative works. If an agent enters a field, it gets programs and shared information in the field. By moving field to field, an agent can change its program composition by itself and it adapts to changing local situations. In this paper, we describe the language specification of Flage, the implementation of the platform for Flage programming and show some program examples.

A formal verification method using an algebraic specification technique is proposed, and its effectiveness is studied. A computerized automatic verification system, which utilizes an algebraic specification to describe system requirements and to prove an inductive theorem based on a term-rewriting technique for verification, is built and evaluated through experimentally verifying the logic design of a digital reactor protection system in boiling water reactors. The results show that the proposed method can mathematically correctly verify the logic design in a limited time, thereby improving accuracy and reducing person-hours for the verification.

To be practical, mobile agents must be "intelligent." The Plangent system enables mobile agents to make a plan based on user input and adapt it according to information gathered from the network.

Hypersequential programming can produce a highly reliable concurrent program, by precluding the injection of harmful nondeterminism. This method serializes, the program to remove all types of nondeterminism (intended, harmful, and persistent). The programmer debugs it as a serial program. Then it is parallelized by restoring only intended and persistent nondeterminism.

The authors present hypersequential programming, a new method that eases the difficulty of concurrent programming and makes the concurrent program highly reliable. The difficulty of concurrent programming is due mainly to its nondeterminism. The authors classify nondeterminism into three types: intended, harmful, and persistant. In traditional concurrent programming, a programmer first designs and implements programs so as to maximize concurrency, which may include all three types of nondeterminism. She then tries to detect harmful nondeterministic behavior by testing and debugging them. However, removing all harmful nondeterministic behavior is actually very difficult.
Hypersequential programming, on the other hand, first serializes the concurrent program to remove all types of nondeterminism, and then the programmer tests and debugs it as a sequential program. Finally, it is parallelized by restoring only intended and persistent nondeterminism. Hypersequential programming can develop a highly reliable concurrent program, because the injection of harmful nondeterminism is precluded. In this article, the authors also present a simple embodiment of hypersequential programming using Petri nets.

Our goal is to establish a flexible programming support for evolving systems that will enable us to modify programs using less labor, while maintaining good quality during service life. EVA (EVolution mechanism for flexible Agent) was developed to allow a flexible programming support system to be constructed based on our programming method for evolving systems. We consider that programming methods for evolving systems need to satisfy the following essential conditions. First, they need to make it easy to specify changes in a system in terms of new requirements. Second, they need to have a procedure for transmitting the new requirements to a program. Third, they need to be able to guarantee that the resultant program will meet the new requirements. Finally, because of the repetitive nature of much evolving systems work, they need to provide for the reuse of similar modifications during programming.
In order to overcame limitations in program modification techniques which have only considered programming products, programming processes have been introduced into our method. To achieve our goal, we have formulated programming products and programming processes using such formal techniques as functional programming, type theory, modules, parameterized programming and natural deduction, and have constructed a mechanism of reusing these formal programming processes. This paper explains a case study which shows how to develop an evolving system using EVA and it discusses how we can use EVA's mechanism effectively.

Petri net is a formal, graphical, and executable language to describe concurrent Systems, which is used in many software design methods. However, most design methods use a Petri net as an extended state transition system and do not make the best use of diversity of meaning of Petri net, which can describe both a state transition model and a data flow model uniformly. This paper proposes the three phase net-oriented software design method which consists of three phases (structure analysis, structure design, and behavior design) and uses only a net model uniformly as a design chart throughout these phases, while other conventional design methods use 3 or 4 charts complementarily. In this method, a net is stepwise refined from an ambiguous specification to an executable design document. This paper explains the proposed method using a design process example for an elevator control system.

This paper concerns a Petri-net-based model for describing reactive and concurrent systems. Although many high-level Petri nets have been proposed, they are insufficiently practical to describe reactive and concurrent systems in the detail modeling, design and implementation phases. They are mainly intended to describe concurrent systems in the rough modeling phase and lack in several important features (e.g., concurrent tasks, task communication/synchronization, I/O interface, task scheduling) which the most actual implementations of reactive and concurrent systems have. Therefore it is impossible to simulate and analyze the systems accurately without explicitly modeling these features. On the other hand, programming languages based on Petri nets are deeply dependent on their execution environments and not sophisticated as modeling and specification languages. This paper proposes MENDEL net which is a high-level Petri net extended by incorporating concurrent tasks, task communication/synchronization, I/O interface, and task scheduling in a sophisticated manner. MENDEL nets are a wide-spectrum modeling language, that is, they are suitable for not only modeling but also designing and implementing reactive and concurrent systems.

In this paper, we examine ''program adjustment'', a formal and practical approach to developing correct concurrent programs, by automatically adjusting an imperfect program to satisfy given constraints. A concurrent program is modeled by a finite state process, and program adjustment to satisfy temporal logic constraints is formalized as the synthesis of an arbiter process which partially serializes target (i.e., imperfect) processes to remove harmful nondeterministic behaviors. Compositional adjustment is also proposed for large-scale compound target processes, using process equivalence theory. We have developed a computer-aided programming environment on the parallel computer Multi-PSI, called MENDELS ZONE, that adopts this compositional adjustment. Adjusted programs can be compiled into the kernel language (KL1) and executed on Multi-PSI.

MENDELS ZONE is a formal specification-based practical parallel program development system on an MIMD machine with 64 processors. It has been applied to the several practical applications: one such application is described in formal specifications totalling 3700 lines, and the corresponding parallel programs generated from these formal specifications totals 6200 lines. MENDELS ZONE has several key aspects. First, an algebraic specification is used for the functional part of parallel programs and a temporal logic specification is used for the synchronization part of the parallel programs. Second, Petri nets and data-flow diagrams are adopted for visualization. Third, MENDELS ZONE has the following unique features from a parallel programming viewpoint. (1) The confluence property of the complete term rewriting system ensures the quality of non-deterministic execution in parallel programs; (2) Serialization in parallel programming is specified using propositional temporal logic; (3) Parallel implementation of theorem provers contributes to practical use.

Reflection or metalevel architecture has received attention in recent years, since this approach provides functional extension and dynamic adaptation of computer systems. In this paper, we propose a technique to introduce reflection into a kind of algebraic system called rewriting logic. Since rewriting logic can model concurrent object-oriented systems, our technique enables modeling of reflective object-oriented systems including metaobjects and metaobject protocols. A framework for developing denotational semantics is given based on a category-theoretic model. We present some problems for finishing our semantics which remain unsolved.

Rewriting Logic has been proposed as a unified model of parallel and concurrent computation, especially concurrent object-oriented computation and agent oriented computation. In this paper, we present a category-theoretic technique in which simulation relation between concurrent processes described by rewriting Logic is analyzed. In this technique, simulation relation is represented by morphisms in the category of concurrent processes. Moreover, this technique is shown to be applicable to Petri nets by modeling them by rewriting logic. By this method, it is acknowledged that our technique is applicable to Petri nets including multi-loops whose treatment is limited in other techniques.

Although many CASE tools for object-oriented methods (OO CASE tools) have been proposed, few, if any, can verify that the constructed analysis and design models actually match the requirements of the system being developed. In order to realize this kind of verification, we propose a software development method amalgamating OO CASE tools and algebraic specification techniques. We are developing an experimental system named COOAD (CASE tool for Object-Oriented Analysis and Design) in order to examine the effectiveness of our proposition. COOAD supports object-oriented analysis and design, verification of the analysis and design, and generation of code. In this paper, we propose the software development method, introduce COOAD, and illustrate the facilities of COOAD with an example.

When objects migrate or are reused, they must find suitable existing objects and establish communication with them. The authors describe the first stage of Omega, a model that will let developers dynamically adjust object-communication methods so that new and existing objects can exchange messages.

This paper describes an application of artificial intelligence technology to the implementation of a rapid prototyping method in Object-Oriented Performance Design (OOPD) for real-time systems. OOPD consists of two prototyping phases for real-time systems. And each of these phases consists of three steps: prototype construction, prototype execution, and prototype evaluation. We present the following artificial intelligence based methods and tools to be applied to the individual steps. In the prototype construction step, a rapid construction mechanism using reusable software components is implemented based on planning. In the prototype execution step, a hybrid inference mechanism is used to execute the constructed prototype described in declarative knowledge representation. MENDEL, which is a Prolog based concurrent object-oriented language, can be used as a prototype construction tool and a prototype execution tool. In the prototype evaluation step, an expert system which is based on qualitative reasoning is implemented to detect and diagnose bottlenecks and generate an improvement plan for them.

Net-Oriented Analysis and Design (NOAD) is defined as three items: (1) Various nets are utilized as an effective modeling method. (2) Inter-relationships among various nets are determined. (3) Verification or analysis methods for nets are provided and they are implemented based on the mathematical theory, that is Net theory. Very few methods have been presented to satisfy these three items. For example, the Real-Time SA method covers item (1) only. The Object-Oriented Analysis and Design method (OOA/OOD) covers items (1) and (2). NOAD can be regarded as an extension to OOA/OOD. This paper discusses how effectively various nets have been used in actual software development support methods and tools and evaluates such several methods and tools from the NOAD viewpoint.

This paper describes MENDELS ZONE, a Petri-net-based concurrent programming environment, which is especially suitable for cooperating discrete event systems. MENDELS ZONE adopts MENDEL net, which is a type of high level (hierarchical colored) Petri net. One of the characteristics of the MENDEL nets is a process-oriented hierarchy like CCS, which is different from the subnet-oriented hierarchy in the Jensen's hierarchical colored Petri net. In a process-oriented hierarchy, a hierarchical unit is a process, which is more natural for cooperating and decentralized discrete event control systems. This paper also proposes a design methodology for MENDEL nets. Although many Petri net tools have been proposed, most tools support only drawing, simulation, and analysis of Petri nets ; few tools support the design methodology for Petri nets. While Petri nets are good final design documents easy to understand, analyzable, and executable, it is often difficult to write Petri nets directly in an earlier design phase when the system structure is obscure. A proposed design methodology makes a designer to construct MENDEL nets systematically using causality matrices and temporal logic. Furthermore, constructed MENDEL nets can be automatically compiled into a concurrent programming language and executed on a parallel computer.

A software prototyping environment called TransObj (TRANSaction and OBJect) is used for designing real-time Transaction-based Concurrent Software Systems (TCSS). In a TCSS design process, a software designer should perform both functional design and performance design. The designer should change his design view from a transaction-based paradigm to an object-based paradigm during the TCSS design process. Recognition of re-entrant functional objects and serially reusable functional objects in the TCSS should be required. TransObj includes the Stepwise Prototyping Method (SPM), and two SPM-based tools: Prolog-based TransObj (P-TransObj) and GPSS-based TransObj (G-TransObj). SPM enables the designer to advance both functional design and performance design for the TCSS prototype as controling the change of design view paradigms. P-TransObj mainly checks the prototype in a microscopic view on a personal computer. G-TransObj mainly checks the same prototype with a longer time span on a large-scale computer.

An application of structual modeling and automated reasoning as an intelligent software development environment for concurrent programs is presented. This application, using an integration of software reuse and theorem-proving methods, synthesizes an absolutely correct program and increases software productivity. The concurrent programs are described by a Prolog-based concurrent object-oriented language called MENDEL/87. The functional part of the reusable component is generated by structural modeling, and the synchronization part is synthesized from temporal-logic specifications by the use of an automated-reasoning mechanism. A description is also given of the MENDELS ZONE, implemented on a Prolog machine, which is the working base of the method.

対象システムに悪影響を及ぼすものとその要因を解明し改善する作業は,一般的に手間がかかる.また,対象システムの規模が大きく複雑であれば,改善プランも数多く存在する.さらに,ある箇所を修正すると周辺への影響も大きい・このような作業は,通常,専門的な知識と経験を用いて行われている.これらの作業に対してエキスパートシステムを導入すると,評価や改善の効率を高めると期待できる.待ち行列ネットワークの形態にモデル化できるシステムを対象システムとする.また,この対象システムには過大な負荷がかかっている,すなわち,そのモデルである待ち行列ネットワークは,非定常(過負荷)状態にある,あるいはその可能性をもつシステムとする.このような待ち行列ネットワークに悪影響を及ぼすものとして,稼動率や待ち行列長が過大な窓口(ボトルネック窓口)に着目する.このような窓口の同定その要因の解明,および改善プランの提示を行う"ボトルネック診断エキスパートシステム(Bottleneck Diagnosis Expert System:BDES)"について考察する。そこで用いられるヒューリスティクな知識は,対象システム内の窓口の接続の形状やパラメータの大小関係により詳細に分類したものであるこれらは,Prolog言語の事実や規則を用いてインプリメントされた.

A concurrent programming model is provided which is oriented to data stream, software reuse, and prototyping. Based on this model, a program synthesis method is described that consists of two parts: (1) retrieving and interconnecting components from I/O data specifications and (2) synthesizing a synchronization supervisor from a propositional temporal logic specification. MENDEL/87, which is a Prolog-based concurrent object-oriented language, is used as the programming language in this model. This synthesis method has been implemented using Prolog on a Prolog machine.

© 1986, Springer-Verlag. Software prototyping with MENDEL, which is Prolog based concurrent object oriented language, is described. MENDEL can deal with following characteristics such as: 1) meta inference, 2) object concurrency, 3) linkage to C language, 4) propositional temporal logic, 5) Prolog predicates for performance prediction simulator. The object generation in MENDEL, that is a program tranformation of concurrency and temporal dependence requirement specifications, is also described.

The system performance evaluation has three phases; evaluation -diagnosis- improvement, which form a feed-back cycle. Among the three phases, past studies have been focusing mainly on the evaluation phase and many computerized methods were already proposed. On the other hand, the other two phases have been performed based on a try-and-error method. There have been no standard methods for these two phases. A new method for these phases is introduced here. It provides supports to even non-experts to obtain nearly optimum performance. In this method, diagnosis is done by a simple rule-base system and improvement plans are generated in a heuristic way. An experimental tool called Qpit*i was developed based on this method and is presented in this paper. Qpit*i uses simulation data and produces several improvement plans against spotted bottle-necks in an interactive mode with users. As an example of Qpit*i application, it was applied to the simple task allocation problem and expected results were obtained.