Accepted Papers

Aleksej Di Salvo and Guido Proietti: "Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor"

Abstract: We consider a 2-edge connected, undirected graph $G=(V,E)$, with $n$ nodes and $m$ non-negatively real weighted edges, and a single source shortest paths tree (SPT) $T$ of $G$ rooted at an arbitrary node $r$. If an edge in $T$ is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge, instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an $O(m\log^2n)$ time and linear space algorithm to find a best swap edge for every edge of $T$, thus improving for $m = o \left( n^2/\log^2 n \right)$ the previously known $O(n^2)$ time and space complexity algorithm.

Alessandro Ferrante and Mimmo Parente: "Existence of Nash Equilibria in Selfish Routing problems"

Abstract: The problem of routing traffic through a congested network is studied. The framework is that described by Koutsoupias and Papadimitriou where the network is constituted by m parallel links, each having a finite capacity and there are n selfish agents wishing to route their traffic through one of these links: thus the problem sets naturally in the context of noncooperative games. Given the lack of coordination among the agents in large networks, much effort has been lavished in the framework of mixed Nash equilibria where the agent's routing choices are regulated by probabilistic distribution, one for each agent, which let the system reach thus a stochastic steady state from which no agent is willing to deviate unilaterally. Recently Mavronicolas and Spirakis have investigated fully mixed equilibria, where agents have all non zero probabilities to route their traffics on the links. Here we concentrate on constrained situations where some agents are forbidden to route their traffic on some links: in this case we show that at most one Nash equilibrium may exist and we give necessary and sufficient conditions on its existence; the conditions relating the traffic load of the agents. We study also a dynamic behaviour of the network, establishing under which conditions the network is still in equilibrium when some of the constraints are removed. All these conditions are effective in the sense that given a set of yes/no routing constraints on each link for each agent, we provide the probability distributions that achieve the unique Nash equilibrium associated to the constraints (if it exists).

Anat Bremler-Barr and Leah Epstein: "Path layout on tree networks: Bounds in different label switching models"

Abstract: Path Layout is a fundamental graph problem in label switching protocols. This problem is raised in various protocols such as the traditional ATM protocol and MPLS which is a new label switching protocol standardized recently by the IETF. Path layout is essentially the problem of reducing the size of the label-table in a router. The size is equivalent to the number of different paths that pass through the router, or start from it. A reduction in the size can be achieved by choosing a relatively small number of paths, from which a larger set is composed using concatenation. In this paper we deal with three variations of the Path Layout Problem according to the special characteristics of paths in three label switching protocols, MPLS, ATM and TRAINET. We focus on tree networks, and show an algorithm which finds label-tables of small size, while permitting concatenation of at most k paths. We prove that this algorithm gives worst case tight bounds (up to constant factor) for all three models. The bounds are given as a function of the size of the tree, and the maximum degree.

Arvind Gupta, Jan Manuch and Ladislav Stacho: "Fault tolerant forwarding and optical indexes - a design theory approach"

Abstract: We study the problem of designing fault tolerant routings in complete and complete bipartite optical networks. We show that this problem has strong connections to various fundamental problems in design theory. Using design theory approach, we find optimal $f$-tolerant arc-forwarding indexes for complete networks of a prime power order, and all complete bipartite networks. Similarly, we find almost exact values for $f$-tolerant optical indexes for these networks. Our work motivates an interesting relaxation of an extensively studied problem on mutually orthogonal Latin squares.

Bogdan Chlebus and Mariusz Rokicki: "Asynchronous Broadcast in Radio Networks"

