Provenance is a standardised record that describes how entities, activities, and agents have influenced a piece of data; it is commonly represented as graphs with relevant labels on both their nodes and edges. With the growing adoption of provenance in a wide range of application domains, users are increasingly confronted with an abundance of graph data, which may prove challenging to process. Graph kernels, on the other hand, have been successfully used to efficiently analyse graphs. In this paper, we introduce a novel graph kernel calledprovenance kernel, which is inspired by and tailored for provenance data. We employ provenance kernels to classify provenance graphs from three application domains. Our evaluation shows that they perform well in terms of classification accuracy and yield competitive results when compared against existing graph kernel methods and the provenance network analytics method while more efficient in computing time. Moreover, the provenance types used by provenance kernels are a symbolic representation of a tree pattern which can, in turn, be described using the domain-agnostic vocabulary of provenance. Therefore, provenance types thus allow for the creation of explanations of predictive models built on them.

Compliance is when a human positively responds to a request or a recommendation given by a system. For example, when prompted, providing your thumbprint for an automated biometric scanner at the airport or starting to watch a new TV show on a streaming service ‘we think you will love’. In trust-related research, compliance is frequently used as a behavioural measure of trust. When evaluating the compliance-trust association in experimental settings, typically, the participants agree, when asked, that they complied because they trusted the system. We developed three scenarios in instantaneous settings where compliance with an instruction delivered by a robot would typically be ascribed to trust. However, rather than asking, ‘Did you trust?’, we asked, ‘Why did you comply?’ In a thematic analysis of responses, we discovered robot design characteristics and sources not related to the design that persuade humans to comply with instructions delivered by a robot.

In response to the increasing calls for algorithmic accountability, UML2PROV is a novel approach to address the existing gap between application design, where models are described by UML diagrams, and provenance design, where generated provenance is meant to describe an application's flows of data, processes and responsibility, enabling greater accountability of this application. The originality of UML2PROV is that designers are allowed to follow their preferred software engineering methodology to create the UML Diagrams for their application, while UML2PROV takes the UML diagrams as a starting point to automatically generate: (1) the design of the provenance to be generated (expressed asPROV templates); and (2) the software library for collecting runtime values of interest (encoded as variable-value associations known asbindings), which can be deployed in the application without developer intervention. At runtime, the PROV templates combined with the bindings are used to generate high-quality provenance suitable for subsequent consumption. UML2PROV is rigorously defined by an extensive set of 17 patterns mapping UML diagrams to provenance templates, and is accompanied by a reference implementation based on Model Driven Development techniques. A systematic evaluation of UML2PROV uses quantitative data and qualitative arguments to show the benefits and trade-offs of applying UML2PROV for software engineers seeking to make applications provenance-aware. In particular, as the UML design drives both the design and capture of provenance, we discuss how the levels of detail in UML designs affect aspects such as provenance design generation, application instrumentation, provenance capability maintenance, storage and run-time overhead, and quality of the generated provenance. Some key lessons are learned such as: starting from a non-tailored UML design leads to the capture of more provenance than required to satisfy provenance requirements and therefore, increases the overhead unnecessarily; alternatively, if the UML design is tailored to focus on addressing provenance requirements, only relevant provenance gets to be collected, resulting in lower overheads.

Provenance network analytics is a novel data analytics approach that helps infer properties of data, such as quality or importance, from their provenance. Instead of analysing application data, which are typically domain-dependent, it analyses the data’s provenance as represented using the World Wide Web Consortium’s domain-agnostic PROV data model. Specifically, the approach proposes a number of network metrics for provenance data and applies established machine learning techniques over such metrics to build predictive models for some key properties of data. Applying this method to the provenance of real-world data from three different applications, we show that it can successfully identify the owners of provenance documents, assess the quality of crowdsourced data, and identify instructions from chat messages in an alternate-reality game with high levels of accuracy. By so doing, we demonstrate the different ways the proposed provenance network metrics can be used in analysing data, providing the foundation for provenance-based data analytics.

