Accepted Papers

Vincenzo Auletta, Roberto De Prisco, Paolo Penna and Giuseppe Persiano: "On Designing Truthful Mechanisms for Online Scheduling"

Abstract: We study the *online* version of the scheduling problem involving *selfish agents* considered by Archer and Tardos [FOCS 2001]: jobs must be scheduled on $m$ parallel related machines, each of them owned by a different *selfish agent*. Our study focuses on general techniques to translate approximation/competitive algorithms into equivalent approximation/competitive *truthful mechanisms*. Our results show that this translation is more problematic in the online setting than in the offline one. For $m=2$, we develop an offline and an online ``translation'' technique which, allow to obtain $f(\rho)$-approximation/competitive (polynomial-time) mechanism starting from *any* $\rho$-approximation/competitive (polynomial-time) algorithm, with $f(\rho)= \rho(1+\epsilon)$ in the offline case, for every $\epsilon >0$. By contrast, one of our lower bounds implies that, in general, online $\rho$-competitive algorithms cannot be turned into $\rho(1+ \epsilon)$-competitive mechanisms, for some $\epsilon>0$ and every $m\geq 2$. We also investigate the issue of designing new online algorithms from scratch so to obtain efficient competitive mechanisms, and prove some lower bounds on a class of ``natural'' algorithms. Finally, we consider the variant introduced by Nisan and Ronen [STOC 1999] in which machines can be *verified*. For this model, we give a $O(1)$-competitive online mechanism for *any* number of machines and prove that some of the above lower bounds can be broken.

Amos Beimel: "On Private Computation in Incomplete Networks"

Abstract: Suppose that some parties are connected by an incomplete network of reliable and private channels. The parties cooperate to execute some protocol. However, the parties are curious -- after the protocol terminates each processor tries to learn information from the communication it heard. We say that a function can be computed privately in a network if there is a protocol in which each processor learns only the information implied by its input and the output of the protocol. The question we address in this paper is what functions can be computed privately in a given incomplete network. It is known that if a network is 2-connected then every pair of parties can communicate privately. Thus, the question is intersting only for non-2-connected networks. We first characterize the functions that can be computed privately in simple networks -- networks with one separating vertex and two 2-connected components. We then deal with private computations in arbitrary networks: we reduce this question to private computations of related functions on trees, and give sufficient and necessary conditions on the functions that can be computed privately on trees.

Jean-Claude Bermond and Laurent Braud and David Coudert: "Traffic Grooming on the Path"

Abstract: In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most 1/C of the bandwidth of the wavelength, we will say that the grooming factor is C. That means that on a given edge of the network we can groom (group) at most C requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexer (shortly ADM) used in the network (related to the cost of the nodes). Here we consider the case where the network is a path on N nodes, P_N. Thus the routing is unique. For a given grooming factor C minimizing the number of wavelengths is an easy problem, well known and related to the load problem. But minimizing the number of ADM's is NP-complete for a general set of requests and no results are known. Here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where C=2 and where we have a static uniform all-to-all traffic (requests being all pairs of vertices).

Davide Bilo, Guido Proietti: "Range Augmentation Problems in Static Ad-Hoc Wireless Networks"

Abstract: Given a set $V$ of $n$ stations, a transmission power cost function $c:V\times V\mapsto \mathbb{R^+}\cup\{+\infty\}$, an initial power assignment $p_0: V\mapsto \mathbb{R^+}$, and a connectivity property $\pi$, a \emph{range augmentation problem} consists of finding a minimum power augmentation assignment $p$ such that $p_f(\cdot)=p_0(\cdot)+p(\cdot)$ satisfies property $\pi$. In this paper, we focus on the problem of increasing the connectivity of an already existing connected network, to make it resilient to the failure of either a wireless link or a station. For these problems we give a ${\cal H}^2_n$-approximation greedy algorithm (where ${\cal H}_n$ is the $n$-th harmonic number) after proving that they are both not approximable within $(1- o(1))\ln n$, unless NP $\subset$ DTIME$(n^{{\cal O}(\log\log n)})$, even when $c$ is a distance cost function restricted to three power levels, or it is a distance cost function and $p_0$ induces a tree network. Moreover, we prove that both problems remain APX-hard even if the initial power assignment is uniform. In this latter scenario, we finally show that any $\lambda$-approximation algorithm for the corresponding problem in wired networks, is a $2\lambda$-approximation algorithm for the wireless case.

