Catálogo de publicaciones - libros

Classical distributed database systems monolithically offer distribution transparency and higher performance. This is made possible by making data available and closer to the application domain(s) that uses it by means such as the data distribution, duplication, and fragmentation. However, with the advances in technologies this monolithic and top down approach becomes insufficient. In the new networked computational environment, the data distribution issue has evolved into data integration from several heterogeneous and autonomous data sources. Heterogeneous distributed databases are designed to deal with issue of data integration and interoperability. They are developed to allow timely and reliable access to heterogeneous and autonomous data sources in an environment that is characterized as “sometime, somewhere.” The concept of mobility, where users access information through a remote connection with portable devices, has introduced additional complexities and restrictions to the heterogeneous distributed database system. This keynote address first introduces a three dimensional space to classify and identify the evolution of different classes of database systems. It also extensively discusses Heterogeneous Distributed Database Systems (HDDBS) and Mobile Data Access Systems (MDAS). Finally, it will address several research issues and their potential solutions.

We survey the MADIS architecture. It supports high availability, fault tolerance and seamless error recovery in computer networks for distributed web services. MADIS is open for plugging in different protocols for replication, failure resilience and recuperation. We outline ongoing research which aims at improving fault tolerance and error recovery by a dynamic adaptation of protocols plugged into MADIS. Future development of MADIS envisages an extension with functionality supporting web-based services also for mobile users, possibly including an integration of voice and data traffic over a single internet link.

A hierarchy is an arrangement of qualitative values in a tree with certain properties. Hierarchies allow to define the confusion conf(r, s) in using qualitative value r instead of the intended or correct value s . From here, “predicate P holds for object o ”, written P( o ), is generalized to “P holds for o within confusion ε ”, written P_ ε ( o ). These precision-controlled predicates are useful to retrieve approximate answers, where the error (confusion) is known. The predicates are implemented through an extended SQL that uses confusion to retrieve information from a database. We show how to extend any database for precision-controlled retrieval. Limiting the total error is also useful, and this is achieved by predicate P^e. Examples are given.

In this paper we deal with the solution of very large instances of the design distribution problem for distributed databases. Traditionally the capacity for solving large scale instances of NP-hard problems has been limited by the available computing resources and the efficiency of the solution algorithms. In contrast, in this paper we present a new solution approach that permits to solve larger instances using the same resources. This approach consists of the application of a systematic method for transforming an instance A into a smaller instance A ’ that has a large representativeness of instance A . For validating our approach we used a mathematical model developed by us, whose solution yields the design of a distributed database that minimizes its communication costs. The tests showed that the solution quality of the transformed instances was on the average 10.51% worse than the optimal solution; however, the size reduction was 97.81% on the average. We consider that the principles used in the proposed approach can be applied to the solution of very large instances of NP-hard problems of other problem types.

This is an initial case on exploring the application of algorithmic skeletons to abstract low-level interprocess communication in MPI. The main purpose is intended to illustrate the competitive performance demonstrated by the skeletal approach when compared to utilization of the pure MPI, whilst providing an abstraction with reusability advantages. This initial work involves the implementation of the Wagar’s hyperquicksort algorithm in conjunction with the MPI-based eSkel skeleton library. The reported results compare three MPI-based implementations of hyperquicksort. Firstly a canonic MPI one; secondly, two implementations using the MPI-based skeletal library eSkel . Lastly, the S3L_sort routine, part of its optimized numerical libraries from Sun, is employed as baseline. This overall comparison demonstrates that the use of algorithmic skeletons caused a slight performance degradation, while providing some promising guidance on the use of abstraction for low-level communication operations using the eSkel model.

We present a simple implementation of a token-based distributed mutual exclusion algorithm for multithreaded systems. Several per-node requests could be issued by threads running at each node. Our algorithm relies on special-purpose alien threads running at host processors on behalf of threads running at other processors. The algorithm uses a tree to route requests for the token. We present a performance simulation study comparing two versions of our algorithm with a known algorithm based on path reversal on trees. Results show that our algorithm performs very well under a high load of requests while obtaining acceptable performance under a light load.

The problem of evaluating time complexity of random distributed algorithms is considered. A common and natural way to randomize a distributed algorithm is to use random walks i.e. memoryless stochastic processes: a “token” message circulates in the system and, at each step, the node that owns it sends it to one of its neighbors chosen at random. The token usually contains some pieces of information or part of the result of some distributed computing for instance. In this paper we focus on the cover time, defined by the expected time to visit all nodes in the system. This quantity often appears in the complexity of random walk based distributed algorithms. We provide a general method to compute the cover time on any arbitrary graph modeling a distributed system.

Peer-to-Peer networks (P2P) exhibit specific characteristics that can be exploited for media streaming delivery. In this paper we propose a P2P-based architecture for video streaming delivery incorporating reputation, cooperation, and semantic clustering strategies. We believe that the integration of those strategies will lead to significant improvements of P2P-based media streaming delivery. In our approach all peers cooperate and share resources. They inform each other about these resources using a resource ticket. Only the best peers are selected and shown in an access ticket. Reputation is proposed as a way for supervising and keeping the media stream of acceptable quality for end-peers.

An intrusion detection system (IDS) usually has to analyse Giga-bytes of audit information. In the case of anomaly IDS, the information is used to build a user profile characterising normal behaviour. Whereas for misuse IDSs, it is used to test against known attacks. Probabilistic methods, e.g. hidden Markov models, have proved to be suitable to profile formation but are prohibitively expensive. To bring these methods into practise, this paper aims to reduce the audit information by folding up subsequences that commonly occur within it. Using n-grams language models, we have been able to successfully identify the n-grams that appear most frequently. The main contribution of this paper is a n-gram extraction and identification process that significantly reduces an input log file keeping key information for intrusion detection. We reduced log files by a factor of 3.6 in the worst case and 4.8 in the best case. We also tested reduced data using hidden Markov models (HMMs) for intrusion detection. The time needed to train the HMMs is greatly reduced by using our reduced log files, but most importantly, the impact on both the detection and false positive ratios are negligible.

In order to manage fairly the service of the queueing elements, the support of QoS with a sophisticated packet scheduling algorithms that is a part of the Fair Queuing family can be considered as essential. Two are the main parts that this work focuses; First, the Palindromic Motion (PM) algorithm that works as a timestamp (or sorted priority) scheduler keeping the flow service priority and second, the two backup flexible credit methods for adjustment of the weight which are used instead of the fixed credit method with a lower maximum weight. A feedback mechanism is used for adjusting the weight size considering the current packet size. The provisional increase of the weight is proposed by the two backup methods; the Direct Increase Weight (DIW) algorithm and the Compound Round Robin (CRR) algorithm. Advantages over recent schemes like Group Round Robin (GRR) etc are presented. Simulation experiments are provided.