PROV-TEMPLATEIS a declarative approach that enables designers and programmers to design and generate provenance compatible with the PROV standard of the World Wide Web Consortium. Designers specify the topology of the provenance to be generated by composing templates, which are provenance graphs containing variables, acting as placeholders for values. Programmers write programs that log values and package them up in sets of bindings, a data structure associating variables and values. An expansion algorithm generates instantiated provenance from templates and sets of bindings in any of the serialisation formats supported by PROV. A quantitative evaluation shows that sets of bindings have a size that is typically 40 percent of that of expanded provenance templates and that the expansion algorithm is suitably tractable, operating in fractions of milliseconds for the type of templates surveyed in the article. Furthermore, the approach shows four significant software engineering benefits: separation of responsibilities, provenance maintenance, potential runtime checks and static analysis, and provenance consumption. The article gathers quantitative data and qualitative benefits descriptions from four different applications making use of PROV-TEMPLATE. The system is implemented and released in the open-source library ProvToolbox for provenance processing.

We present a canonical form for prov that is a normalized way of representing prov documents as mathematical expressions. As opposed to the normal form specified by the prov-constraints recommendation, the canonical form we present is defined for all prov documents, irrespective of their validity, and it can be serialized in a unique way. The article makes the case for a canonical form for prov and its potential uses, namely comparison of prov documents in different formats, validation, and signature of prov documents. A signature of a prov document allows the integrity and the author of provenance to be ascertained; since the signature is based on the canonical form, these checks are not tied to a particular encoding, but can be performed on any representation of prov .

Provenance data can be expressed as a graph with links informing who and which activities created, used and modified entities. The semantics of these links and domain specific reasoning can support the inference of additional information about the elements in the graph. If such elements include personal identifiers and/or personal identifiable information, then inferences may reveal unexpected links between elements, thus exposing personal data beyond an individual's intentions. Provenance graphs often entangle data relating to multiple individuals. It is therefore a challenge to protect personal data from unintended disclosure in provenance graphs. In this paper, we provide a Privacy Impact Assessment (PIA) template for identifying imminent privacy threats that arise from provenance graphs in an application-agnostic setting. The PIA template identifies privacy threats, lists potential countermeasures, helps to manage personal data protection risks, and maintains compliance with privacy data protection laws and regulations.

In the information age, tools for examining the validity of data are invaluable. Provenance is one such tool, and the PROV model proposed by the World Wide Web Consortium in 2013 offers a means of expressing provenance in a machine readable format. In this paper, we examine from a user's standpoint notions of provenance, the accessibility of the PROV model, and the general attitudes towards history and the verifiability of information in modern data society. We do this through the medium of an online-game designed to explore these issues and present the findings of the study along with a discussion of some of its implications.

On the Web, where resources such as documents and data are published, shared, transformed, and republished, provenance is a crucial piece of metadata that would allow users to place their trust in the resources they access. The open provenance model (OPM) is a community data model for provenance that is designed to facilitate the meaningful interchange of provenance information between systems. Underpinning OPM is a notion of directed graph, where nodes represent data products and processes involved in past computations and edges represent dependencies between them; it is complemented by graphical inference rules allowing new dependencies to be derived. Until now, however, the OPM model was a purely syntactical endeavor. The present article extends OPM graphs with an explicit distinction between precise and imprecise edges. Then a formal semantics for the thus enriched OPM graphs is proposed, by viewing OPM graphs as temporal theories on the temporal events represented in the graph. The original OPM inference rules are scrutinized in view of the semantics and found to be sound but incomplete. An extended set of graphical rules is provided and proved to be complete for inference. The article concludes with applications of the formal semantics to inferencing in OPM graphs, operators on OPM graphs, and a formal notion of refinement among OPM graphs.

The prov family of documents are the final output of the World Wide Web Consortium Provenance Working Group, chartered to specify a representation of provenance to facilitate its exchange over the Web. This article reflects upon the key requirements, guiding principles, and design decisions that influenced the prov family of documents. A broad range of requirements were found, relating to the key concepts necessary for describing provenance, such as resources, activities, agents and events, and to balancing prov’s ease of use with the facility to check its validity. By this retrospective requirement analysis, the article aims to provide some insights into how prov turned out as it did and why. Benefits of this insight include better inter-operability, a roadmap for alternate investigations and improvements, and solid foundations for future standardization activities.