Tiziana Calamoneri and Paola Vocca: "On the Approximability of the $L(h,k)$-Labelling"

Abstract: Given an undirected graph $G$, an \Lhk\ of $G$ assigns colors to vertices from the integer set $\{0, \ldots,\lambda_{h,k}\}$, such that any two vertices $v_i$ and $v_j$ receive colors $c(v_i)$ and $c(v_j)$ satisfying the following conditions: \emph{i)} if $v_i$ and $v_j$ are adjacent then $|c(v_i)-c(v_j)|\geq h$; \emph{ii)} if $v_i$ and $v_j$ are at distance two then $|c(v_i)-c(v_j)|\geq k$. The aim of the \Lhk\ problem is to minimize $\lambda_{h,k}$. In this paper we study the approximability of the \Lhk\ problem on bipartite graphs and extend the results to $s$-partite and general graphs. Indeed, the decision version of this problem is known to be NP-complete in general and, to our knowledge, there are no polynomial solutions, either exact or approximate, for bipartite graphs. Here, we state some results concerning the approximability of the \Lhk\ problem for bipartite graphs, exploiting a novel technique, consisting in computing approximate vertex- and edge-colorings of auxiliary graphs to deduce an $L(h,k)$-labelling for the input bipartite graph. We derive an approximation algorithm with performance ratio bounded by $\frac{4}{3} D^2$, where, $D$ is equal to the minimum even value bounding the minimum of the maximum degrees of the two partitions. One of the above coloring algorithms is in fact an approximating edge-coloring algorithm for hypergraphs of maximum dimension $d$, i.e. the maximum edge cardinality, with performance ratio $d$. Furthermore, we consider a different approximation technique based on the reduction of the \Lhk\ problem to the vertex-coloring of the square of a graph. Using this approach we derive an approximation algorithm with performance ratio bounded by $\mbox{min}(h,2k)\sqrt{n}+o(k\sqrt{n})$, assuming $h \geq k$. Hence, the first technique is competitive when $D=O(n^{1/4})$. We then extend the latter approximation strategy to $s$-partite graphs, obtaining an $(\mbox{min}(h,sk)\sqrt{n}+o(sk\sqrt{n}))$-approximation ratio, and to general graphs deriving an $(h\sqrt{n}+o(h\sqrt{n}))$-approximation algorithm, assuming $h\geq k$. Finally, we prove that the \Lhk\ problem is not easier than coloring the square of a graph.

Ioannis Caragiannis, Aleksei V. Fishkin, Christos Kaklamanis, Evi Papaioannou: "A tight bound for online coloring of disk graphs"

Abstract: We present an improved upper bound on the competitiveness of the online coloring algorithm {\sf First-Fit} in disk graphs which are graphs representing overlaps of disks on the plane. We also show that this bound is best possible for deterministic online coloring algorithms that do not use the disk representation of the input graph. We also present a related new lower bound for unit disk graphs.

A. Clementi, M. Di Ianni, M. Lauria, A. Monti , G. Rossi, R. Silvestri: "Divide et Impera is almost optimal for the bounded-hop MST problem on random Euclidean instances"

Abstract: The \ghmstd{h} problem is defined as follows: Given a set $S$ of points in the $d$-dimensional Euclidean space and $\root \in S$, find a minimum-cost spanning tree for $S$ rooted at $\root$ with height at most $h$. We investigate the problem for any constants $h$ and $d>0$. We prove the first non trivial lower bound on the solution cost \emph{for almost all} Euclidean instances (i.e. the lower-bound holds with hight probability). Then we introduce an easy-to-implement, very fast divide et impera heuristic and we prove that its solution cost matches the lower bound.

Shantanu Das, Paola Flocchini, Amiya Nayak, Nicola Santoro: "Distributed Exploration of an Unknown Graph"

Abstract: We consider a group of identical asynchronous agents, initially located at different nodes of an undirected simple graph. The nodes of the graph are unlabeled, and each contains a whiteboard where the visiting agents can write to and read from. The agents, initially, do not know the graph nor its topology. The only a-priori knowledge the agents may have is either the number $n$ of nodes, or the total number $k$ of agents. The goal is for the agents to construct a labelled map of the unknown graph, the same for all agents, so to be in complete agreement with each-other about their environment. This problem, called Labelled Map Construction, is closely related to a variety of other basic problems, including election and rendezvous. We are interested in efficient and generic protocols that can solve the problem, irrespective of the graph topology, where the cost of the algorithm is measured in terms of the total number of moves (or, edge traversals) made by the agents. We present a novel deterministic algorithm that, provided that $n$ and $k$ are co-prime (a necessary condition), constructs a map of the graph, elects a leader among the agents, and provides a unique labelling on the nodes of the graph. Our algorithm uses no more than $O(k\ m)$ edge traversals where $m$ is the number of edges in the graph. Our result improves on the finding by Barriere et al. for graphs with sense of direction, extending it to all labelled graphs, provided that one of $n$ or $k$ is known.

