Catálogo de publicaciones - libros

Because of their highly distributed nature and the lack of global rebalancing, skiplists are becoming an increasingly important logarithmic search structure for concurrent applications. Unfortunately, none of the concurrent skiplist implementations in the literature, whether lock-based or lock-free, have been proven correct. Moreover, the complex structure of these algorithms, most likely the reason for a lack of a proof, is a barrier to software designers that wish to extend and modify the algorithms or base new structures on them.

This paper proposes a simple new lock-based concurrent skiplist algorithm. Unlike other concurrent skiplist algorithms, this algorithm preserves the skiplist properties at all times, which facilitates reasoning about its correctness. Though it is lock-based, the algorithm is highly scalable due to a novel use of optimistic synchronization: it searches without acquiring locks, requiring only a short lock-based validation before adding or removing nodes. Experimental evidence shows that this simpler algorithm performs as well as the best previously known lock-free algorithm under the most common search patterns.

In a sensor network the sensors, or nodes, obtain data and have to communicate these data to a central node. Because sensors are battery powered they are highly energy constrained. Data aggregation can be used to combine data of several sensors into a single message, thus reducing sensor communication costs at the expense of message delays. Thus, the main problem of data aggregation is to balance the communication and delay costs.

In this paper we study the data aggregation problem as a bicriteria optimization problem; the objectives we consider are to minimize maximum energy consumption of a sensor and a function of the maximum latency costs of a message. We consider distributed algorithms under an asynchronous time model, and under an almost synchronous time model, where sensor clocks are synchronized up to a small drift. We use competitive analysis to assess the quality of the algorithms.

Mobile-agent-based distributed systems are attracting widespread attention as the adaptive and flexible systems: mobile agents traverse the distributed system and carry out a task at each node. In such mobile-agent-based systems, is the most fundamental scheme supporting cooperation among mobile agents. It requires to accomplish all-to-all information exchange over all agents so that each agent can obtain the all information each agent initially has. Rendezvous algorithms, which require that all the agents rendezvous on a node at a time, can achieve this requirement, however it takes excessive cost for our objective. In this paper, we newly introduce the mobile agent gossip problem. In this problem, an agent can obtain the information of another agent by meeting the agent itself or the agent that has already got the information. The gossip scheme is expected to accomplish the all-to-all information exchange with a smaller number of agents’ moves than the rendezvous algorithms. We propose mobile agent gossip algorithms on several network topologies, and prove that all proposed algorithms are asymptotically optimal in term of the number of moves.

In this paper, we first introduce the . Based on intrinsic properties of these words, we present a new approach to solve the Circle Formation Problem in the semi-synchronous model (SSM)—no two robots are supposed to be at the same position in the initial configuration. The proposed protocol is — all the robots are eventually in the desired configuration, which remains true thereafter. In SSM, the improvement of the latest recent work for this problem is twofold: (1) the protocol works for any number of weak robots, except if  = 4, and (2) no robot is required to reach its computed destination in one step.

Finally, starting from a biangular configuration, our protocol also solves CFP in the fully asynchronous model (CORDA). To our best knowledge, it is the first CFP protocol for SSM which is compatible with CORDA.

Distributed Coordination, (Uniform) Circle Formation, Mobile Robot Networks, Self-Deployment.

A number of recent studies address systems of mobile autonomous robots from a distributed computing point of view. Although such systems employ robots that are relatively weak and simple (i.e., dimensionless, oblivious and anonymous), they are nevertheless expected to have strong fault tolerance capabilities as a group. This paper studies the partitioning problem, where robots must divide themselves into size-balanced groups, and examines the impact of common orientation on the solvability of this problem. First, deterministic crash-fault tolerant algorithms are given for the problem in the asynchronous full-compass and semi-synchronous half-compass models, and a randomized algorithm is given for the semi-synchronous no-compass model. Next, the role of common orientation shared by the robots is examined. Necessary and sufficient conditions for the partitioning problem to be solvable are given in the different timing models. Finally, the problem is proved to be unsolvable in the no-compass asynchronous model.

The focus of the present paper is on providing a local deterministic algorithm for colouring the edges of subgraphs of Unit Disc Graphs. These are geometric graphs such that for some positive integers , the following property holds at each node : if we partition the unit circle centered at into 2 equally sized wedges then each wedge can contain at most points different from . We assume that the nodes are location aware, i.e. they know their Cartesian coordinates in the plane. The algorithm presented is local in the sense that each node can receive information emanating only from nodes which are at most a constant (depending on and , but not on the size of the graph) number of hops away from it, and hence the algorithm terminates in a constant number of steps. The number of colours used is 2 + 1 and this is optimal for local algorithms (since the maximal degree is 2 and a colouring with 2 colours can only be constructed by a global algorithm), thus showing that in this class of graphs the price for locality is only one additional colour.

Edge Colouring, Geometric Graphs, Unit Disk Graphs, Local Algorithm, Location Awareness, Wedge, Wireless Network.

The proliferation of cheap portable, wireless computing devices (e.g., cell phones and PDAs) promises the availability of a large number of computing devices in a relatively small geographic region. Researchers have proposed using such an ensemble of wireless devices to create a wireless ad-hoc lattice computer (WAdL) to harness the collective computing capabilities of the devices for the common cause of scientific computing via analogical simulations. Faulty devices or lack of wireless coverage leads to “gaps” in a WAdL, rendering it ineffective for analogical simulations.

In this paper we discuss our soultion to the problem of bridging gaps in WAdLs by assigning active devices on the perimeter of the gap as proxies for the defective devices in the gap. We establish lower bounds on the communication dilation witnessed by such proxy assignments for single-row gaps and general row-column convex gaps, and present dilation-optimal, constant time algorithms for computing proxy assignments for single-row gaps and gaps that are rectangular in shape.

We present the first location oblivious distributed unit disk graph coloring algorithm having a provable performance ratio of three (i.e. the number of colors used by the algorithm is at most three times the chromatic number of the graph). This is an improvement over the standard sequential coloring algorithm since we present a new lower bound of 10/3 for the worst-case performance ratio of the sequential coloring algorithm. The previous greatest lower bound on the performance ratio of the sequential coloring algorithm was 5/2. Using simulation, we also compare our algorithm with other existing unit disk graph coloring algorithms.

Let be a -edge connected graph and denote the diameter of after deleting any of its  <  edges. We prove that if , , ..., are -edge connected, -edge connected,..., -edge connected graphs and 0 ≤  < , 0 ≤  < ,..., 0 ≤  <  and  =  +  + ... +  + ( − 1), then the edge fault-diameter of , the Cartesian product of , , ..., , with faulty edges is

This paper studies the problem of broadcasting in synchronous point-to-point networks, where one initiator owns a piece of information that has to be transmitted to all other vertices as fast as possible. The model of fractional dynamic faults with threshold is considered: in every step either a fixed number , or a fraction , of sent messages can be lost depending on which quantity is larger.

As the main result we show that in complete graphs and hypercubes it is possible to inform all but a constant number of vertices, exhibiting only a logarithmic slowdown, i.e. in time (log) where is the diameter of the network and is the number of vertices.

Moreover, for complete graphs under some additional conditions (sense of direction, or < 0.55) the remaining constant number of vertices can be informed in the same time, i.e. (log).