Applications that operate over streaming data with high-volume and real-time processing requirements are becoming increasingly important. These applications process streaming data in real-time and deliver instantaneous responses to support precise and on-time decisions. In such systems, traceability - the ability to verify and investigate the source of a particular output - in real-time is extremely important. This ability allows raw streaming data to be checked and processing steps to be verified and validated in timely manner. Therefore, it is crucial that stream systems have a mechanism for dynamically tracking provenance - the process that produced result data - at execution time, which we refer to as on-the-fly stream provenance tracking. In this paper, we propose a novel on-the-fly provenance tracking mechanism that enables provenance queries to be performed dynamically without requiring provenance assertions to be stored persistently. We demonstrate how our provenance mechanism works by means of an on-the-fly provenance tracking algorithm. The experimental evaluation shows that our provenance solution does not have a significant effect on the normal processing of stream systems given a 7% overhead. Moreover, our provenance solution offers low-latency processing (0.3 ms per additional component) with reasonable memory consumption.

Understanding the dynamics of a crowdsourcing application and controlling the quality of the data it generates is challenging, partly due to the lack of tools to do so. Provenance is a domain-independent means to represent what happened in an application, which can help verify data and infer their quality. It can also reveal the processes that led to a data item and the interactions of contributors with it. Provenance patterns can manifest real-world phenomena such as a significant interest in a piece of content, providing an indication of its quality, or even issues such as undesirable interactions within a group of contributors. This paper presents an application-independent methodology for analyzing provenance graphs, constructed from provenance records, to learn about such patterns and to use them for assessing some key properties of crowdsourced data, such as their quality, in an automated manner. Validating this method on the provenance records of CollabMap, an online crowdsourcing mapping application, we demonstrated an accuracy level of over 95% for the trust classification of data generated by the crowd therein.

Applications that require continuous processing of high-volume data streams have grown in prevalence and importance. These systems process streaming data in real-time and provide instantaneous response to support precise and ontime decisions. In such systems, it is difficult to know exactly how a particular result is generated or more particularly how to precisely trace stream events that caused a particular result. However, such information is extremely important for validating stream processing results. Therefore, it is crucial that stream processing systems have a mechanism for capturing and querying provenance information - the information pertaining to the process that produced result data - at the level of individual stream events, which we refer to as fine-grained provenance. In this paper, we propose a novel fine-grained provenance solution called Stream Ancestor Function - a reverse mapping function used to express precise dependencies between input and output stream elements. We demonstrate how to utilize stream ancestor functions by means of a stream provenance query and replay execution algorithm. Finally, we evaluate the stream ancestor function in terms of storage consumption for provenance collection and system throughput, demonstrating significant reductions in storage size and reasonable processing overheads.

Provenance refers to the past processes that brought about a given (version of an) object, item or entity. By knowing the provenance of data, users can often better understand, trust, reproduce, and validate it. A provenance-aware application has the functionality to answer questions regarding the provenance of the data it produces, by using documentation of past processes. PrIMe is a software engineering technique for adapting application designs to enable them to interact with a provenance middleware layer, thereby making them provenance-aware. In this article, we specify the steps involved in applying PrIMe, analyze its effectiveness, and illustrate its use with two case studies, in bioinformatics and medicine.

Through technologies such as RSS (Really Simple Syndication), Web Services, and AJAX (Asynchronous JavaScript and XML), the Internet has facilitated the emergence of applications that are composed from a variety of services and data sources. Through tools such as Yahoo Pipes, these “mash-ups” can be composed in a dynamic, just-in-time manner from components provided by multiple institutions (i.e., Google, Amazon, your neighbor). However, when using these applications, it is not apparent where data comes from or how it is processed. Thus, to inspire trust and confidence in mash-ups, it is critical to be able to analyze their processes after the fact. These trailing analyses , in particular the determination of the provenance of a result (i.e., the process that led to it), are enabled by process documentation , which is documentation of an application's past process created by the components of that application at execution time. In this article, we define a generic conceptual data model that supports the autonomous creation of attributable, factual process documentation for dynamic multi-institutional applications. The data model is instantiated using two Internet formats, OWL and XML, and is evaluated with respect to questions about the provenance of results generated by a complex bioinformatics mash-up.

Scientific and business communities are adopting large-scale distributed systems as a means to solve a wide range of resource-intensive tasks. These communities also have requirements in terms of provenance. We define the provenance of a result produced by a distributed system as the process that led to that result. This paper describes a protocol for recording documentation of a distributed system's execution. The distributed protocol guarantees that documentation with characteristics suitable for accurately determining the provenance of results is recorded. These characteristics are confirmed through a number of proofs based on an abstract state machine formalization.

