Catálogo de publicaciones - libros

In this paper, we describe a cost model for an adaptive cell-based index structure which aims at efficient management of immense amounts of spatio-temporal data. We first survey various methods to estimate the performance of R-tree variants. Then, we present our cost model which accurately estimates the number of disk accesses for the adaptive cell-based index structure. To show the accuracy of our model, we perform a detailed analysis using various data sets. The experimental result shows that our model has the average error ratio from 7% to 13%.

In recent years, many researchers have actively studied communi- cation protocols for wireless sensor networks. Most works are based on the assumption that each sensor node knows its own geographical position by GPS (Global Positioning System). For this, however, we have to pay an extra cost for implementing GPS modules in sensor nodes, and thus the size of sensor node should become large. In this paper, we propose a method by which all the nodes in the sensing field can recognize their own positions without equipping GPS modules in every node. In our scheme, only some nodes are equipped with the GPS modules when the sensing field is deployed, and the others can find out their positions through communications to GPS nodes. To validate our method, we carried out a computer simulation, and observed that all nodes could successfully recognize their own positions in 3 rounds.

Automatic distribution of sequential code is of great concern in applying networks of low cost computers to run computationally intensive code. A major difficulty is to prove that the final distributed code is equivalent with the original sequential code. To achieve this, a formal specification of structure and behavior of the distributed and a formal proof of the equivalence of the operational semantics of the sequential with the final distributed code is presented. To support platform and distributing middleware independence a new architecture is presented.

The peer-to-peer (P2P) systems have grown significantly over the last few years due to their potential for sharing various resources. SP (Super-peer) based P2P systems give the responsibility for query processing to the SPs instead of their OPs (Ordinary-Peer). In these systems, selecting the best SP to join is an important problem, but it has received little attention from the research community. In this study, we propose ISP2P (Intelligent Super-peer based P2P system), which can provide the best SP by analyzing dynamic capacity and similarity between peers. This proposed system can improve scalability and reduce SP’s workload by dynamic CPU load, and decrease message traffic by the physical capacity and similarity of content and user behavior.

In this paper, we present a new graph model of sparse matrix decomposition for parallel sparse matrix–vector multiplication. Our model differs from previous graph-based approaches in two main respects. Firstly, our model is based on edge colouring rather than vertex partitioning. Secondly, our model is able to correctly quantify and minimise the total communication volume of the parallel sparse matrix–vector multiplication while maintaining the computational load balance across the processors. We show that our graph edge colouring model is equivalent to the fine-grained hypergraph partitioning-based sparse matrix decomposition model. We conjecture that the existence of such a graph model should lead to faster serial and parallel sparse matrix decomposition heuristics and associated tools.

This paper addresses a problem of integrating the consistency management of Writes Follow Reads (WFR) session guarantee with recovery mechanisms in distributed mobile systems. To solve such a problem, rollback-recovery protocol rVsWFR, providing WFR consistency model for mobile clients and unreliable servers is proposed. The costs of rollback-recovery in rVsWFR protocol are minimized by exploiting the semantics of clients’ operations and the properties of WFR session guarantee. The paper includes the proof of safety property of the presented protocol.

This paper describes an implementation of the three-dimensional (3-D) parallel algorithm for the wave-equation perfectly matched layer (WE-PML) formulations. The parallel approach is based on domain decomposition technique, and uses the Message Passing Interface (MPI) system. To simplify the parallelization strategy, two-dimensional Cartesian topology and derived data types of MPI are used. The performance of the parallel algorithm has been studied using distributed computing method, and performed on a network of PCs interconnected with Ethernet. A speedup factor of 12.9 has been achieved on the 16 PCs system, as compared to one PC case, for a large size problem.

In link-weighted Application Layer Multicast (ALM), each selfish and strategic end-host receiver may cheat in distance measurement to obtain a better position in the ALM tree. Distance cheating of ALM receivers might lead the ALM tree to be sub-optimal and unstable. We proposed a VCG-based cheat-proof mechanism to defend this kind of cheating behavior in previous work. Based on the theoretical framework, a practical algorithm is designed in this paper, which runs distributedly on ALM receivers. The primary characteristic of the distributed algorithm lies in that it is trustworthy to enforce each selfish receiver to fulfill the algorithm truthfully, which is not considered in other similar studies. Simulations results further suggest that the algorithm is effective in defending distance cheating in link-weighted ALM.

The increasing pervasiveness of large scale networks is bringing distributed simulation (DS) to the reach of academic and business communities besides the traditional military ones. This gives academics and industry the advantage of using larger execution platforms and of reusing locally implemented simulation models as building blocks of much larger models. Developing a distributed simulator however requires learning how to use a given DS standard (such as HLA), that implies a non-negligible amount of effort. This paper addresses the problem of defining a language that can equivalently support the development of local or distributed simulators, making the use of the DS standard transparent. The HLA standard is dealt with, but the method can be extended to any other DS standard. The language (called jEQN) addresses the extended queueing network (EQN) domain, and thus it also includes primitives to facilitate the development of queueing network distributed simulators.

We consider peer-to-peer anti-entropy paradigms for epidemic information diffusion, namely pull, push and hybrid cases, and provide exact performance measures for them. Major benefits of the proposed epidemic algorithms are that they are fully distributed, utilize local information only via pair-wise interactions, and provide eventual consistency, scalability and communication topology-independence. Our contribution is the derivation of exact expressions for infection probabilities through elaborated counting techniques on a digraph. Considering the first passage times of a Markov chain based on these probabilities, we find the expected message delay experienced by each peer and its overall mean as a function of initial number of infectious peers. In terms of these criteria, the hybrid approach outperforms pull and push paradigms, and push is better than the pull case. Such theoretical results would be beneficial when integrating the models in several peer-to-peer distributed application scenarios.