Catálogo de publicaciones - libros

Many essential fundamental services for networked distributed systems (ad hoc, wireless or sensor) involve maintaining a global predicate over the entire network (defined by some invariance relation on the global state of the network) by using local knowledge at each of the participating nodes. The participating nodes can no longer keep track of even a small fraction of the knowledge about the global network due to limited storage. We need a new paradigm of localized distributed algorithms, where a node takes simple actions based on local knowledge of only its immediate neighbors and yet the system achieves a global objective. Self-stabilization is a relatively new paradigm for designing such localized distributed algorithms for networks; it is an optimistic way of looking at system fault tolerance and scalable coordination; it provides a cost effective built-in safeguard against transient failures that might corrupt data in a distributed system. We introduce self-stabilizing protocol design with the example of a total dominating set in a network graph and discuss some open problems.

Distributed Sensor Network is a classical area of multi- disciplinary science. This needs a special type of computing, communication and sensing. This talk presents some new results on the following topics: 1) An optimization framework based on mathematical programming for maximizing the coverage probability of a sensor field under the constraints of investment limit; 2) Feature extraction using sensor networks.

In the last several years, we have made great efforts on prototype development and deployments of real systems about peer-to-peer computing. We have released many famous systems in CERNET of China, including: 1) a live streaming system based on P2P computing, named AnySee, in 2004; 2) a P2P VoD system, named GridCast, a P2P based E-Learning system, named APPLE, in 2005; 3) a P2P based gaming platform, named PKTown, and a P2P-based high performance computing platform, named P2HP, in 2006; 4) a P2P live streaming system for wireless environment, named MoSee, in 2007. All these deployed systems have attracted more attention on innovative P2P applications. In the last several years, there are about more than 100,000 users, which have enjoyed the services provided by these applications and we also have collected many data sets about users behaviors in different applications. Based on these logs from real systems, there is one finding: single platform, which includes many typical P2P applications, is a promising system for users, developers and researchers. For users, they can enjoy different services in one software, not many dazzling applications. For developers, they can deploy new P2P services quickly based on the functions and support by platform. For researchers, they can model the complex network and make statistic analysis and physical evolvement based on the traces provided by the platform. In the future, we will focus on P2P based platform, named Ripple, which is to construct a Reliable independent P2P layered engine with manageability to support services, including scientific research, streaming services, game services and etc.

The adoption of self-stabilization as an approach to fault-tolerant behavior has received considerable research interest over the last decade. In this paper, we propose a self-stabilizing algorithm for 3-edge-connectivity of an asynchronous distributed model of computation. The self-stabilizing depth-first search algorithm of Collin and Dolev [4] is run concurrently to build a depth-first search spanning tree of the system. Once such a tree of height is constructed, the detection of all 3-edge-connected components of the system requires () rounds. The result of computation is kept in a distributed fashion in the sense that, upon stabilization of another phase of the algorithm, each processor knows all other processors that are 3-edge-connected to it. Assuming that every processor requires bits for the depth-first search algorithm, the space complexity of our algorithm is () bits per processor.

In this paper, we study the problem of scheduling a set of periodic preemptive independent hard real-time tasks on the minimum number of processors. We assume that the partitioning strategy is used to allocate the tasks to the processors and the EDF method is used to schedule the tasks on each processor. It is known that this scenario is NP-hard; thus, it is unlikely to find a polynomial time algorithm to schedule the tasks on the minimum number of processors. In this work, we derive a lower and an upper bound for the number of processors required to satisfy the constraints of our problem. We also compare a number of heuristic algorithms with each other and with the bounds derived in this paper. Numerical results demonstrate that our lower bound is very tight and it is very close to the optimal solution.

It is a challenging issue whether scientific applications are suitable for Imagine architecture. To address this problem, this paper presents a novel architecture-based optimization for the key techniques of mapping scientific applications to Imagine. Our specific contributions include that we achieve fine kernel granularity and choose necessary arrays to organize appropriate streams. Specially, we develop a new stream program generation algorithm based on the architecture-based optimization. We implement our algorithm to some representative scientific applications on ISIM simulation of Imagine, compared the corresponding FORTRAN programs running on Itanium 2. The experimental results show that the optimizing stream programs can efficiently improve computational intensiveness, enhance locality of LRF and SRF, avoid index stream overhead and enable parallelism to utilize ALUs. It is certain that Imagine is efficient for many scientific applications.

Sparse matrix-vector multiplication (shortly SpMV) dominates the performance of many scientific and engineering applications. However, it tends to run much more slowly than its dense counterpart because the algorithms have poor temporal and spatial locality, the memory access patterns are irregular. Its performance depends heavily on both the nonzero structure of the sparse matrix and on the machine architecture. In this paper, we address the problem of implementing and optimizing SpMV on Imagine stream processor. We present three classes of implementation algorithms based on different key ideas, first two of which highlight different aspects of underlying stream architecture, and the third algorithm is inspired by the SpMV vector implementation. Then we discuss some critical optimizations. The experimental results over same benchmarks show we achieve up to an average 67 percent relative improvement over published evaluation.

The mobile agent (MA) technology has been widely applied in distributed applications. However, since mobile agents are highly autonomous, coordinating the their behaviours is hard. We concentrate on the mutual exclusion issue in this paper and propose an algorithm for achieving mutex among mobile agents. In contrast to the existing algorithms for traditional distributed processes, the proposed algorithm does not require MAs to have a pre-knowledge about other competitors, nor the total number of them. MAs can join/leave the competition session freely. The algorithm performance is also evaluated through simulations.

In this paper a real and complex transportation problem including routing, scheduling and loading tasks is presented. Most of the related works only involve the solution of routing and scheduling, as a combination of up to five different types of VRPs (Rich VRP), leaving away the loading task, which are not enough to define more complex real-world cases. We propose a solution methodology for transportation instances that involve six types of VRPs, a new constraint that limits the number of vehicles that can be attended simultaneously and the loading tasks. They are solved using an Ant Colony System algorithm, which is a distributed metaheuristic. Results from a computational test using real-world instances show that the proposed approach outperforms the transportation planning related to manual designs. Besides a well-known VRP benchmark was solved to validate the approach.

Cellular automata can form the basis of a practical model for a broad range of tasks that require the coordination of many simple computing devices. We propose using “semi-synchronous” cellular automata as a platform for efficiently realizing ant-inspired algorithms that coordinate robots within a fixed, geographically constrained environment. We present an appropriate formalization of the resulting model, illustrated via “proof-of-concept” problems that have ant-robots move and aggregate in various ways.