Abstract Service discovery is a critical task in service‐oriented architectures. In this paper, we study GRIMOIRES, the semantics‐enabled service registry of the OMII software distribution, from a performance perspective. We study the scalability of GRIMOIRES against the amount of information that has been published into it. The methodology we use and the data we present are helpful for researchers to understand the performance characteristics of the registry and, more generally, of semantics‐enabled service discovery. Based on this experimentation, we claim that GRIMOIRES is an efficient semantics‐aware service discovery engine. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract The open provenance architecture approach to the challenge was distinct in several regards. In particular, it allows different components of the challenge workflow to independently record documentation, and for the workflow to be executed in different environments, made possible by an open, well‐defined data model and architecture. Another noticeable feature is that we distinguish between the data recorded about what has occurred, process documentation, and the provenance of a data item, which is all that caused the data item to be as it is. In this view, provenance is obtained as the result of a query over process documentation. This distinction allows us to tailor the system to best address the separate requirements of recording and querying documentation. Other notable features include the explicit recording of causal relationships between both events and data items, an interaction‐based world model, intensional definition of data items in queries rather than relying on explicit naming mechanisms, and styling of documentation to support non‐functional application requirements such as reducing storage costs or ensuring privacy of data. In this paper, we describe how each of these features aid us in answering the challenge's provenance queries. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract The first Provenance Challenge was set up in order to provide a forum for the community to understand the capabilities of different provenance systems and the expressiveness of their provenance representations. To this end, a functional magnetic resonance imaging workflow was defined, which participants had to either simulate or run in order to produce some provenance representation, from which a set of identified queries had to be implemented and executed. Sixteen teams responded to the challenge, and submitted their inputs. In this paper, we present the challenge workflow and queries, and summarize the participants' contributions. Copyright © 2007 John Wiley & Sons, Ltd.

As scientific workflows and the data they operate on, grow in size and complexity, the task of defining how those workflows should execute (which resources to use, where the resources must be in readiness for processing etc.) becomes proportionally more difficult. While "workflow compilers", such as Pegasus, reduce this burden, a further problem arises: since specifying details of execution is now automatic, a workflow's results are harder to interpret, as they are partly due to specifics of execution. By automating steps between the experiment design and its results, we lose the connection between them, hindering interpretation of results. To reconnect the scientific data with the original experiment, we argue that scientists should have access to the full provenance of their data, including not only parameters, inputs and intermediary data, but also the abstract experiment, refined into a concrete execution by the "workflow compiler". In this paper, we describe preliminary work on adapting Pegasus to capture the process of workflow refinement in the PASOA provenance system.

Abstract Scientific workflows are becoming a valuable tool for scientists to capture and automate e‐Science procedures. Their success brings the opportunity to publish, share, reuse and re‐purpose this explicitly captured knowledge. Within the $^{my}$ Grid project, we have identified key resources that can be shared including complete workflows, fragments of workflows and constituent services. We have examined the alternative ways that these resources can be described by their authors (and subsequent users) and developed a unified descriptive model to support their later discovery. By basing this model on existing standards, we have been able to extend existing Web service and Semantic Web service infrastructure whilst still supporting the specific needs of the e‐Scientist. The $^{my}$ Grid components enable a workflow life‐cycle that extends beyond execution to include the discovery of previous relevant designs, the reuse of those designs and their subsequent publication. Experience with example groups of scientists indicates that this cycle is valuable. The growing number of workflows and services mean more work is needed to support the user in effective ranking of search results and to support the re‐purposing process. Copyright © 2006 John Wiley & Sons, Ltd.

As the Web services and grid community adopt semantic Web technology, we observe a shift towards higher-level workflow composition and service discovery practices. While this provides excellent functionality to non-expert users, more sophisticated middleware is required to hide the details of service invocation and service integration. An investigation of a common bioinformatics use case reveals that the execution of high-level workflow designs requires additional processing to harmonise syntactically incompatible service interfaces. In this paper, we present an architecture to support the automatic reconciliation of data formats in such Web service workflows. The mediation of data is driven by ontologies that encapsulate the information contained in heterogeneous data structures supplying a common, conceptual data representation. Data conversion is carried out by a configurable mediator component, consuming mappings between XML schemas and OWL ontologies. We describe our system and give examples of our mapping language against the background of a bioinformatics use case