Yefim Dinitz and Noam Solomon: "Two Absolute Bounds for Distributed Bit Complexity"

Abstract: The concept of distributed communication bit complexity was introduced by Dinitz, Rajsbaum, and Moran. They studied bit complexity of Consensus and Leader Election, arriving at more or less exact bounds. This paper answers two questions on Leader Election, which remained open. The first is to close the gap between the known upper and lower bounds, for electing a leader by two linked processors. The second is whether the known algorithm, sending 1.5n bits while electing a leader in a chain of even length n, is optimal, in the case when $n$ is known to the processors. For both problems, absolutely exact bounds are found. Moreover, the lower bound proofs show that there is no optimal algorithm other than the suggested one(s).

Stefan Dobrev, Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung: "Finding Short Right-Hand-on-the-Wall Walks in Undirected Graphs"

Abstract: We consider the problem of {\em perpetual traversal} by a single agent in an undirected graph $G$. Our requirements are: (1) deterministic algorithm, (2) each node is visited within $O(n)$ moves, (3) the agent uses no memory, it can use only the label of the link via which it arrived to the current node, (4) no marking of the underlying graph is allowed and (5) no additional information is stored in the graph (e.g. routing tables, spanning tree) except the ability of each vertex to distinguish between the incident edges (called {\em local orientation}). The traversal is {\em perpetual}, i.e. we do not require the algorithm to recognize that it has already traversed the whole graph and that it can terminate. This problem is unsolvable, as has been proven in \cite{Bu78, Rol80} even for much less restrictive setting. Our approach is to somewhat relax the requirement (5). We fix the following traversal algorithm: {\em ``Start by taking the edge with the smallest label. Afterwards, whenever you come to a node, continue by taking the successor edge (in the local orientation) to the edge via which you arrived''} and ask whether it is possible for any given undirected graph to assign the local orientations in such a way that the resulting traversal visits every node in $O(n)$ moves. We give a positive answer to this question, by showing how to construct such local orientations. This leads to an extremely simple, memoryless, yet efficient traversal algorithm.

Pierre Fraigniaud, David Ilcinkas, Sergio Rajsbaum, S\'ebastien Tixeuil: "An $\Omega (\log n)$ space lower bound for graph exploration with stop (extended abstract)"

Abstract: We consider the task of exploring graphs with anonymous nodes by a team of non-cooperative robots modeled as finite automata. These robots have no \emph{a priori} knowledge of the topology of the graph, or of its size. Each edge has to be traversed by at least one robot. We first show that, for any set of $q$ non-cooperative $K$-state robots, there exists a graph of size $O(qK)$ that no robot of this set can explore. This improves the $O(K^{O(q)})$ bound by Rollik (1980). Our main result is an application of this improvement. It concerns exploration with stop, in which one robot has to explore and stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes. We prove that exploration with stop requires $\Omega(\log n)$ bits for the family of graphs with at most $n$ nodes. On the other hand, we prove that there exists an exploration with stop algorithm using a robot with $O(D \log \Delta)$ bits of memory to explore all graphs of diameter at most $D$ and degree at most $\Delta$.

Markus Hinkelmann, Andreas Jakoby: "Communications in Unknown Networks: Preserving the Secret of Topology."

Abstract: Cryptography investigates security aspects of data distributed in a network. This kind of security does not protect the secrecy of the network topology against being discovered if some kind of communication has to be established. But there are several scenarios where even the network topology has to be a part of the secret. In this paper we study the question of communication within a secret network where all processing nodes of the network have only partial knowledge (e.g.routing tables) of the complete topology. We introduce a model for measuring the loss of security of the topology when communication takes place. We will investigate lower bounds on the knowledge that can be deduced from the communication string. Several kinds of routing tables are not sufficient to guarantee the secrecy of topology. On the other hand, if a routing table allows to specify the direction from which a message is coming from we can run a protocol solving the all-to-all communication problem such that no processing node can gain additional knowledge about the network. Finally, we investigate the problem, whether a knowledge base can be generated from local knowledge of the processing nodes without losing the state of secrecy. It will be shown that this is not possible for static networks and most kinds of dynamic networks.