Abstract: We study asynchronous packet radio networks in which transmissions among nodes may be delayed. We consider the task of broadcasting a message generated by a source node. The timing of arrivals of messages is controlled by adversaries. We consider three different adversaries. The edge adversary can have a transmitted message delivered at different times to different recipients. The crash adversary is the edge one augmented by a power to crash nodes. The node adversary can have a message received at arbitrary times, but simultaneously by all the recipients. A protocol specifies for each node how many times the message is retransmitted by this node, after it has been received. The total number of transmissions of nodes is defined to be a measure of performance of a broadcast protocol, and is called its work. The radio network is modeled as a graph and is given as input to a centralized algorithm. An aim of the algorithm could be either to find a broadcast protocol, possibly with additional properties, or to verify correctness of a given protocol. We give an algorithm to find a protocol correct against the edge adversary. The obtained protocol is work-exponential in general. This is an inherent property of the problem, as is justified by a lower bound. We develop a polynomial algorithm to verify correctness of a given protocol for a given network against the edge adversary. We show that a problem to decide if there exists a protocol, for a given network and of a specified work performance, is NP-hard. We extend some of these results to the remaining two adversaries.

Chryssis Georgiou, Peter Musial, and Alex Shvartsman: "Long-Lived Rambo: Trading Knowledge for Communication"

Abstract: Shareable data services providing consistency guarantees, such as atomicity (linearizability), make building dynamic distributed systems easier. In general it is difficult to combine the guarantee of linearizability with efficiency and practicality. A reconfigurable linearizable data service, called \RAMBO{}, was developed by Lynch and Shvartsman. This service guarantees consistency under dynamic conditions involving asynchrony, message loss, node crashes, and new node arrivals. The specification of the original algorithm is given at an abstract level aimed at concise presentation and formal reasoning about correctness. The algorithm propagates information by means of gossip messages. If the service is in use for a very long time, the size and the number of gossip messages may grow without bound. First, \RAMBO{} allows new nodes to join the computation, but it does not allow the nodes to leave gracefully (other than failing). Given that in asynchronous systems failure detection is difficult, it may be impossible to distinguish departed nodes from the nodes that crash. Second, \RAMBO{} gossips information without regard for what may already be known. % This paper presents a consistent data service for \emph{long-lived} objects that improves on \RAMBO{} in two ways: it includes an incremental communication protocol and a leave service. Together with \RAMBO{} object management algorithm, this yields a practical and long-lived atomic data service. The new protocol taking advantage of the local knowledge, and it carefully manages the size of messages by removing redundant information from messages, while the leave service allows the nodes to leave the system gracefully. The incremental communication protocol is designed to ensure correctness in the asynchronous settings with message loss and node crashes. The new algorithm is formally proved correct by forward simulation using levels of abstraction. By trading knowledge for communication the algorithm substantially reduces the number and the size of gossip messages. An experimental implementation of the system was developed for networks-of-workstations. The paper includes analytical and preliminary empirical results that illustrate the advantages of the new algorithm.

Deshi Ye and Hu Zhang: "The Range Assignment Problem in Static Ad-Hoc Networks on Metric Spaces"

Abstract: In this paper we study the range assignment problem in static ad-hoc networks on metric spaces. We consider the $h$-strong connectivity and $h$-broadcast problems on trees, high dimensional Euclidean spaces and general metric spaces. Both homogeneous and non-homogeneous cases are explored. We prove that the $h$-broadcast problem is polynomial solvable on trees and there exists an $O(n^2)$-approximation algorithm for the $h$-strong connectivity problem on trees. Furthermore, we propose a probabilistic $O(\log n \log\log n)$-approximation algorithm for the $h$-broadcast problem and a probabilistic $O(n^2 \log n \log\log n)$-approximation algorithm for the $h$-strong connectivity problem on high dimensional Euclidean spaces and general metric spaces, where $n$ is the number of stations. In the case of high dimensional Euclidean spaces and general metric spaces, if the distance-power gradient $\alpha\leq 1+O(\log\log\log n/\log\log n)$, an $O(\log^{\al} n)$-approximation algorithm and an $O(n^2 \log^{\al} n)$-approximation algorithm are developed for the $h$-broadcast problem and the $h$-strong connectivity problem, respectively. They are the first algorithms for the range assignment problem in static ad-hoc networks on general metric spaces. And the approximation ratio of $O(\log n \log\log n)$ for the $h$-broadcast problem on general metric spaces is close to the known lower bound $O(\log n)$ [G. Rossi, The Range Assignment Problem in Static Ad-Hoc Wireless Networks, Ph.D. Thesis, 2003].

Deshi Ye, Guochuan Zhang: "On-line scheduling of parallel jobs"