Complex services in service-oriented architectures such as the grid typically require to be configured in multiple ways that cannot be anticipated by service designers; we illustrate this requirement by studying the myGrid registry, a grid registry capable of supporting annotations of service descriptions by third-party users. Instead, services have to be conceived so that they can be configured at deployment and run time. We argue that KAoS is a powerful and flexible language that can help define such configurations. Using our registry case study, we examine the requirements that the definition of such complex configurations brings on policy languages and explain how they can be satisfied. Specifically, we use role-value maps to express constraints between property values; we introduce a notion of PolicySet with associated parameters that support constraints within a well defined scope; finally, we define a notion of context that allows us to refer to property values that were extant in past execution environments. Essentially, these concepts allow us to add constraints to values in policy definitions, to organise policies in coherent and structure blocks, and to refer to the execution history. The paper discusses these concepts and how they are implemented in a binding of the KAoS policy language to the myGrid registry.

Current methods for monitoring the security of large-scale commodity clusters tend to treat these clusters as nothing more than collections of independent nodes. As such, the techniques used to secure these clusters have, for the most part, been adaptations of techniques developed for securing and monitoring enterprise computing environments. We have previously proposed the idea of monitoring the security-state of large-scale commodity clusters by examining their emergent properties, that is, properties that are only visible when one ceases to look at a cluster as a collection of disparate nodes and begins to look at the properties of the cluster as a whole. We show that by correlating the open network ports observed on cluster nodes with other emergent properties - such as active processes and the contents of important system files - security analysts can make insightful observations that can greatly restrict the actions that an attacker can carry out undetected.

While the grid and Web services have helped us support heterogeneous resource access through the use of service oriented architectures, they have not addressed the issue of heterogeneous data representation. Since service providers often describe their service interfaces using different data models than those assumed by the client, it is common for additional processing to be required to compensate for the mismatch in data formats. By utilising technology from the semantic Web, we are able to augment existing Web service systems with middleware to automatically perform data harmonisation when a syntactic mismatch occurs. To achieve this, we have developed a mapping language which can be used to annotate XML data structures with OWL concepts and properties, a mapping language engine to implement this language, and a dynamic web service invocation component to execute Web services.

Very large scale computations are now becoming routinely used as a methodology to undertake scientific research. In this context, 'provenance systems' are regarded as the equivalent of the scientist's logbook for in silico experimentation: provenance captures the documentation of the process that led to some result. Using a protein compressibility analysis application, we derive a set of generic use cases for a provenance system. In order to support these, we address the following fundamental questions: what is provenance? How to record it? What is the performance impact for grid execution? What is the performance of reasoning? In doing so, we define a technology-independent notion of provenance that captures interactions between components, internal component information and grouping of interactions, so as to allow us to analyze and reason about the execution of scientific processes. In order to support persistent provenance in heterogeneous applications, we introduce a separate provenance store, in which provenance documentation can be stored, archived and queried independently of the technology used to run the application. Through a series of practical tests, we evaluate the performance impact of such a provenance system. In summary, we demonstrate that provenance recording overhead of our prototype system remains under 10% of execution time, and we show that the recorded information successfully supports our use cases in a performant manner.

Notification services (NSs) are middleware components providing asynchronous message delivery between publishers and consumers. Multiple interconnected NSs form a distributed NS, with each NS routing notifications between publishers and consumers at different locations, enabling consumers to share subscriptions, reducing the number of messages sent. Consumers can specify quality of service (QoS) levels when subscribing to a NS, using negotiation to find QoS levels acceptable to both parties. However, if consumers specify sufficiently different QoS levels, notifications cannot be shared and new subscriptions must be made. Chained negotiation can be used to negotiate QoS levels through intermediate NSs, enabling the reuse of existing subscriptions for additional consumers. In this paper, we present a chained negotiation engine, evaluating its performance and behaviour, showing that it enables negotiation over QoS while still sharing notifications, and that it provides better results for a consumer by negotiation directly with the publisher.