Taisuke Izumi and Toshimitsu Masuzawa: "An Improved Algorithm for Adaptive Condition-Based Consensus"

Abstract: Condition-Based Approach studies restrictions on the inputs of a distributed problem, called conditions, to circumvent several impossibility results. Especially, for the synchronous consensus problem, the relation between conditions and time complexity bounds has been studied. In our previous work, we introduced adaptiveness on time complexity of the condition-based approach, and established the adaptive condition-based approach: It classifies all possible input vectors into the hierarchical sequence of conditions according to their difficulty called legality level. For such hierarchy, adaptive algorithms achieve time complexity depending on the legality level of input vectors. In this paper, we propose an improved version of the adaptive condition-based algorithms for synchronous consensus that achives better time complexity than the previous one. On the assumption that majority of processes are correct, the proposed algorithm terminates within $\min\{f + 2, t+ 1\} - l$ rounds if $l < f$, where $f$ and $t$ is the actual and the maximum numbers of faults respectively, and $l$ is the legality level of input vectors. Moreover, the algorithm terminates in $1$ round if $l \geq t$ and $f=0$, and terminates within $2$ rounds if $l \geq f$ holds. Compared with our previous algorithm, the proposed algorithm improves time complexity by one round in the case of $f = t$ and $l > f$.

Branislav Katreniak: "Biangular circle formation by asynchronous mobile robots"

Abstract: Consider a community of simple autonomous robots (decentralized, asynchronous, no common coordinate system, no identities, no direct communication, no memory of the past, deterministic) moving freely in the plane and able to sense the positions of the other robots. We study the task of forming an absolutely symmetric formation -- regular circle. We do not reach this goal for all initial configurations, in general we form only a less symmetric formation -- biangular circle. Existing algorithms for similar tasks (forming a regular circle) are known only for stronger models (synchronous) and only converge to the final formation. In this paper we present an algorithm that solves the biangular circle formation problem deterministically in finite time.

Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco: "Hardness and approximation results for black hole search in arbitrary graphs"

Abstract: A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous arbitrary network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given graph and a given starting node we are interested in the fastest possible black hole search by two agents. We prove that finding a fastest black hole search scheme in an arbitrary graph is NP-hard, thus solving an open problem stated in \cite{CKMP04}. We also give a $39/11$-approximation algorithm for this problem, thus improving on the 4-approximation scheme observed in \cite{CKMP04}. Finally, we show that any black hole search scheme that explores the given input graph via some spanning tree cannot have an approximation ratio better than 3/2. Note that black hole search schemes based on spanning trees represent a very natural class of algorithms; our new algorithm also belongs to this class. We believe that more general classes of algorithms will be very difficult to analyze.

Rastislav Kralovic, Richard Kralovic: "On Semi-perfect 1-factorizations"

Abstract: The perfect 1-factorization conjecture by A. Kotzig [K63] asserts the existence of a 1-factorization of a complete graph K2n in which any two 1-factors induce a Hamiltonian cycle. This conjecture is one of the prominent open problems in graph theory. Apart from its theoretical significance it has a number of applications, particularly in designing topologies for wireless communication. Recently, a weaker version of this conjecture has been proposed for the case of semi-perfect 1-factorizations. A semi-perfect 1-factorization is a decomposition of a graph G into distinct 1-factors F1,...,Fk such that F1 U Fi forms a Hamiltonian cycle for any 1<i≤k. We show that complete graphs K2n, hypercubes Q2n+1 and tori T2n x 2n admit a semi-perfect 1-factorization.

Paolo Penna and Carmine Ventre: "Free-riders in Steiner tree cost-sharing games"