Abstract: We study an on-line parallel job scheduling problem, where jobs arrive over list. A parallel job may require a number of machines for its processing at the same time. Upon the arrival of a job, its processing time and the number of requested machines become known, and it must be scheduled immediately without any knowledge of future jobs. We present a 8-competitive on-line algorithm, which improves the previous upper bound of 12 by Johannes (2001). Furthermore, we investigate two special cases and show better bounds.

Eric Angel, Evripidis Bampis, Fanny Pascual: "Traffic grooming in a passive star WDM network"

Abstract: We consider the traffic grooming problem in passive WDM star networks. Traffic grooming is concerned with the development of techniques for combining low speed traffic components onto high speed channels in order to minimize network cost. We first prove that the traffic grooming problem in star networks is NP-hard for a more restricted case than the one considered in [1]. Then, we propose a polynomial time algorithm for the special case where there are two wavelengths per fiber, using matching techniques. Furthermore, we propose two reductions of our problem to two combinatorial optimization problems (the constrained multiset multicover problem, and the demand matching problem), allowing us to obtain a polynomial time log(2C) (resp. 2+(13/16)) approximation algorithm for the minimization (resp. maximization) version of the problem, where $C$ is the capacity of each wavelength. [1]: R. Dutta and G.N. Rouskas, "On Optimal Traffic Grooming in WDM Rings", IEEE Journal on selected areas in communications, Vol. 20, No. 1, January 2002.

Fertin, G.and Raspaud, A. and Sykora, O.: "No-Hole L(p,0) Labelling of Cycles, Grids and Hypercubes"

Abstract: In this paper, we address a particular case of the general problem of lambda labellings, concerning frequency assignment for telecommunication networks. In this model, stations within a given radius r must use frequencies that differ at least by a value p, while stations that are within a larger radius r'>r must use frequencies that differ by at least another value q. The aim is to minimize the span of frequencies used in the network. This can be modelled by a graph labelling problem, called the L(p,q) labelling, where one wants to label vertices of the graph G modelling the network by integers in the range [0;M], while minimizing the value of M. M is then called the lambda number of G, and is denoted by $\lambda_q^p (G)$. Another parameter that sometimes needs to be optimized is the fact that all the possible frequencies (i.e., all the possible values in the span) are used. In this paper, we focus on this problem. More precisely, we want that: (1) all the frequencies are used and (2) condition(1) being satisfied, the span must be minimum. We call this the no-hole L(p,q) labelling problem for G. Let [0;M'] be this new span and call the $\nu$ number of G the value M', and denote it by $\nu^p_q(G)$. In this paper, we study a special case of no-hole L(p,q) labelling, namely where q=0. We also focus on some specific topologies: cycles, hypercubes, 2-dimensional grids and 2-dimensional tori. For each of the mentioned topologies cited above, we give bounds on the $\nu_0^p$ number and show optimality in some cases. The paper is concluded by giving new results concerning the (general, i.e. not necessarily no-hole) L(p,q) labelling of hypercubes.

Flaminia L. Luccio and Jop F. Sibeyn: "Tighter Bounds on Feedback Vertex Sets in Mesh-based Networks"

Abstract: In this paper we consider the minimum feedback vertex set problem in graphs, i.e., the problem of finding a minimal cardinality subset of the vertices, whose removal makes a graph acyclic. The problem is N P-hard for general topologies, but optimal and near-optimal solutions have been provided for particular networks. In this paper the problem is considered for undirected graphs with the following topologies: two- and higher-dimensional meshes of trees, trees of meshes and pyramid networks. For the meshes of trees and the tree of meshes the results are asymptotically optimal. For the pyramid networks, the presented upper and lower bounds are almost matching.

G.Cordasco, L.Gargano, M. Hammar, A.Negro, V. Scarano: "F-Chord: Improved Uniform Routing on Chord"

Abstract: We propose a family of novel schemes based on Chord retaining all positive aspects that made Chord a popular topology for routing in P2P networks. The schemes, based on the Fibonacci number system, allow to improve on the maximum/average number of hops for lookups and the routing table size per node.