Effective coordination of agents' actions in partially-observable domains is a major challenge of multi-agent systems research. To address this, many researchers have developed techniques that allow the agents to make decisions based on estimates of the states and actions of other agents that are typically learnt using some form of machine learning algorithm. Nevertheless, many of these approaches fail to provide an actual means by which the necessary information is made available so that the estimates can be learnt. To this end, we argue that cooperative communication of state information between agents is one such mechanism. However, in a dynamically changing environment, the accuracy and timeliness of this communicated information determine the fidelity of the learned estimates and the usefulness of the actions taken based on these. Given this, we propose a novel information-sharing protocol, post-task-completion sharing, for the distribution of state information. We then show, through a formal analysis, the improvement in the quality of estimates produced using our strategy over the widely used protocol of sharing information between nearest neighbours. Moreover, communication heuristics designed around our information-sharing principle are subjected to empirical evaluation along with other benchmark strategies (including Littman's Q-routing and Stone's TPOT-RL) in a simulated call-routing application. These studies, conducted across a range of environmental settings, show that, compared to the different benchmarks used, our strategy generates an improvement of up to 60% in the call connection rate; of more than 1000% in the ability to connect long-distance calls; and incurs as low as 0.25 of the message overhead.

Recommender systems are widely used to cope with the problem of information overload and, to date, many recommendation methods have been developed. However, no one technique is best for all users in all situations. To combat this, we have previously developed a market-based recommender system that allows multiple agents (each representing a different recommendation method or system) to compete with one another to present their best recommendations to the user. In our system, the marketplace encourages good recommendations by rewarding the corresponding agents who supplied them according to the users' ratings of their suggestions. Moreover, we have theoretically shown how our system incites the agents to bid in a manner that ensures only the best recommendations are presented. To do this effectively in practice, however, each agent needs to be able to classify its recommendations into different internal quality levels, learn the users' interests for these different levels, and then adapt its bidding behavior for the various levels accordingly. To this end, in this paper, we develop a reinforcement learning and Boltzmann exploration strategy that the recommending agents can exploit for these tasks. We then demonstrate that this strategy does indeed help the agents to effectively obtain information about the users' interests which, in turn, speeds up the market convergence and enables the system to rapidly highlight the best recommendations.

Recommender systems have been widely advocated as a way of coping with the problem of information overload for knowledge workers. Given this, multiple recommendation methods have been developed. However, it has been shown that no one technique is best for all users in all situations. Thus we believe that effective recommender systems should incorporate a wide variety of such techniques and that some form of overarching framework should be put in place to coordinate the various recommendations so that only the best of them (from whatever source) are presented to the user. To this end, we show that a marketplace, in which the various recommendation methods compete to offer their recommendations to the user, can be used in this role. Specifically, this article presents the principled design of such a marketplace (including the auction protocol, the reward mechanism, and the bidding strategies of the individual recommendation agents) and evaluates the market's capability to effectively coordinate multiple methods. Through analysis and simulation, we show that our market is capable of shortlisting recommendations in decreasing order of user perceived quality and of correlating the individual agent's internal quality rating to the user's perceived quality.

The Java RMI collector is arguably the most widely used distributed garbage collector. Its distributed reference listing algorithm was introduced by Birrell et al. in the context of Network Objects, where the description was informal and heavily biased toward implementation. In this article, we formalize this algorithm in an implementation-independent manner, which allows us to clarify weaknesses of the initial presentation. In particular, we discover cases critical to the correctness of the algorithm that were not accounted for by Birrell. We use our formalization to derive an invariant-based proof of correctness of the algorithm that avoids notoriously difficult temporal reasoning. Furthermore, we offer a novel graphical representation of the state transition diagram, which we use to provide intuitive explanations of the algorithm and to investigate its tolerance to faults in a systematic manner. Finally, we examine how the algorithm may be optimized, either by placing constraints on message channels or by tightening the coupling between the application program and distributed garbage collector.

We introduce the Resource Aware Programming framework, which allows users to monitor the resources used by their programs and to programmatically express policies for the management of such resources. The framework is based on a notion of hierarchical groups, which act as resource containers for the computations they sponsor. Asynchronous notifications for resource exhaustion and for computation termination can be handled by arbitrary user code, which is also executed under the control of this hierarchical group structure. Resources are manipulated by the programmer using resource descriptors, whose operations are specified by a resource algebra. In this article, we overview the Resource Aware Programming framework and describe its semantics in the form of a language-independent abstract machine able to model both shared and distributed memory environments. Finally, we discuss a prototype implementation of the Resource Aware Programming framework in Java.

