Catálogo de publicaciones - libros

This paper is a position paper on the nature of dynamic systems. While there is an agreement on the definition of what a static distributed system is, there is no agreed definition on what a dynamic distributed system is. This paper is a first step in that direction. To that end, it emphasizes two orthogonal dimensions that are present in any dynamic distributed system, namely the varying and possibly very large number of entities that currently define the system, and the fact that each of these entities knows only a few other entities (its neighbors) and possibly will never be able to know the whole system it is a member of. To illustrate the kind of issues one has to cope with in dynamic systems, the paper considers, as a “canonical” problem, a simple data aggregation problem. It shows the type of dynamic systems in which that problem can be solved and the ones in which it cannot be solved. The aim of the paper is to give the reader an idea of the subtleties and difficulties encountered when one wants to understand the nature of dynamic distributed systems.

Existing grid applications commonly use workflows for the orchestration of grid services. Existing workflow models however suffer from the lack of adaptivity. In this paper we define Adaptive Grid Workflow nets (AGWF nets) appropriate for modeling grid workflows and allowing changes in the process structure as a response to triggering events/exceptions. Moreover, a recursion is allowed, which makes the model especially appropriate for a number of grid applications. We show that soundness can be verified for AGWF nets.

We consider BioAmbients, a calculus for specifying biological entities and for simulating and analysing their behaviour. We extend BioAmbients to take quantitative information into account by defining a stochastic semantics, based on a simulation stochastic algorithm, to determine the actual rate of transitions.

Timed transition systems are a widely studied model for real-time systems. The intention of the paper is to show the applicability of the general categorical framework of open maps to the setting of testing equivalence on timed transition systems, in order to transfer general concepts of equivalences to the model. In particular, we define a category of timed transition systems, whose morphisms are to be thought of as simulations, and an accompanying (sub)category of observations, to which the corresponding notion of open maps is developed. We then use the open maps framework to obtain an abstract bisimilarity which is established to coincide with timed testing equivalence.

A object is an object that can be concurrently accessed by several processes. It has been shown by Maurice Herlihy that any concurrent object defined by a sequential specification can be wait-free implemented from reliable atomic registers (shared variables) and consensus objects. means that any invocation of an operation of the object issued by a non-faulty process does terminate, whatever the behavior of the other processes (e.g., despite the fact they are very slow or even have crashed).

So, an important issue consists in providing reliable atomic registers and reliable consensus objects despite the failures experienced by the base objects from which these atomic registers and consensus objects are built. This paper considers self-implementations, i.e., the case where a reliable atomic register (resp., consensus object) is built from unreliable atomic registers (resp., unreliable consensus objects). The paper addresses the object failure model where the base objects can suffer or crash failures. When there are solutions the paper presents corresponding algorithms, and when there is no solution, it presents the corresponding impossibility result. The paper has a tutorial flavor whose aim is to make the reader familiar with important results when one has to build resilient concurrent objects. To that aim, the paper use both algorithms from the literature and new algorithms.

The paper describes equivalent transformations of structures of the Sisal 3.1 programming language (based on Sisal 90). These transformations are aimed to decompose the complex language structures into more simple ones that can be directly expressed by the internal representation IR1 (based on the IF1 language). Currently some description of similar transformations can be found in few works about Sisal 90 in the form of examples. A front-end compiler from Sisal 3.1 into IR1 performs these transformations, so they can help to understand better its translation strategy. The paper also briefly describes Sisal 3.1 and IR1.

This paper proposes an implementation of the data structure called bag or multiset used by descriptive programming languages (e.g. Gamma, Linda) over an open system. In this model, a succession of ”chemical reactions” consumes the elements of the bag and produces new elements according to specific rules. This approach is particularly interesting as it suppresses all unneeded synchronization and reveals all the potential parallelism of a program. An efficient implementation of a bag provides an efficient implementation of the subsequent program. This paper defines a new communication and synchronization model adapted from workqueues used in parallel computing. The proposed model allows to benefit from the potential parallelism offered by this style of programming when only an approximate solution is needed.

Massively multiplayer online games (MMOG) require large amounts of computational resources for providing a responsive and scalable gameplay for thousands of concurrently participating players. In current MMOG, large data-centers are dedicated to a particular game title. Such static hosting requires a huge upfront investment and carries the risk of false estimation of user demand. The concept of grid computing allows to use resources on-demand in a dynamic way, and is therefore a promising approach for MMOG services to overcome the limitations of static game provisioning. In this paper, we discuss different parallelization mechanisms for massively multiplayer gaming and grid architecture concepts suitable for on-demand game services. The work presented here provides both a state-of-the-art analysis and conceptual use case discussion: We outline the new European project which targets at scaling real-time interactive online applications and MMOG, including First Person Shooter (FPS) and Real-Time Strategy (RTS) games, in an on-demand manner using a distributed grid architecture. Finally, we describe our experimental online game Rokkatan and report experimental scalability results for this game on a multi-server grid architecture.

In this paper we present methods for parallelization of 3D CFD forest fire modelling code on Non-uniform memory computers in frame of the OpenMP environment. Mathematical model is presented first. Then, some peculiarities of this class of computers are considered, along with properties and limitations of the OpenMP model. Techniques for efficient parallelization are discussed, considering different types of data processing algorithms. Finally, performance results for the parallelized algorithm are presented and analyzed (for up to 16 processors).

The paper presents IARnet toolkit, a set of high-level tools and services simplifying integration of software resources into a distributed computing environment and development of distributed applications involving dynamic discovery and composition of resources. A case study of using IARnet for solving large scale discrete optimization problems is discussed.