Janka Chlebikova and Miroslav Chlebik: "On Approximability of the Independent Set Problem for Low Degree Graphs"

Abstract: We obtain slightly improved upper bounds on efficient approximability of the Maximum Independent Set problem in graphs of maximum degree at most B (shortly, B-MaxIS), for small B>=3. The degree-three case plays a role of the central problem, as many of the results for the other problems use reductions to it. Our careful analysis of approximation algorithms of Berman and Fujito for 3-MaxIS shows that one can achieve approximation ratio arbitrarily close to 3-\sqrt{13}/2. Improvements of approximation factor below 6/5 for this case translate to improvements below (B+3)/5 of approximation factors for B-MaxIS for all odd~B. Consequently, for any odd B>= 3, a polynomial time algorithm for B-MaxIS exists with approximation ratio arbitrarily close to (B+3)/5-[[4(5\sqrt{13}-18)]/5].[(B-2)!!][(B+1)!!]. This is currently the best upper bound for B-MaxIS for any odd B, 3<= B<613.

Leszek Gasieniec, Igor Potapov, and Qin Xin: "Time efficient gossiping in known radio networks"

Abstract: We study here a gossiping problem (all-to-all communication) in known radio networks, i.e., when all nodes are aware of the network topology. We start our presentation with a deterministic algorithm for the gossiping problem that works in at most $n$ units of a time in any radio network of size $n$. This is an optimal algorithm in the sense that there exist radio network topologies, such as: a line, a star and a complete graph in which the radio gossiping cannot be completed in less then $n$ units of time. Further, we show that there isn't any radio network topology in which the gossiping task can be solved in time $<\lfloor\log(n-1)\rfloor+2.$ We show also that this lower bound can be matched from above for a fraction of all possible integer values of $n;$ and for all other values of $n$ we propose a solution admitting gossiping in time $\lceil\log(n-1)\rceil+2.$ We show later an ({\sl one-off}\/) optimal radio gossiping in trees. Finally we study asymptotically optimal $O(D)$-time gossiping (where $D$ is a diameter of the network) in graphs with max-degree $\Delta=O(\frac{D^{1-1/(i+2)}}{\log^{i+1} n}),$ for any integer constant $i\ge 0$ and $D$ large enough.

Luciano Margara, Alessandro Pistocchi, Marco Vassura: "Perfect Token Distribution on Trees"

Abstract: Load balancing on a multi-processor system consists of redistributing tasks among processors so that all processors end up with roughly the same amount of work to perform. The token distribution problem is a variant of the load balancing problem where each task has unit-size and it represents an atomic element of work. We present an algorithm for computing a perfect token distribution on distributed tree-connected networks having worst-case running time O(TD) (D denotes the diameter of the tree and T denotes the total number of tokens). This is the first fully decentralized algorithm for computing perfect token distributions on arbitrary tree-connected networks which does not receive as input any kind of aggregate information about the network (e.g., number of nodes or total number of tokens).

Michel Paquette, Andrzej Pelc: "Optimal decision strategies in Byzantine environments"

Abstract: A Boolean value of given a priori probability distribution is transmitted to a deciding agent by several processes. Each process fails independently with given probability, and faulty processes behave in a Byzantine way. A deciding agent has to make a decision concerning the transmitted value on the basis of messages obtained by processes. We construct a deterministic decision strategy which has the provably highest probability of correctness. It computes the decision in time linear in the number of processes. Decision optimality may be alternatively approached from a local, rather than global, point of view. Instead of maximizing the total probability of correctness of a decision strategy, we may try to find, for every set of values conveyed by processes, the conditionally most probable original value that could yield this set. We call such a strategy locally optimal, as it locally optimizes the probability of a decision, given a set of relayed values, disregarding the impact of such a choice on the overall probability of correctness. We construct a locally optimal decision strategy which again computes the decision value in time linear in the number of processes. We establish the surprising fact that, in general, local probability maximization may lead to a decision strategy which does not have the highest probability of correctness. However, if the probability distribution of the Boolean value to be conveyed is uniform, and all processes have the same failure probability smaller than 1/2, this anomaly does not occur.

Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Flaminia Luccio, Nicola Santoro, Cindy Sawchuk: "Mobile Agent Rendezvous When Tokens Fail"