My Grid is an e-Science Grid project that aims to help biologists and bioinformaticians to perform workflow-based in silico experiments, and help them to automate the management of such workflows through personalisation, notification of change and publication of experiments. In this paper, we describe the architecture of my Grid and how it will be used by the scientist. We then show how my Grid can benefit from agents technologies. We have identified three key uses of agent technologies in my Grid: user agents, able to customize and personalise data, agent communication languages offering a generic and portable communication medium, and negotiation allowing multiple distributed entities to reach service level agreements.

The notion of agent has of late become popular in the Grid community, as exemplified by several workshops on the use of agents in the Grid. What are agents for the Grid? What is the difference between agents and Web-services? These are questions that we address by describing a port of the SoFAR agent framework to Web services in the context of a bioinformatics Grid. In this first paper, we focus our discussion solely on issues at the transport layer. Through an agent communication language (ACL) and an abstract communication model, we have been able to define a generic API to communications, and are able to support multiple protocols, including the XML protocol, the transport mechanism of Web services. This approach facilitates the development of applications, makes our environment future-proof, and promotes the open-ness of our Grid architecture to third-party developers.

We present a new distributed garbage collection algorithm that is able to reorganise diffusion trees and to support mobile objects. It has a modular design comprising three components: a reliable transport mechanism, a reference-counting based distributed garbage collector for non-mobile objects, and an extra layer that provides mobility. The algorithm is formalised by an abstract machine and is proved to be correct. The safety property ensures that an object may not be reclaimed as long as it is referred to locally or remotely. The liveness property guarantees that unreachable objects will eventually be reclaimed. The mobility property certifies that messages are always forwarded towards more recent mobile object positions.

Massively distributed computing is a challenging problem for garbage collection algorithm designers as it raises the issue of scalability. The high number of hosts involved in a computation can require large tables for reference listing, whereas the lack of information sharing between hosts in a same locality can entail redundant GC traffic. In this paper, we argue that a conceptual hierarchical organisation of massive distributed computations can solve this problem. By conceptual hierarchical organisation, we mean that processors are still able to communicate in a peer to peer manner using their usual communication mechanism, but GC messages will be routed as if processors were organised in hierarchy. We present an extension of a distributed reference counting algorithm that uses such a hierarchical organisation. It allows us to bound table sizes by the number of hosts in a domain, and it allows us to share GC information between hosts in a same locality in order to reduce cross-network GC traffic.

In this paper, we study how linking mechanisms contribute to the expressiveness of hypertext systems. For this purpose, we formalise hypertext systems as abstract machines. As the primary benefit of hypertext systems is to be able to read documents non-linearly, their expressiveness is defined in terms of the ability to follow links. Then, we classify hypertext systems according to the power of the underlying automaton. The model allow us to compare embedded vs separate links and simple vs generic links. Then, we investigate history mechanisms, adaptive hypertexts, and functional links. Our conclusion is that simple links, whether embeded or separate, generic links, and some adaptive links all give hypertext systems the power of finite state automata. The history mechanism confers them the power of pushdown automata, whereas the general functional links give them Turing completeness.

The remote service request, a form of remote procedure call, and the global pointer, a global naming mechanism, are two features at the heart of Nexus, a library for building distributed systems. NeXeme is an extension of Scheme that fully integrates both concepts in a mostly-functional framework, hence providing an expressive language for distributed computing. This paper presents a semantics for this Scheme extension, and also describes a NeXeme implementation, including its distributed garbage collector.

We present the formal semantics of future in a Scheme-like language which has both side-effects and first-class continuations. Correctness is established by proving that programs annotated by future have the same observable behaviour as their non-annotated counterparts, even though evaluation may be parallel.

The PCKS-machine is an abstract machine that evaluates parallel functional programs with first-class continuations. Parallelism is introduced by the construct pcall, which provides a fork-and-join type of parallelism. To the best of our knowledge, the PCKS-machine is the first implementation of such a language that is proved to have a transparent construct for parallelism: every program using such a construct returns the same result as in the absence of this construct. This machine is also characterised by the non-speculative invocation of continuations whose interest is illustrated in an application. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.