Catálogo de publicaciones - libros

The problem we consider originates from the design of efficient on-board networks in satellites (also called Traveling Wave Tube Amplifiers). Signals incoming in the network through ports have to be routed through an on-board network to amplifiers. The network is made of expensive switches with four links and subject to two types of constraints. First, the amplifiers may fail during satellite lifetime and cannot be repaired. Secondly, as the satellite is rotating, all the ports are not well oriented and hence not available. Let us assume that we have  +  ports (inputs) and  +  amplifiers (outputs), then a amplifiers (outputs), then a (,,)−network is said to be if, for any choice of inputs and outputs, there exist edge-disjoint paths linking all the chosen inputs to all the chosen outputs. Then, the objective is to design a valid network having the minimum number of switches denoted (,,). In the special case where = 0, these networks were already studied as . Here we present validity certificates from which derive lower bounds for (,,); we also provide constructions of optimal (or quasi optimal) networks for practical values of and (1 ≤  ≤  ≤ 8) and a general way to build networks for any and any .

This paper studies a gathering problem for a system of asynchronous autonomous mobile robots that can move freely in a two-dimensional plane. We consider robots equipped with inaccurate (incorrect) compasses which may point a different direction from other robots’ compasses. A gathering problem is that the robots are required to eventually gather at a single point which is not given in advance from any initial configuration.

In this paper, we propose several inaccurate compass models and give two algorithms which solve the gathering problem on these models. One algorithm is the first result dealing with the compasses whose indicated direction may change in every beginning of execution cycles of robots. It solves the problem when compasses point different at most /8 from the (absolute) north. The other one solves the problem when the compasses never change its pointed direction and their difference is at most /3 among robots.

The recently established computational equivalence between the traditional message-passing model and the mobile-agents model is based on the existence of a mobile-agents algorithm that simulates the execution of message-passing algorithms. Like most existing protocols for mobile agents, this simulation protocol works correctly only if the agents are fault-free.

We consider the problem of performing the simulation of message-passing algorithms when the simulating agents may crash unexpectedly. We show how to simulate any distributed algorithm for the message-passing model in a mobile-agents system with agents, tolerating up to  ≤  − 1 crashes during the simulation. Two fault-tolerant simulation algorithms are presented, one for non-anonymous settings (i.e., where either the networks nodes or the agents or both have distinct identities), and one for anonymous systems (where both the network nodes and the agents are anonymous). In both cases, the simulation overhead is polynomial.

Unlike the existing fault-free simulation algorithm, both our protocols are able to detect termination even if the simulated algorithm has no explicit termination detection.

A set of input vectors is conclusive if correct functionality for all input vectors is implied by correct functionality over vectors in . We consider four functionalities of comparator networks: sorting, merging of two equal length sorted vectors, sorting of bitonic vectors, and halving (i.e., separating values above and below the median). For each of these functionalities, we present tight lower and upper bounds on the size of conclusive sets. Bounds are given both for conclusive sets composed of binary vectors and of general vectors. The bounds for general vectors are smaller than the bounds for binary vectors implied by the 0-1 principle. Our results hold also for comparator networks with unbounded fanout.

Assume the network at hand has inputs and outputs, where is even. We present a conclusive set for sorting that contains nonbinary vectors. For merging, we present a conclusive set with nonbinary vectors. For bitonic sorting, we present a conclusive set with nonbinary vectors. For halving, we present binary vectors that constitute a conclusive set. We prove that all these conclusive sets are optimal.

We consider the problem of characterizing user equilibria and optimal solutions for selfish routing in a given network. We extend the known models by considering users . While in the typical selfish routing setting the users follow a strategy that minimizes their individual cost by taking into account the (dynamic) congestion due to the current routing pattern, an user ignores congestion altogether. Instead, he decides his routing on the basis of cheapest routes on a network without any flow whatsoever. These cheapest routes can be, for example, the shortest paths in the network without any flow. This model tries to capture the fact that routing tables for at least a fraction of the flow in large scale networks such as the Internet may be based on the physical distances or hops between routers alone. The phenomenon is similar to the case of traffic networks where a certain percentage of travelers base their route simply on the distances they observe on a map, without thinking (or knowing, or caring) about the delays experienced on this route due to their fellow travelers. In this work we study the price of anarchy of such networks, i.e., the ratio of the total latency experienced by the users in this setting over the optimal total latency if all users were centrally coordinated.

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We show that, for a reducible graph , the minimum number of required rounds is , where is the independence number of . This upper bound is tight and the result implies the square-root conjecture which was first posed in MFCS 2004. We also show that for reducible -free graphs at most  − 1 rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time.