Abstract: The mobile agent rendezvous problem consists of k = 2 or more mobile agents trying to rendezvous or meet in a minimum amount of time on an n node ring network. Tokens and markers have been used successfully to achieve rendezvous when the problem is symmetric, e.g., the network is an anonymous ring and the mobile agents are identical and run the same deterministic algorithm. In this paper, we explore how token failure affects the time required for mobile agent rendezvous under symmetric conditions with different types of knowledge. Our results suggest that knowledge of n is better than knowledge of k in terms of achieving rendezvous as quickly as possible in the faulty token setting.

Paolo Penna and Carmine Ventre: "Sharing the Cost of Multicast Transmissions in Wireless Networks"

Abstract: We investigate the problem of sharing the cost of a multicast transmission in a wireless network where each node (radio station) of the network corresponds to a (set of) user(s) potentially interested in receiving the transmission. As in the model considered by Feigenbaum \emph{et al} [2001], users may act \emph{selfishly} and report a false ``level of interest'' in receiving the transmission trying to be charged less by the system. We consider the issue of designing so called \emph{truthful mechanisms} for the problem of maximizing the \emph{net worth} (i.e., the overall ``happiness'' of the users minus the cost of the transmission) for the case of \emph{wireless} networks. Intuitively, truthful mechanism guarantee that no user has an incentive in reporting a false valuation of the transmission. Unlikely the ``wired'' network case, here the cost of a set of connections implementing a multicast tree is \emph{not} the sum of the single edge costs, thus introducing a complicating factor in the problem. We provide both positive and negative results on the existence of optimal algorithms for the problem and their use to obtain VCG truthful mechanisms achieving the same performances.

Paul Boone, Edgar Chavez, Lev Gleitzky, Evangelos Kranakis, Jaroslav Opatrny, Gelasio Salazar, Jorge Urrutia: "Morelia Test: Improving the Efficiency of the Gabriel Test and Face Routing in Ad-hoc Networks"

Abstract: An important technique for discovering routes between two nodes in an ad-hoc network involves application of the face routing algorithm on a planar spanner of the network. Face routing on a planar subgraph guarantees message delivery in networks whose geometrical representation contains large holes without any node and having complex contours, where the usual greedy algorithms fail. Existing techniques for constructing a suitable planar spanner involve local tests that eliminate crossings between existing links by deleting some of the links. The existing tests do not test whether the deleted links actually create some crossings and some of the links are deleted needlessly. As a result, the routes in the face routing will have an unnecessarily large number of hops from source to destination. We consider a new local test for preprocessing a wireless network that produces a planar subgraph on which we can apply face routing. The test is relatively simple, requires low overhead and does not unnecessarily eliminate existing links unless it is needed to eliminate a crossing, thus reducing overhead usually associated with multiple hops.

R. Wang, F.C.M. Lau, Y. Liu: "NP-Complete Results for All-Shortest Paths Interval Routing"

Abstract: $k$-Interval Routing Scheme ($k$-IRS) is a compact routing method that allows up to $k$ interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit $k$-IRS. All the problems related to single-shortest path $k$-IRS have already been shown to be NP-compete. For all-shortest paths $k$-IRS, the characterization problem remains open for $k\geqslant 1$. We investigate the time complexity of devising minimal-space all-shortest paths $k$-IRS and prove that it is NP-complete to decide whether a graph admits an all-shortest paths $k$-IRS, for every integer $k\geqslant 3$, as well as whether a graph admits an all-shortest paths $k$-strict IRS, for every integer $k\geqslant 4$. These are the first NP-completeness results for all-shortest paths $k$-IRS where $k$ is a constant and the graph is unweighted. Moreover, the NP-completeness holds also for the linear case.

Rachel Matichin, David Peleg: "Approximation Algorithm for Hotlink Assignment in the Greedy Model"