Abstract: We consider cost-sharing mechanisms for the Steiner tree game. In this well-studied *cooperative* game, each *selfish* user expresses his/her willingness to pay for being connected to a source node $s$ in an underlying graph. A *mechanism* decides which users will be connected and divides the cost of the corresponding (optimal) Steiner tree among these users (*budget balance* condition). Since users can form *coalitions* and misreport their willingness to pay, the mechanism must be *group strategyproof*: even coalitions of users cannot benefit from lying to the mechanism. We present new *polynomial-time* mechanisms which satisfy a standard set of axioms considered in the literature (i.e., budget balance, group strategyproofness, voluntary participation, consumer sovereignty, no positive transfer, cost optimality) and consider the *free riders* issue recently raised by Immorlica et al. [SODA 2005]: it would be desirable to avoid users that are connected for free. We also provide a number of negative results on the existence of *polynomial-time* mechanisms with certain guarantee on the number of free riders. Finally, we extend our technique and results to a variant considered by BilÚ et al. [SPAA 2004] with applications to *wireless* multicast cost sharing.

Giuseppe Prencipe: "On The Feasibility of Gathering by Autonomous Mobile Robots"

Abstract: Given a set of $n$ autonomous mobile robots that can freely move on a two dimensional plane, they are required to gather in a position of the plane not fixed in advance (\gatheringP). The main research question we address in this paper is: under which conditions this task can be accomplished by the robots? The studied robots are quite simple: they are anonymous, totally asynchronous, they do not have any memory of past computations, they cannot explicitly communicate among each other. We show that this simple task cannot be in general accomplished by the considered system of robots.

Nicola Santoro, Peter Widmayer: " Majority and Unanimity In Synchronous Networks With Ubiquitous Dynamic Faults"

Abstract: In this paper we are interested in synchronous distributed systems subject to transient and ubiquitous failures. This includes systems where failures will occur on {\em any} communication link, systems where {\em every} processor will fail at one time or another, etc., and, following a failure, normal functioning can resume after a finite (although unpredictable) amount of time. Notice that these cases cannot be handled by the traditional {\em component failure} models. The model we use is the {\em transmission failure} model, known also as the {\em dynamic faults} model. Using this model, we study the fundamental problem of {\em agreement} in synchronous systems of arbitrary topology. We establish bounds on the number of dynamic faults that make any non-trivial form of agreement (even strong majority) impossible; in turn, these bounds express connectivity requirements which must be met to achieve any meaningful form of agreement. We also provide, constructively, bounds on the number of dynamic faults in spite of which any non-trivial form of agreement (even unanimity) is possible. These bounds are shown to be tight for a large class of networks, that includes hypercubes, toruses, rings, and complete graphs; incidentally, we close the existing gap between possibility and impossibility of non-trivial agreement in complete graphs in presence of dynamic Byzantine faults. None of these results is derivable in the component failure models; in particular, all our {\em possibility} results hold in situations for which those models indicate {\em impossibility}.

Mordechai Shalom and Shmuel Zaks: "Minimizing the Number of ADMs in SONET Rings with Maximum Throughput"

Abstract: SONET ADMs are dominant cost factors in WDM/SONET rings. Whereas most previous papers on the topic concentrated on the number of wavelengths assigned to a given set of lightpaths, more recent papers argue that the number of ADMs is a more realistic cost measure. The minimization of this cost factor has been investigated in recent years, where single-hop and multi-hop communication models, with arbitrary traffic and uniform traffic loads have been investigated. As a first attempt to understand the trade-off between the number of wavelengths and the number of ADMs, we concentrate on the all-to-all, uniform traffic instance with multi-hop, splittable communication. We look for a solution which makes a full use of the bandwidth and uses the minimum possible number of ADMs under this constraint. We develop an architecture based on successive nested polygons and present a necessary and sufficient condition for a solution in this architecture to be feasible. This architecture leads to a solution using $O(W \log W + N)$ ADMs (compared to $N W$ ADMs for the basic architecture in \cite{GLS99}) which is optimal for $W=O(N/\log N)$. We further improve this result to $O(W \log \overline{W} + N)$ ADMs, where $\overline{W}=o(W)$.

Rui Wang, Francis C. M. Lau : "OptimalGossiping in Square Meshes in All-Port Mode and with Short Packets"

Abstract: N/A

Mirjam Wattenhofer, Roger Wattenhofer, Peter Widmayer: "Geometric Routing without Geometry"

Abstract: In this paper we propose a new routing paradigm, called pseudo-geometric routing. In pseudo-geometric routing, each node u of a network of computing elements is assigned a pseudo coordinate composed of the graph (hop) distances from u to a set of designated nodes (the anchors) in the network. On theses pseudo coordinates we employ greedy geometric routing. Almost as a side effect, pseudo-geometric routing is not restricted to planar unit disk graph networks anymore, but succeeds on general networks.