Abstract: Link-based information structures such as the web can be enhanced through the addition of hotlinks. Assume that each node in the information structure is associated with a weight representing the access frequency of the node by users. In order to access a particular node, the user has to follow a path leading to it from the root node. By adding new hotlinks to the tree, it may be possible to reduce the access cost of the system, namely, the expected number of steps needed to reach a leaf from the root, assuming the user can decide which hotlinks to follow in each step. The hotlink assignment problem involves finding a set of hotlinks maximizing the gain in the expected cost. The paper addresses this problem in the more realistic greedy user model recently introduced in [GKMP03], and presents a polynomial time 2-approximation algorithm for the hotlink assignment problem on trees.

Reuven Cohen, David Peleg: " Robot Convergence via Center-of-Gravity Algorithms"

Abstract: Consider a group of N robots aiming to converge towards a single point. The robots cannot communicate, and their only input is obtained by visual sensors. A natural algorithm for the problem is based on requiring each robot to move towards the robots' center of gravity. The paper proves the correctness of the center-of-gravity algorithm in the semi-synchronous model for any number of robots, and its correctness in the fully asynchronous model for two robots.

S. Choplin, L. Narayanan, J. Opatrny: "Two-Hop Virtual Path Layout in Tori"

Abstract: We consider the problem of D-hop virtual path layout in ATM (Asynchronous Transfer Mode) networks. Given a physical network and an all-to-all traffic pattern, the problem consists of designing a virtual network with a given diameter D, which can be embedded in the physical one with a minimum congestion (the congestion is the maximum load of a physical link). Here we propose a method to solve this problem when the diameter is 2. We use this method to give an asymptotically optimal solution for the 2-hop virtual path layout problem for all-to-all traffic when the physical network is a mesh, a torus or a chordal ring.

Stefan Dobrev, Paola Flocchini, Nicola Santoro: "Improved Bounds for Optimal Black Hole Search\\ with a Network"

Abstract: A black hole is a harmful host that destroys incoming agents without leaving any observable trace of such a destruction. The black hole search problem is to unambiguously determine the location of the black hole. A team of agents, provided with a network map and executing the same protocol, solves the problem if at least one agent survives and, within finite time, knows the location of the black hole. It is known that a team must have at least two agents. Interestingly, two agents with a map of the network can ocate the black hole with O(n) moves in many highly regular networks; however the protocols used apply only to a narrow class of networks. On the other hand, any universal solution protocol must use Omega(n log n) moves in the worst case, regardless of the number of agents. In this paper we present a universal protocol that allows a team of two agents with a network map to locate the black hole using at most O(n + d log d) moves, where d is the diameter of the network. This means that, without losing its universality and without violating the worst-case \Omega(n log n) lower bound, this algorithm allows two agents to locate a black hole with Theta(n) cost in a very large class of (possibly unstructured) networks: those where d = O(n/log n).

Vittorio Biló and Luca Moscardelli: "The price of anarchy in all-optical networks"

Abstract: In this paper we consider all-optical networks in which a service provider has to satisfy a given set of communication requests. Each request is charged a cost depending on its wavelength and on the wavelengthsof the other requests met along its path in the network. Under the assumption that each request is issued bya selfish agent, we seek for payment strategies which can guarantee the exisyence of a pure Nash equilibrium,that is of paths to the requests so that no request can lower its cost by choosing a different path in the network.For such strategies, we bound the loss of performance of the network (price of anarchy) by comparing the numberof wavelengths used by the worst pure Nash equilibrium with that of a centralized optimal solution.

Yon Dourisboure and Cyril Gavoille: "Sparse Additive Spanners for Bounded Tree-Length Graphs"

Abstract: This paper concerns construction of additive stretched spanners with few edges for $n$-vertex graphs having a tree-decomposition into bags of diameter at most $\delta$, i.e., the tree-length $\delta$ graphs. For such graphs we construct additive $2\delta$-spanners with $O(\delta n\log n)$ edges, and additive $6\delta$-spanners with $O(\delta n)$ edges. We also show a lower bound, and prove that there are graphs of tree-length $\delta$ for which every multiplicative $\delta$-spanner (and thus every additive $(\delta-1)$-spanner) requires $\Omega(n^{1+1/\Theta(\delta)})$ edges.