Publications

2020

• Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, Alexandre Nolin
  Coloring Fast Without Learning Your Neighbors' Colors.
  2020 34rd International Symposium on Distributed Computing (DISC)
  » show abstract« hide abstract
  Abstract

  We give an improved randomized CONGEST algorithm for distance-2 coloring that uses Δ²+1 colors and runs in O(log n) rounds, improving the recent O(log Δ ⋅ log n)-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to O(log Δ) + 2^{O(√{log log n})}.
• Fabian Kuhn, Philipp Schneider
  Computing Shortest Paths and Diameter in the Hybrid Network Model.
  2020 39th ACM Symposium on Principles of Distributed Computing (PODC)
  » show abstract« hide abstract
  Abstract

  The HYBRID model, introduced in [Augustine et al., SODA '20], provides a theoretical foundation for networks that allow multiple communication modes. The model follows the principles of synchronous message passing, whereas nodes are allowed to use two fundamentally different communication modes. First, a local mode where nodes may exchange arbitrary information per round over edges of a local communication graph G (akin to the LOCAL model). Second, a global mode where every node may exchange O(log n) messages of size O(log n) bits per round with arbitrary nodes in the network. The HYBRID model intends to reflect the conditions of many real hybrid networks, where high-bandwidth but inherently local communication is combined with highly flexible global communication with restricted bandwidth. We continue to explore the power and limitations of the HYBRID model by investigating the complexity of computing shortest paths and diameter of the local communication graph G. We show that the all pair shortest paths problem can be solved exactly in [EQUATION] rounds, which improves on the previous Õ(n2/3) round algorithm and closes the gap to the known [EQUATION] lower bound (up to polylog n factors). Furthermore, we give constant approximations for the k-source shortest paths problem (k-SSP) with runtime [EQUATION], provided that k is sufficiently large. As k-SSP has a lower bound of [EQUATION] even for large approximation ratios, our k-SSP algorithms are almost tight for large enough k. In the case of a single source we give an exact Õ(n2/5)-round algorithm, improving on the known [EQUATION]-round algorithm for graphs with large diameter D. For the diameter problem we provide algorithms with complexities Õ(n1/3/ε) and Õ(n0.397/ε) and approximation factors (3/2 + ε) and (1 + ε), respectively. On the negative side, we demonstrate that the classical 2-party set-disjointness framework can be adapted for the HYBRID model to prove a lower bound of [EQUATION] rounds for computing the diameter exactly. For the weighted diameter problem the same holds for computing (2 − ε)-approximations for any ε > 0.
• Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus
  Distance-2 Coloring in the CONGEST Model.
  2020 39th ACM Symposium on Principles of Distributed Computing (PODC)
  » show abstract« hide abstract
  Abstract

  We give efficient randomized and deterministic distributed algorithms for computing a distance-2 vertex coloring of a graph G in the CONGEST model. In particular, if Δ is the maximum degree of G, we show that there is a randomized CONGEST model algorithm to compute a distance-2 coloring of G with Δ2 + 1 colors in O(log Δ · log n) rounds. Further if the number of colors is slightly increased to (1 + ∈)Δ2 for some ∈ > 1/polylog n, we show that it is even possible to compute a distance-2 coloring deterministically in polylog n time in the CONGEST model. Finally, we give a O(Δ2 + log* n)-round deterministic CONGEST algorithm to compute distance-2 coloring with Δ2 + 1 colors.
• Alkida Balliu, Fabian Kuhn, Dennis Olivetti
  Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta.
  2020 39th ACM Symposium on Principles of Distributed Computing (PODC)
  » show abstract« hide abstract
  Abstract

  The problem of coloring the edges of an n-node graph of maximum degree Δ with 2Δ − 1 colors is one of the key symmetry breaking problems in the area of distributed graph algorithms. While there has been a lot of progress towards the understanding of this problem, the dependency of the running time on Δ has been a longstanding open question. Very recently, Kuhn [SODA '20] showed that the problem can be solved in time [EQUATION]. In this paper, we study the edge coloring problem in the distributed LOCAL model. We show that the (degree + 1)-list edge coloring problem, and thus also the (2Δ − 1)-edge coloring problem, can be solved deterministically in time 2O(log2 log Δ)+O(log*n). This is a significant improvement over the result of Kuhn [SODA '20].
• Mohamad Ahmadi, Fabian Kuhn
  Distributed Maximum Matching Verification in CONGEST
  2020 34rd International Symposium on Distributed Computing (DISC)
  » show abstract« hide abstract
  Abstract

  We study the maximum cardinality matching problem in a standard distributed setting, where the nodes V of a given n-node network graph G = (V,E) communicate over the edges E in synchronous rounds. More specifically, we consider the distributed CONGEST model, where in each round, each node of G can send an O(log n)-bit message to each of its neighbors. We show that for every graph G and a matching M of G, there is a randomized CONGEST algorithm to verify M being a maximum matching of G in time O(|M|) and disprove it in time O(D + ), where D is the diameter of G and is the length of a shortest augmenting path. We hope that our algorithm constitutes a significant step towards developing a CONGEST algorithm to compute a maximum matching in time Õ(s^*), where s^* is the size of a maximum matching.
• Philipp Bamberger, Fabian Kuhn, Yannic Maus
  Efficient Deterministic Distributed Coloring with Small Bandwidth.
  2020 39th ACM Symposium on Principles of Distributed Computing (PODC)
  » show abstract« hide abstract
  Abstract

  We show that the (degree + 1)-list coloring problem can be solved deterministically in O(D · log n · log2 Δ) rounds in the CONGEST model, where D is the diameter of the graph, n the number of nodes, and Δ the maximum degree. Using the recent polylogarithmic-time deterministic network decomposition algorithm by Rozhoň and Ghaffari [49], this implies the first efficient (i.e., poly log n-time) deterministic CONGEST algorithm for the (Δ + 1)-coloring and the (degree + 1)-list coloring problem. Previously the best known algorithm required [EQUATION] rounds and was not based on network decompositions. Our techniques also lead to deterministic (degree + 1)-list coloring algorithms for the congested clique and the massively parallel computation (MPC) model. For the congested clique, we obtain an algorithm with time complexity O(log Δ · log log Δ), for the MPC model, we obtain algorithms with round complexity O(log2 Δ) for the linear-memory regime and O(log2 Δ + log n) for the sublinear memory regime.
• Fabian Kuhn
  Faster Deterministic Distributed Coloring Through Recursive List Coloring
  2020 31st ACM-SIAM Symp. on Discrete Algorithms (SODA)
  » show abstract« hide abstract
  Abstract

  We provide novel deterministic distributed vertex coloring algorithms. As our main result, we give a deterministic distributed algorithm to compute a (Δ + 1)-coloring of an n-node graph with maximum degree rounds. For graphs with arboricity a, we obtain a deterministic distributed algorithm to compute a (2 + o(1))a-coloring in time . Further, for graphs with bounded neighborhood independence, we show that a (Δ + 1)-coloring can be computed more efficiently in time . This in particular implies that also a (2Δ – 1)-edge coloring can be computed deterministically in rounds, which improves the best known time bound for small values of Δ. All results even hold for the list coloring variants of the problems. As a consequence, we also obtain an improved deterministic n-round algorithm for Δ-coloring non-complete graphs with maximum degree Δ ≥ 3. Most of our algorithms only require messages of O(log n) bits (including the (Δ + 1)-vertex coloring algorithms). Our main technical contribution is a recursive deterministic distributed list coloring algorithm to solve list coloring problems with lists of size Δ1+o(1). Given some list coloring problem and an orientation of the edges, we show how to recursively divide the global color space into smaller subspaces, assign one of the subspaces to each node of the graph, and compute a new edge orientation such that for each node, the list size to out-degree ratio degrades at most by a constant factor on each recursion level.
• John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider
  Shortest Paths in a Hybrid Network Model
  2020 31st ACM-SIAM Symp. on Discrete Algorithms (SODA)
  » show abstract« hide abstract
  Abstract

  We introduce a communication model for hybrid networks, where nodes have access to two different communication modes: a local mode where (like in traditional networks) communication is only possible between specific pairs of nodes, and a global mode where (like in overlay networks) communication between any pair of nodes is possible. Typically, communication over short-range connections is cheaper and can be done at a much higher rate than communication via the overlay network. Therefore, we are focusing on the LOCAL model for the local connections where nodes can exchange an unbounded amount of information per round. For the global communication we assume the so-called nodecapacitated clique model, where in each round every node can exchange O(log n)-bit messages with O(log n) arbitrary nodes. We explore the impact of hybrid communication on the complexity of distributed algorithms by studying the problem of computing shortest paths in the graph given by the local connections. We present the following results. For the all-pairs shortest paths problem, we show that an exact solution can be computed in time Õ (n2/3), and that approximate solutions can be computed in time but not faster. For the single-source shortest paths problem an exact solution can be computed in time , where SPD denotes the shortest path diameter. Furthermore, a (l + o(1))-approximate solution can be computed in time . Finally, we show that for every constant ε > 0, it is possible to compute an O(1)-approximate solution in time.

• Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler, Thim Strothmann
  Forming tile shapes with simple robots.
  2020 Nat Comput, volume: 19(2), pages: 375 - 390
  » show abstract« hide abstract
  Abstract

  Motivated by the problem of manipulating nanoscale materials, we investigate the problem of reconfiguring a set of tiles into certain shapes by robots with limited computational capabilities. As a first step towards developing a general framework for these problems, we consider the problem of rearranging a connected set of hexagonal tiles by a single deterministic finite automaton. After investigating some limitations of a single-robot system, we show that a feasible approach to build a particular shape is to first rearrange the tiles into an intermediate structure by performing very simple tile movements. We introduce three types of such intermediate structures, each having certain advantages and disadvantages. Each of these structures can be built in asymptotically optimal O(n2) rounds, where n is the number of tiles. As a proof of concept, we give an algorithm for reconfiguring a set of tiles into an equilateral triangle through one of the intermediate structures. Finally, we experimentally show that the algorithm for building the simplest of the three intermediate structures can be modified to be executed by multiple robots in a distributed manner, achieving an almost linear speedup in the case where the number of robots is reasonably small, and explain how the algorithm can be used to construct a triangle distributedly.

• Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, Jara Uitto
  Improved distributed degree splitting and edge coloring.
  2020 Distrib Comput, volume: 33, issue: (3-4), pages: 293 - 310
  » show abstract« hide abstract
  Abstract

  The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy. We present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su (Proc SODA 2017:2505–2523, 2017): our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for (2+o(1))Δ-edge-coloring, improving on that of Ghaffari and Su.

• Sebastian Daum, Fabian Kuhn, Yannic Maus
  Rumor spreading with bounded in-degree.
  2020 Theor Comput Sci, volume: 810, pages: 43 - 57
  » show abstract« hide abstract
  Abstract

  In the gossip-based model of communication for disseminating information in a network, in each time unit, every node u can contact a single random neighbor v but can possibly be contacted by many nodes. In the present paper, we consider a restricted model where at each node only one incoming call can be answered in one time unit. We study the implied weaker version of the well-studied pull protocol, which we call restricted pull. We prove an exponential separation of the rumor spreading time between two variants of the protocol (the answered call among a set of calls is chosen adversarially or uniformly at random). Further, we show that if the answered call is chosen randomly, the slowdown of restricted pull versus the classic pull protocol can w.h.p. be upper bounded by , where with Δ and δ being the largest and smallest degree of the network and being the degree of u.

• Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, Anisur Rahaman Molla
  The Cost of Global Broadcast in Dynamic Radio Networks
  2020 Theor Comput Sci, volume: 806, pages: 363 - 387
  » show abstract« hide abstract
  Abstract

  We study the time complexity of single and multi token broadcast in adversarial dynamic radio networks. Initially, k tokens (which are k pieces of information) are distributed among the n nodes of a network and all the tokens need to be disseminated to all the nodes in the network. We first consider the single-token broadcast problem (i.e., the case k=1). By presenting upper and lower bounds, we show that the time complexity of single-token broadcast depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. Then, we give two generic algorithms which allow to transform generalized forms of single-token broadcast algorithms into multi-token broadcast (k-token broadcast) algorithms. Based on these generic algorithms, we obtain k-token broadcast algorithms for a number of different dynamic network settings. For one of the modeling assumptions, our algorithm is complemented by a lower bound which shows that the upper bound is close to optimal.

2019

• Abdolhamid Ghodselahi, Fabian Kuhn, Volker Turau
  Competitive Concurrent Distributed Scheduling
  2019 30th Int. Symp. on Algorithms and Computation (ISAAC)
• Mohsen Ghaffari, Fabian Kuhn, Jara Uitto
  Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds
  2019 60th IEEE Symp. on Foundations of Computer Science (FOCS)
• Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, Rotem Oshman
  Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles
  2019 33rd International Symposium on Distributed Computing (DISC)
• Janosch Deurer, Fabian Kuhn, Yannic Maus
  Deterministic Distributed Dominating Set Approximation in the CONGEST Model
  2019 38th ACM Symp. on Principles of Distributed Computing (PODC)
• Philipp Bamberger, Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Jara Uitto
  On the Complexity of Distributed Splitting Problems
  2019 38th ACM Symp. on Principles of Distributed Computing (PODC)
• Mohsen Ghaffari, Fabian Kuhn
  On the Use of Randomness in Local Distributed Graph Algorithms
  2019 38th ACM Symp. on Principles of Distributed Computing (PODC)
• Bernhard Haeupler, Fabian Kuhn, Anders Martinsson, Kalina Petrova, Pascal Pfister
  Optimal Strategies for Patrolling Fences
  2019 46th Int. Coll. on Automata, Languages, and Programming (ICALP)
• Mohamad Ahmadi, Fabian Kuhn, Shay Kutten, Anisur Rahaman Molla, Gopal Pandurangan
  The Communication Cost of Information Spreading in Dynamic Networks
  2019 39th IEEE Int. Conf. on Distributed Computing Systems (ICDCS), Dallas, USA
  » show abstract« hide abstract
  Abstract

  This paper investigates the message complexity of distributed information spreading in adversarial dynamic net- works. While distributed computations in dynamic networks have been studied intensively over the last years, almost all of the existing work solely focuses on the time complexity of distributed algorithms. In information spreading, the goal is to spread k tokens of information to every node on an n-node network. We consider the amortized (average) message complexity of spreading a token, assuming that the number of tokens is large. In a static network, this basic problem can be solved using (asymptotically optimal) O(n) amortized messages per token. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. We present two sets of results depending on how nodes send messages to their neighbors: 1. Local broadcast: We show a tight lower bound of \tilde{Ω}(n^2) on the number of amortized local broadcasts, which is matched by the naive flooding algorithm. The lower bound holds for randomized algorithms against a strongly adaptive adversary. 2. Unicast: We study the message complexity as a function of the number of dynamic changes in the network. To facilitate this, we introduce adversary-competitive message complexity as a natural complexity measure for analyzing dynamic networks: The adversary pays a unit cost for every topological change and the message cost of an algorithm is determined as the actual number of messages sent minus the total cost of the adversary. Under this model, we give a deterministic algorithm that obtains an optimal amortized message complexity of O(n) if the number of tokens k is sufficiently large. We also present a randomized algorithm that achieves subquadratic amortized message complexity for much smaller k under an oblivious adversary.
• John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian Kuhn, Jason Li, Christian Scheideler
  Distributed Computation in Node-Capacitated Networks
  2019 31st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA)
  » show abstract« hide abstract
  Abstract

  In this paper, we study distributed graph algorithms in networks in which the nodes have a limited communication capacity. Many distributed systems are built on top of an underlying network- ing infrastructure, for example by using a virtual communication topology known as an overlay network. Although this underlying network might allow each node to directly communicate with a large number other nodes, the amount of communication that a node can perform in a fixed amount of time is typically much more limited. We introduce the node-capacitated clique model as an abstract communication model, which allows us to study the effect of nodes having limited communication capacity on the complexity of distributed graph computations. In this model, the n nodes of a network are connected as a clique and communicate in synchronous rounds. In each round, every node can exchange messages of O (log n) bits with at most O (log n) other nodes. When solving a graph problem, the input graph G is defined on the same set of n nodes, where each node initially knows the identifiers of all its neighbors in G. To initiate research on the node-capacitated clique model, we present distributed algorithms for the Minimum Spanning Tree (MST), BFS Tree, Maximal Independent Set, Maximal Matching, and Vertex Coloring problems. We show that even with only O(logn) concurrent interactions per node, the MST problem can still be solved in polylogarithmic time. In all other cases, the runtime of our algorithms depends linearly on the arboricity of G, which is a constant for many important graph families such as planar graphs.
• Philipp Bamberger, Fabian Kuhn, Yannic Maus
  Local Distributed Algorithms in Highly Dynamic Networks
  2019 33rd IEEE Int. Parallel and Distributed Processing Symposium (IPDPS)
  » show abstract« hide abstract
  Abstract

  We define a generalization of local distributed graph problems to (synchronous round-based) dynamic networks and present a framework for developing algorithms for these problems. The algorithms should satisfy non-trivial guarantees in every round. The guarantees should be stronger the more stable the graph has been during the last few rounds and coincide with the definition of the static graph problem if no topological change appeared recently. Moreover, if only a constant neighborhood around some part of the graph is stable during an interval, the algorithms should quickly converge to a solution for this part of the graph that remains unchanged throughout the interval. We demonstrate our generic framework with two classic distributed graph problems, namely (degree+1)-vertex coloring and maximal independent set (MIS). To illustrate the given guarantees consider the vertex coloring problem: Any conflict between two nodes caused by a newly inserted edge is resolved within T = O(log n) rounds. During this conflict resolving both nodes always output colors that are not in conflict with their respective ‘old‘ neighbors. The largest color that a node is allowed to output is determined by the number of distinct neighbors that it has seen in the last T rounds.
• Mohsen Ghaffari, Jara Uitto
  Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
  2019 30th ACM-SIAM Symposium on Discrete Algorithms (SODA)

• Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, Calvin Newport
  Contention Resolution on a Fading Channel
  2019 Distrib Comput, volume: 32, issue: 6, pages: 517 - 533
  » show abstract« hide abstract
  Abstract

  In this paper, we study upper and lower bounds for contention resolution on a single hop fading channel; i.e., a channel where receive behavior is determined by a signal to interference and noise ratio equation. The best known previous solution solves the problem in this setting in O(log^2 n/ log log n) rounds, with high probability in the system size n. We describe and analyze an algorithm that solves the problem in O(log n+log R)rounds, where R is the ratio between the longest and shortest link, and is a value upper bounded by a polynomial in n for most feasible deployments. We complement this result with an Ω(log n) lower bound that proves the bound tight for reasonable R. We note that in the classical radio network model (which does not include signal fading), high probability contention resolution requires Ω(log^2 n) rounds. Our algorithm, therefore, affirms the conjecture that the spectrum reuse enabled by fading should allow distributed algorithms to achieve a significant improvement on this log^2 n speed limit. In addition, we argue that the new techniques required to prove our upper and lower bounds are of general use for analyzing other distributed algorithms in this increasingly well-studied fading channel setting.

2018

• Mohsen Ghaffari, Fabian Kuhn
  Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
  2018 32nd International Symposium on Distributed Computing (DISC)
  » show abstract« hide abstract
  Abstract

  This paper presents improved deterministic distributed algorithms, with O(log n)-bit messages, for some basic graph problems. The common ingredient in our results is a deterministic distributed algorithm for computing a certain hitting set, which can replace the random part of a number of standard randomized distributed algorithms. This deterministic hitting set algorithm itself is derived using a simple method of conditional expectations. As one main end-result of this derandomized hitting set, we get a deterministic distributed algorithm with round complexity 2^O(sqrt{log n * log log n}) for computing a (2k-1)-spanner of size O~(n^{1+1/k}). This improves considerably on a recent algorithm of Grossman and Parter [DISC'17] which needs O(n^{1/2-1/k} * 2^k) rounds. We also get a 2^O(sqrt{log n * log log n})-round deterministic distributed algorithm for computing an O(log^2 n)-approximation of minimum dominating set; all prior algorithms for this problem were either randomized or required large messages.
• Mohamad Ahmadi, Fabian Kuhn, Rotem Oshman
  Distributed Approximate Maximum Matching in the CONGEST Model
  2018 32th Int. Symp. on Distributed Computing (DISC), New Orleans, USA
  » show abstract« hide abstract
  Abstract

  We study distributed algorithms for the maximum matching problem in the CONGEST model, where each message must be bounded in size. We give new deterministic upper bounds, and a new lower bound on the problem. We begin by giving a distributed algorithm that computes an exact maximum (unweighted) matching in bipartite graphs, in O(n log n) rounds. Next, we give a distributed algorithm that approximates the fractional weighted maximum matching problem in general graphs. In a graph with maximum degree at most Delta, the algorithm computes a (1-eps)-approximation for the problem in time O(log(Delta W)/eps^2), where W is a bound on the ratio between the largest and the smallest edge weight. Next, we show a slightly improved and generalized version of the deterministic rounding algorithm of Fischer [DISC '17]. Given a fractional weighted maximum matching solution of value f for a given graph G, we show that in time O((log^2(Delta)+log^*n)/eps), the fractional solution can be turned into an integer solution of value at least (1-eps)f for bipartite graphs and (1-\eps).f.(g-1)/g for general graphs, where g is the length of the shortest odd cycle of G. Together with the above fractional maximum matching algorithm, this implies a deterministic algorithm that computes a (1-eps).f.(g-1)/g-approximation for the weighted maximum matching problem in time O(log(Delta W)/eps^2 + (log^2(Delta)+log^* n)/eps). On the lower-bound front, we show that even for unweighted fractional maximum matching in bipartite graphs, computing an (1 - O(1/sqrt{n}))-approximate solution requires at least Omega(D+sqrt{n}) rounds in CONGEST (ignoring log factors). This lower bound requires the introduction of a new 2-party communication problem, for which we prove a tight lower bound.
• Mohsen Ghaffari, Fabian Kuhn
  Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping
  2018 32nd International Symposium on Distributed Computing (DISC)
  » show abstract« hide abstract
  Abstract

  We present a distributed minimum spanning tree algorithm with near-optimal round complexity of O~(D+sqrt{n}) and message complexity O~(min{n^{3/2}, m}). This is the first algorithm with sublinear message complexity and near-optimal round complexity and it improves over the recent algorithms of Elkin [PODC'17] and Pandurangan et al. [STOC'17], which have the same round complexity but message complexity O~(m). Our method also gives the first broadcast algorithm with o(n) time complexity - when that is possible at all, i.e., when D=o(n) - and o(m) messages. Moreover, our method leads to an O~(sqrt{nD})-round GOSSIP algorithm with bounded-size messages. This is the first such algorithm with a sublinear round complexity.
• Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela, Jara Uitto
  Distributed Recoloring
  2018 32nd International Symposium on Distributed Computing (DISC)
  » show abstract« hide abstract
  Abstract

  Given two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the graph is properly colored after each step? We introduce the notion of distributed recoloring: The input graph represents a network of computers that needs to be recolored. Initially, each node is aware of its own input color and target color. The nodes can exchange messages with each other, and eventually each node has to stop and output its own recoloring schedule, indicating when and how the node changes its color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously. We are interested in the following questions: How many communication rounds are needed (in the deterministic LOCAL model of distributed computing) to find a recoloring schedule? What is the length of the recoloring schedule? And how does the picture change if we can use extra colors to make recoloring easier? The main contributions of this work are related to distributed recoloring with one extra color in the following graph classes: trees, 3-regular graphs, and toroidal grids.
• Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler, Thim Strothmann
  Forming Tile Shapes with Simple Robots
  2018 24th International Conference on DNA Computing and Molecular Programming (DNA 24) Springer
  » show abstract« hide abstract
  Abstract

  Motivated by the problem of manipulating nanoscale materials, we investigate the problem of reconfiguring a set of tiles into certain shapes by robots with limited computational capabilities. As a first step towards developing a general framework for these problems, we consider the problem of rearranging a connected set of hexagonal tiles by a single deterministic finite automaton. After investigating some limitations of a single-robot system, we show that a feasible approach to build a particular shape is to first rearrange the tiles into an intermediate structure by performing very simple tile movements. We introduce three types of such intermediate structures, each having certain advantages and disadvantages. Each of these structures can be built in asymptotically optimal O(n^2) rounds, where n is the number of tiles. As a proof of concept, we give an algorithm for reconfiguring a set of tiles into an equilateral triangle through one of the intermediate structures. Finally, we experimentally show that the algorithm for building the simplest of the three intermediate structures can be modified to be executed by multiple robots in a distributed manner, achieving an almost linear speedup in the case where the number of robots is reasonably small.
• Mohsen Ghaffari, David G. Harris, Fabian Kuhn
  On Derandomizing Local Distributed Algorithms
  2018 59th IEEE Symposium on Foundations of Computer Science (FOCS)
  » show abstract« hide abstract
  Abstract

  The gap between the known randomized and deterministic local distributed algorithms underlies arguably the most fundamental and central open question in distributed graph algorithms. In this paper, we combine the method of conditional expectation with network decompositions to obtain a generic and clean recipe for derandomizing LOCAL algorithms. This leads to significant improvements on a number of problems, in cases resolving known open problems. Two main results are: - An improved deterministic distributed algorithm for hypergraph maximal matching, improving on Fischer, Ghaffari, and Kuhn [FOCS '17]. This yields improved algorithms for edge-coloring, maximum matching approximation, and low out-degree edge orientation. The last result gives the first positive resolution in the Open Problem 11.10 in the book of Barenboim and Elkin. - Improved randomized and deterministic distributed algorithms for the Lovász Local Lemma, which get closer to a conjecture of Chang and Pettie [FOCS '17].
• Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler
  Shape Recognition by a Finite Automaton Robot
  2018 43rd Symposium on Mathematical Foundations of Computer Science (MFCS)
  » show abstract« hide abstract
  Abstract

  Motivated by the problem of shape recognition by nanoscale computing agents, we investigate the problem of detecting the geometric shape of a structure composed of hexagonal tiles by a finite-state automaton robot. In particular, in this paper we consider the question of recognizing whether the tiles are assembled into a parallelogram whose longer side has length l = f(h), for a given function f(*), where h is the length of the shorter side. To determine the computational power of the finite-state automaton robot, we identify functions that can or cannot be decided when the robot is given a certain number of pebbles. We show that the robot can decide whether l = ah+b for constant integers a and b without any pebbles, but cannot detect whether l = f(h) for any function f(x) = omega(x). For a robot with a single pebble, we present an algorithm to decide whether l = p(h) for a given polynomial p(*) of constant degree. We contrast this result by showing that, for any constant k, any function f(x) = omega(x^(6k + 2)) cannot be decided by a robot with k states and a single pebble. We further present exponential functions that can be decided using two pebbles. Finally, we present a family of functions f_n(*) such that the robot needs more than n pebbles to decide whether l = f_n(h).
• Sebastian Brandt, Seth Pettie, Jara Uitto
  Fine-grained Lower Bounds on Cops and Robbers
  2018 26th Annual European Symposium on Algorithms (ESA)
  » show abstract« hide abstract
  Abstract

  Cops and Robbers is a classic pursuit-evasion game played between a group of g cops and one robber on an undirected N-vertex graph G. We prove that the complexity of deciding the winner in the game under optimal play requires Omega (N^{g-o(1)}) time on instances with O(N log^2 N) edges, conditioned on the Strong Exponential Time Hypothesis. Moreover, the problem of calculating the minimum number of cops needed to win the game is 2^{Omega (sqrt{N})}, conditioned on the weaker Exponential Time Hypothesis. Our conditional lower bound comes very close to a conditional upper bound: if Meyniel's conjecture holds then the cop number can be decided in 2^{O(sqrt{N}log N)} time. In recent years, the Strong Exponential Time Hypothesis has been used to obtain many lower bounds on classic combinatorial problems, such as graph diameter, LCS, EDIT-DISTANCE, and REGEXP matching. To our knowledge, these are the first conditional (S)ETH-hard lower bounds on a strategic game.
• Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Juho Hirvonen
  Improved Distributed Delta-Coloring
  2018 ACM Symposium on Principles of Distributed Computing (PODC)
  » show abstract« hide abstract
  Abstract

  We present a randomized distributed algorithm that computes a $\Delta$-coloring in any non-complete graph with maximum degree $\Delta \geq 4$ in $O(\log \Delta) + 2^{O(\sqrt{\log\log n})}$ rounds, as well as a randomized algorithm that computes a $\Delta$-coloring in $O((\log \log n)^2)$ rounds when $\Delta \in [3, O(1)]$. Both these algorithms improve on an $O(\log^3 n/\log \Delta)$-round algorithm of Panconesi and Srinivasan~[STOC'1993], which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an $\Omega(\log\log n)$ round lower bound of Brandt et al.~[STOC'16].
• Orr Fischer, Tzlil Gonen, Fabian Kuhn, Rotem Oshman
  Possibilities and Impossibilities for Distributed Subgraph Detection
  2018 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA)
  » show abstract« hide abstract
  Abstract

  In the distributed subgraph detection problem, we are given a fixed subgraph H, and the network must decide whether the network graph contains a copy of H or not. Subgraph detection can be solved in a constant number of rounds if message size is unbounded, but in the CONGEST model, where each message has bounded size, it can have high round complexity. Distributed subgraph detection has received significant attention recently, with new upper and lower bounds, but several fundamental questions remain open. In this paper we prove new possibility and impossibility results for subgraph detection in the CONGEST model. We show for the first time that some subgraphs require superlinear --- in fact, nearly quadratic --- running time, even in small-diameter networks. We also study cycle-detection, and show that any even cycle can be detected in sublinear time (in contrast to odd cycles, which require linear time). For the special case of triangle-detection, we show that deterministic algorithms require $Omega(log n)$ total communication even in graphs of degree 2, and that one-round randomized algorithms must send $Omega(Δ)$ bits in graphs of degree Δ, improving on the recent results of [Abboud et. al.]. Finally, we extend a recent lower bound of [Izumi, Le Gall] on listing all triangles to cliques of any size.
• Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Jara Uitto
  Deterministic Distributed Edge-Coloring with Fewer Colors
  2018 50th ACM Symposium on Theory of Computing (STOC)
  » show abstract« hide abstract
  Abstract

  We present a deterministic distributed algorithm, in the $\LOCAL$ model, that computes a $(1+o(1))\Delta$-edge-coloring in polylogarithmic-time, so long as the maximum degree $\Delta=\tilde{\Omega}(\log n)$. For smaller $\Delta$, we give a polylogarithmic-time $3\Delta/2$-edge-coloring. These are the first deterministic algorithms to go below the natural barrier of $2\Delta-1$ colors, and they improve significantly on the recent polylogarithmic-time $(2\Delta-1)(1+o(1))$-edge-coloring of Ghaffari and Su [SODA'17] and the $(2\Delta-1)$-edge-coloring of Fischer, Ghaffari, and Kuhn [FOCS'17], positively answering the main open question of the latter. The key technical ingredient of our algorithm is a simple and novel gradual packing of judiciously chosen near-maximum matchings, each of which becomes one of the color classes.
• Fabian Kuhn, Yannic Maus, Simon Weidner
  Deterministic Distributed Ruling Sets of Line Graphs
  2018 Int. Coll. on Structural Information and Communication Complexity (SIROCCO)
  » show abstract« hide abstract
  Abstract

  An $(\alpha,\beta)$-ruling set of a graph $G=(V,E)$ is a set $R\subseteq V$ such that for any node $v\in V$ there is a node $u\in R$ in distance at most $\beta$ from $v$ and such that any two nodes in $R$ are at distance at least $\alpha$ from each other. The concept of ruling sets can naturally be extended to edges, i.e., a subset $F\subseteq E$ is an \emph{$(\alpha,\beta)$-ruling edge set} of a graph $G=(V,E)$ if the corresponding nodes form an $(\alpha,\beta)$-ruling set in the line graph of $G$. This paper presents a simple deterministic, distributed algorithm, in the CONGEST ~ model, for computing $(2,2)$-ruling edge sets in $O(\logstar n)$ rounds. Furthermore, we extend the algorithm to compute ruling sets of graphs with bounded \emph{diversity}. Roughly speaking, the diversity of a graph is the maximum number of maximal cliques a vertex belongs to. We devise $(2,O(\diversity))$-ruling sets on graphs with diversity $\diversity$ in $O(\diversity+\logstar n)$ rounds. This also implies a fast, deterministic $(2,O(\rank))$-ruling edge set algorithm for hypergraphs with rank at most \rank. Furthermore, we provide a ruling set algorithm for general graphs that for any $B\geq 2$ computes an $\big(\alpha, \alpha \ceil{\log_B n}\big)$-ruling set in $O(\alpha \cdot B \cdot \log_B n)$ rounds in the CONGEST model. The algorithm can be modified to compute a $\big(2, \beta \big)$-ruling set in $O(\beta \degree^{2/\beta} + \logstar n)$ rounds in the CONGEST model, which matches the currently best known such algorithm in the more general LOCAL model.
• Paweł Gawrychowski, Fabian Kuhn, Jakub Łopuszański, Konstantinos Panagiotou, Pascal Su
  Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees
  2018 29th ACM-SIAM Symposium on Discrete Algorithms (SODA)
  » show abstract« hide abstract
  Abstract

  Preprocessing a tree for finding the nearest common ancestor of two nodes is a basic tool with multiple applications. Quite a few linear-space constant-time solutions are known and the problem seems to be well-understood. This is however not so clear if we want to design a labeling scheme. In this model, the structure should be distributed: every node receives a distinct binary string, called its label, so that given the labels of two nodes (and no further information about the topology of the tree) we can compute the label of their nearest common ancestor. The goal is to make the labels as short as possible. Alstrup, Gavoille, Kaplan, and Rauhe [Theor. Comput. Syst. 37(3):441-456 2004] showed that O(log n)-bit labels are enough, with a somewhat large constant. More recently, Alstrup, Halvorsen, and Larsen [SODA 2014] refined this to only 2.772 log n, and provided a lower bound of 1.008 log n. We connect the question of designing a labeling scheme for nearest common ancestors to the existence of a tree, called a minor-universal tree, that contains every tree on n nodes as a topological minor. Even though it is not clear if a labeling scheme must be based on such a notion, we argue that all already existing schemes can be reformulated as such. Further, we show that this notion allows us to easily obtain clean and good bounds on the length of the labels. As the main upper bound, we show that 2.318 log n- bit labels are enough. Surprisingly, the notion of a minor- universal tree for binary trees on n nodes has been already used in a different context by Hrubes et al. [CCC 2010], and Young, Chu, and Wong [J. ACM 46(3):416-435, 1999] introduced a very closely related (but not equivalent) notion of a universal tree. On the lower bound side, we show that any minor-universal tree for trees on n nodes must contain at least Omega(n^2.174) nodes. This highlights a natural limitation for all approaches based on defining a minor- universal tree. We complement the existential results with a generic transformation that allows us, for any labeling scheme for nearest common ancestors based on a minor- universal tree, to decrease the query time to constant, while increasing the length of the labels only by lower order terms.
• Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, Jara Uitto
  The Complexity of Distributed Edge Coloring with Small Palettes
  2018 29th ACM-SIAM Symposium on Discrete Algorithms (SODA)

2017

• Fabian Kuhn, Philipp Schneider
  Broadcasting in an Unreliable SINR Model
  2017 21st Conference on Principles of Distributed Systems (OPODIS) , pages: 3:1 - 3:21
• Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, Jara Uitto
  Improved Distributed Degree Splitting and Edge Coloring
  2017 International Symposium on DIStributed Computing (DISC)
  » show abstract« hide abstract
  Abstract

  The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy. We present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su [SODA'17]: our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for $(2+o(1))\Delta$-edge-coloring, improving on that of Ghaffari and Su.
• Magnús M. Halldórsson, Fabian Kuhn, Nancy Lynch, Calvin Newport
  An Efficient Communication Abstraction for Dense Wireless Networks
  2017 31st Symposium on Distributed Computing (DISC) , pages: 25:1 - 25:16
• Abdolhamid Ghodselahi, Fabian Kuhn
  Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks
  2017 31st Symposium on Distributed Computing (DISC)
  » show abstract« hide abstract
  Abstract

  The Arrow protocol is a simple and elegant protocol to coordinate exclusive access to a shared object in a network. The protocol solves the underlying distributed queueing problem by using path reversal on a pre-computed spanning tree (or any other tree topology simulated on top of the given network). It is known that the Arrow protocol solves the problem with a competitive ratio of O(log D) on trees of diameter D. This implies a distributed queueing algorithm with competitive ratio O(s · log D) for general networks with a spanning tree of diameter D and stretch s. In this work we show that when running the Arrow protocol on top of the well-known probabilistic tree embedding of Fakcharoenphol, Rao, and Talwar [STOC03], we obtain a randomized distributed queueing algorithm with a competitive ratio of O(log n) even on general network topologies. The result holds even if the queueing requests occur in an arbitrarily dynamic and concurrent fashion and even if communication is asynchronous. From a technical point of view, the main of the paper shows that the competitive ratio of the Arrow protocol is constant on a special family of tree topologies, known as hierarchically well separated trees.
• Manuela Fischer, Mohsen Ghaffari, Fabian Kuhn
  Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
  2017 58th IEEE Symposium on Foundations of Computer Science (FOCS) , pages: 180 - 191
• Seth Gilbert, Fabian Kuhn, Chaodong Zheng
  Communication Primitives in Cognitive Radio Networks
  2017 36th ACM Symposium on Principles of Distributed Computing (PODC) , pages: 23 - 32
• Mohsen Ghaffari, Fabian Kuhn, Hsin-Hao Su
  Distributed MST and Routing in Almost Mixing Time
  2017 36th ACM Symposium on Principles of Distributed Computing (PODC) , pages: 131 - 140
• Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman Molla
  Greedy Routing and the Algorithmic Small-World Phenomenon
  2017 36th ACM Symposium on Principles of Distributed Computing (PODC)
  » show abstract« hide abstract
  Abstract

  The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s~\cite{milgram1967small}, was theoretically explained by Kleinberg in 2000~\cite{KleinbergModel}. However, from today's perspective his model has several severe shortcomings %drawbacks that limit the applicability to real-world networks. In order to give a more convincing explanation of the algorithmic small-world phenomenon, we study decentralized greedy routing in a more flexible random graph model (geometric inhomogeneous random graphs) which overcomes all previous shortcomings. %has not only theoretically good properties, Apart from exhibiting good properties in theory, it has also been extensively experimentally validated that this model reasonably captures real-world networks. In this model, the greedy routing protocol is purely distributed as each vertex only needs to know information about its direct neighbors. We prove that it succeeds with constant probability, and in case of success almost surely finds an almost shortest path of length $\Theta(\log\log n)$, where our bound is tight including the leading constant. Moreover, we study natural local patching methods which augment greedy routing by backtracking and which do not require any global knowledge. We show that such methods can ensure success probability 1 in an asymptotically tight number of steps. These results also address the question of Krioukov et al.~\cite{krioukov2007compact} whether there are efficient local routing protocols for the internet graph. There were promising experimental studies, but the question remained unsolved theoretically. Our results give for the first time a rigorous and analytical affirmative answer.
• Sebastian Brandt, Yuval Emek, Jara Uitto, Roger Wattenhofer
  A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
  2017 44th International Colloquium on Automata, Languages, and Programming (ICALP)
  » show abstract« hide abstract
  Abstract

  For the game of Cops and Robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time, and that there exist graphs in which this capture time is tight. When k >= 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O(n^{k + 1}), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. In this paper, the question of Bonato and Nowakowski is answered on the negative, proving that the O(n^{k + 1}) bound is asymptotically tight for any constant k >= 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.
• Mohsen Ghaffari, Fabian Kuhn, Yannic Maus
  On the Complexity of Local Distributed Graph Problems
  2017 ACM Symposium on Theory of Computing (STOC)
  » show abstract« hide abstract
  Abstract

  This paper is centered on the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS '87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and (Δ+1)-vertex coloring), the randomized complexity is at most polylogarithmic in the size n of the network, while the best deterministic complexity is typically 2^(O(log(sqrt(n))). Understanding and narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms. We investigate the problem by introducing a complexity-theoretic framework that allows us to shed some light on the role of randomness in the LOCAL model. We define the SLOCAL model as a sequential version of the LOCAL model. Our framework allows us to prove completeness results with respect to the class of problems which can be solved efficiently in the SLOCAL model, implying that if any of the complete problems can be solved deterministically in log^(O(1))n rounds in the LOCAL model, we can deterministically solve all efficient SLOCAL-problems (including MIS and (Δ+1)-coloring) in log^(O(1))n rounds in the LOCAL model. We show that a rather rudimentary looking graph coloring problem is complete in the above sense: Color the nodes of a graph with colors red and blue such that each node of sufficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized solution. The result can be viewed as showing that the only obstacle to getting efficient determinstic algorithms in the LOCAL model is an efficient algorithm to approximately round fractional values into integer values.

• Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn
  Tight Bounds on Vertex Connectivity Under Sampling
  2017 Acm T Algorithms, volume: 13, issue: 2, pages: 19:1 - 19:26
  » show abstract« hide abstract
  Abstract

  A fundamental result by Karger [10] states that for any λ-edge-connected graph with n nodes, independently sampling each edge with probability p = Ω(log (n)/λ) results in a graph that has edge connectivity Ω(λp), with high probability. This article proves the analogous result for vertex connectivity, when either vertices or edges are sampled. We show that for any k-vertex-connected graph G with n nodes, if each node is independently sampled with probability p=Ω(&sqrt;log(n)/k), then the subgraph induced by the sampled nodes has vertex connectivity Ω(kp2), with high probability. If edges are sampled with probability p = Ω(log (n)/k), then the sampled subgraph has vertex connectivity Ω(kp), with high probability. Both bounds are existentially optimal.

2016

• Mohamad Ahmadi, Fabian Kuhn
  Multi-Message Broadcast in Dynamic Radio Networks
  2016 12th Int. Symp. on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS), Aarhus, Denmark
  » show abstract« hide abstract
  Abstract

  We continue the recent line of research studying information dissemination problems in adversarial dynamic radio networks. We give two generic algorithms which allow to transform generalized version of single-message broadcast algorithms into multi-message broadcast algorithms. Based on these generic algorithms, we obtain multi-message broadcast algorithms for dynamic radio networks for a number of different dynamic network settings. For one of the modeling assumptions, our algorithms are complemented by a lower bound which shows that the upper bound is close to optimal.
• Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, Calvin Newport
  Contention Resolution on a Fading Channel
  2016 2016 ACM Symposium on Principles of Distributed Computing (PODC)
  » show abstract« hide abstract
  Abstract

  In this paper, we study upper and lower bounds for contention resolution on a single hop fading channel; i.e., a channel where receive behavior is determined by a signal to interference and noise ratio (SINR) equation. The best known previous solution solves the problem in this setting in O(log2 n log log n) rounds, with high probability in the system size n. We describe and analyze an algorithm that solves the problem in O(log n + log R) rounds, where R is the ratio between the longest and shortest link, and is a value upper bounded by a polynomial in n for most feasible deployments. We complement this result with an Ω(log n) lower bound that proves the bound tight for reasonable R. We note that in the classical radio network model (which does not include signal fading), high probability contention resolution requires Ω(log 2 n) rounds. Our algorithm, therefore, affirms the conjecture that the spectrum reuse enabled by fading should allow distributed algorithms to achieve a significant improvement on this log2 n speed limit. In addition, we argue that the new techniques required to prove our upper and lower bounds are of general use for analyzing other distributed algorithms in this increasingly well-studied fading channel setting.
• Dan Hefetz, Fabian Kuhn, Yannic Maus, Angelika Steger
  Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model
  2016 30th International Symposium on DIStributed Computing (DISC), Paris, September 26-30, 2016
  » show abstract« hide abstract
  Abstract

  We show an Omega(\Delta^{\frac{1}{3}-\frac{\eta}{3}}) lower bound on the runtime of any deterministic distributed O(\Delta^{1+\eta})-graph coloring algorithm in a weak variant of the LOCAL model. In particular, given a network graph G=(V,E), in the weak LOCAL model nodes communicate in synchronous rounds and they can use unbounded local computation. The nodes have no identifiers, but instead, the computation starts with an initial valid vertex coloring. A node can broadcast a single message of unbounded size to its neighbors and receives the set of messages sent to it by its neighbors. The proof uses neighborhood graphs and improves their understanding in general such that it might help towards finding a lower (runtime) bound for distributed graph coloring in the standard LOCAL model.
• Fabian Kuhn, Sebastian Daum, Yannic Maus
  Rumor Spreading with Bounded In-Degree
  2016 23rd Int. Coll. on Structural Information and Communication Complexity (SIROCCO), Helsinki, Finland
  » show abstract« hide abstract
  Abstract

  In the classic gossip-based model of communication for disseminating information in a network, in each time unit, every node u is allowed to contact a single random neighbor v. If u knows the data (rumor) to be disseminated, it disperses it to v (known as PUSH) and if it does not, it requests it from v (known as PULL). While in the classic gossip model, each node is only allowed to contact a single neighbor in each time unit, each node can possibly be contacted by many neighboring nodes. In the present paper, we consider a restricted model where at each node only one incoming request can be served. As long as only a single piece of information needs to be disseminated, this does not make a difference for push requests. It however has a significant effect on pull requests. In the paper, we therefore concentrate on this weaker pull version, which we call 'restricted pull'. We distinguish two versions of the restricted pull protocol depending on whether the request to be served among a set of pull requests at a given node is chosen adversarially or uniformly at random. As a first result, we prove an exponential separation between the two variants. We show that there are instances where if an adversary picks the request to be served, the restricted pull protocol requires a polynomial number of rounds whereas if the winning request is chosen uniformly at random, the restricted pull protocol only requires a polylogarithmic number of rounds to inform the whole network. Further, as the main technical contribution, we show that if the request to be served is chosen randomly, the slowdown of using restricted pull versus using the classic pull protocol can w.h.p. be upper bounded by O(Δ/δlogn), where Δ and δ are the largest and smallest degree of the network.

2015

• Fabian Kuhn, Anisur Rahaman Molla
  Distributed Sparse Cut Approximation
  2015 19th Int. Conf. on Principles of Distributed Systems (OPODIS), Rennes, France
• Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, Anisur Rahaman Molla
  The Cost of Global Broadcast in Dynamic Radio Networks
  2015 19th Int. Conf. on Principles of Distributed Systems (OPODIS), Rennes, France
  » show abstract« hide abstract
  Abstract

  We study the single-message broadcast problem in dynamic radio networks. We show that the time complexity of the problem depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. More formally, we model communication using the standard graph-based radio network model. To model the dynamic network, we use a variant of the synchronous dynamic graph model introduced in [Kuhn et al., STOC 2010]. For integer parameters $T\geq 1$ and $k\geq 1$, we call a dynamic graph $T$-interval $k$-connected if for every interval of $T$ consecutive rounds, there exists a $k$-vertex-connected stable subgraph. Further, for an integer parameter $\tau\geq 0$, we say that the adversary providing the dynamic network is $\tau$-oblivious if for constructing the graph of some round $t$, the adversary has access to all the randomness (and states) of the algorithm up to round $t-\tau$. As our main result, we show that for any $T\geq 1$, any $k\geq 1$, and any $\tau\geq 1$, for a $\tau$-oblivious adversary, there is a distributed algorithm to broadcast a single message in time $O\big(\big(1+\frac{n}{k\cdot \min \set{\tau,T}} \big ) \cdot n \log^3 n \big)$. We further show that even for large interval $k$-connectivity, efficient broadcast is not possible for the usual adaptive adversaries. For a $1$-oblivious adversary, we show that even for any $T\leq (n/k)^{1-\eps}$ (for any constant $\eps > 0$) and for any $k\geq 1$, global broadcast in $T$-interval $k$-connected networks requires at least $\Omega(n^2/k^2\log n)$ time. Further, for a $0$-oblivious adversary, broadcast cannot be solved in $T$-interval $k$-connected networks as long as $T<n-k$.
• Abdolhamid Ghodselahi, Fabian Kuhn
  Serving Online Requests with Mobile Servers
  2015 26th Int. Symp. on Algorithms and Computation (ISAAC), Nagoya, Japan
  » show abstract« hide abstract
  Abstract

  We study an online problem in which mobile servers have to be moved in order to efficiently serve a set of online requests. More formally, there is a set of n nodes and a set of k mobile servers that are placed at some of the nodes. Each node can potentially host several servers and the servers can be moved between the nodes. There are requests 1,2, ... that are adversarially issued at nodes one at a time, where a request issued at time t needs to be served at all times t' ≥ t. The cost for serving the requests is a function of the number of servers and requests at the different nodes. The requirements on how to serve the requests are governed by two parameters ɑ ≥ 1 and β ≥ 0. An algorithm needs to guarantee that at all times, the total service cost remains within a multiplicative factor of ɑ and an additive term β of the current optimal service cost. We consider online algorithms for two different minimization objectives. We first consider the natural problem of minimizing the total number of server movements. We show that in this case for every k, the competitive ratio of every deterministic online algorithm needs to be at least Ω(n). Given this negative result, we then extend the minimization objective to also include the current service cost. We give almost tight bounds on the competitive ratio of the online problem where one needs to minimize the sum of the total number of movements and the current service cost. In particular, we show that at the cost of an additional additive term which is roughly linear in k, it is possible to achieve a multiplicative competitive ratio of 1+ε for every constant ε>0.
• Fabian Kuhn, Sebastian Daum, Yannic Maus
  Brief Announcement: Rumor Spreading with Bounded In-Degree
  2015 26th Int. Symp. on Distributed Computing (DISC), Tokyo, Japan
  » show abstract« hide abstract
  Abstract

  In the classic gossip-based model of communication for disseminating information in a network, in each time unit, every node u is allowed to contact a single random neighbor v. If u knows the data (rumor) to be disseminated, it disperses it to v (known as PUSH) and if it does not, it requests it from v (known as PULL). While in the classic gossip model, each node is only allowed to contact a single neighbor in each time unit, each node can possibly be contacted by many neighboring nodes. In the present paper, we consider a restricted model where at each node only one incoming request can be served. As long as only a single piece of information needs to be disseminated, this does not make a difference for push requests. It however has a significant effect on pull requests. In the paper, we therefore concentrate on this weaker pull version, which we call 'restricted pull'. We distinguish two versions of the restricted pull protocol depending on whether the request to be served among a set of pull requests at a given node is chosen adversarially or uniformly at random. As a first result, we prove an exponential separation between the two variants. We show that there are instances where if an adversary picks the request to be served, the restricted pull protocol requires a polynomial number of rounds whereas if the winning request is chosen uniformly at random, the restricted pull protocol only requires a polylogarithmic number of rounds to inform the whole network. Further, as the main technical contribution, we show that if the request to be served is chosen randomly, the slowdown of using restricted pull versus using the classic pull protocol can w.h.p. be upper bounded by O(Δ/δlogn), where Δ and δ are the largest and smallest degree of the network.
• Sebastian Daum, Fabian Kuhn
  Tight Bounds for MIS in Multichannel Radio Networks
  2015 26th Int. Symp. on Distributed Computing (DISC), Tokyo, Japan
  » show abstract« hide abstract
  Abstract

  In [7] an algorithm has been presented that computes a maximal independent set (MIS) within O(log^2 n/F + log n polyloglog n) rounds in an n-node multichannel radio network with F communication channels. The paper uses a multichannel variant of the standard graph-based radio network model without collision detection and it assumes that the network graph is a polynomially bounded independence graph (BIG), a natural combinatorial generalization of well-known geographic families. The upper bound of [7] is known to be optimal up to a polyloglog factor. In this paper, we adapt algorithm and analysis to improve the result of [7] in two ways. Mainly, we get rid of the polyloglog factor in the running time and we thus obtain an asymptotically optimal multichannel radio network MIS algorithm. In addition, our new analysis allows to generalize the class of graphs from those with polynomially bounded local independence to graphs where the local independence is bounded by an arbitrary function of the neighborhood radius.
• Seth Gilbert, Fabian Kuhn, Calvin Newport, Chaodong Zheng
  Efficient Communication in Cognitive Radio Networks
  2015 34th ACM Symp. on Principles of Distributed Computing (PODC), San Sebastián, Spain
  » show abstract« hide abstract
  Abstract

  Devices in a cognitive radio network use advanced radios to identify pockets of usable spectrum in a crowded band and make them available to higher layers of the network stack. A core challenge in designing algorithms for this model is that different devices might have different views of the network. In this paper, we study two problems for this setting that are well-motivated but not yet well-understood: local broadcast and data aggregation. We consider a single hop cognitive radio network with n nodes that each has access to c channels. We assume each pair of nodes overlaps on at least 1<=k<=c channels. We first describe and analyze CogCast, a randomized algorithm that solves local broadcast in O( (c/k)*max{1,c/n}*lg(n) ) time, with high probability, by spreading information in an epidemic manner through the network. We then propose CogComp, a randomized algorithm that solves data aggregation in O( (c/k)*max{1,c/n}*lg(n) + n ) time, with high probability. The CogComp algorithm uses CogCast as a key primitive to establish a spanning tree among the nodes, so that data can be aggregated from leaves to root. We conclude with a collection of lower bounds that show CogCast is near optimal (in particular, within a lg(n) factor) in many cases. These bounds introduce new techniques of potential standalone interest for those concerned with proving fundamental limits in the cognitive radio network setting.
• Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, Boaz Patt-Shamir
  Near-Optimal Distributed Maximum Flow: Extended Abstract
  2015 34th ACM Symp. on Principles of Distributed Computing (PODC), San Sebastián, Spain
  » show abstract« hide abstract
  Abstract

  We present a near-optimal distributed algorithm for (1+o(1))-approximation of single-commodity maximum flow in undirected weighted networks that runs in (D+ √n)⋅ n^o(1) communication rounds in the Congest model. Here, n and D denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial O(m) time bound, and it nearly matches the Ω(D+√n) round complexity lower bound. The algorithm contains two sub-algorithms of independent interest, both with running time (D+√n)⋅ n^o(1): Distributed construction of a spanning tree of average stretch n^o(1). Distributed construction of an n^o(1)-congestion approximator consisting of the cuts induced by O(log n) virtual trees. The distributed representation of the cut approximator allows for evaluation in (D+√n)⋅ n^o(1) rounds. All our algorithms make use of randomization and succeed with high probability.
• Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn
  Tight Bounds on Vertex Connectivity Under Vertex Sampling
  2015 26th ACM-SIAM Symp. on Discrete Algorithms (SODA), San Diego CA, USA
  » show abstract« hide abstract
  Abstract

  A fundamental result by Karger states that for any λ-edge-connected graph with n nodes, independently sampling each edge with probability p = Ω(log(n)/λ) results in a graph that has edge connectivity Ω(λp), with high probability. This paper proves the analogous result for vertex connectivity, when sampling vertices. We show that for any k-vertex-connected graph G with n nodes, if each node is independently sampled with probability , then the subgraph induced by the sampled nodes has vertex connectivity Ω(kp^2), with high probability. This bound improves upon the recent results of Censor-Hillel et al., and it is existentially optimal.
• Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan
  Distributed Computation of Sparse Cuts via Random Walks
  2015 16th International Conference on Distributed Computing and Networking (ICDCN), Goa, India
  » show abstract« hide abstract
  Abstract

  A sparse cut of a graph is a partition of the vertices into two disjoint subsets such that the ratio of the number of edges across the two subsets divided by the sum of degrees of vertices in the smaller side is minimum. Finding sparse cuts is an important tool in analyzing large-scale distributed networks such as the Internet and Peer-to-Peer networks, as well as large-scale graphs such as the web graph, online social communities, and VLSI circuits. Sparse cuts are useful in graph clustering and partitioning among numerous other applications. In distributed communication networks, they are useful for topology maintenance and for designing better search and routing algorithms. In this paper, we focus on developing a fast distributed algorithm for computing sparse cuts in networks. Given an undirected n-node network G with conductance &phis;, the goal is to find a cut set whose conductance is close to &phis;. We present a distributed algorithm that finds a cut set with sparsity Õ(√&phis;) (Õ hides polylog n factors). Our algorithm works in the CONGEST distributed computing model and outputs a cut of conductance at most Õ (√&phis;) with high probability, in Õ(1/b(1/&phis; + n)log2) rounds, where b is balance of the cut of given conductance. In particular, to find a sparse cut of constant balance, our algorithm takes O((1/&phis; + n)log2 n) rounds. Our algorithm can also be used to output a local cluster, i.e., a subset of vertices near a given source node, and whose conductance is within a quadratic factor of the best possible cluster around the specified node. Our distributed algorithm can work without knowledge of the optimal &phis; value (with only a log n factor slowdown) and hence can be used to find approximate conductance values both globally and with respect to a given source node. Our algorithm uses random walks as a key subroutine and is fully decentralized and uses lightweight local computations. We also give a lower bound on the time needed for any distributed algorithm to compute any non-trivial sparse cut --- any distributed approximation algorithm (for any nontrivial approximation ratio) for computing sparsest cut will take Ω (√n + D) rounds, where D is the diameter of the graph. Our algorithm can be used to find sparse cuts (and their conductance values) and to identify well-connected clusters and critical edges in distributed networks. This in turn can be helpful in the design, analysis, and maintenance of topologically-aware networks.

• Majid Khabbazian, Stephane Durocher, Alireza Haghnegahdar, Fabian Kuhn
  Bounding Interference in Wireless Ad Hoc Networks With Nodes in Random Position
  2015 Ieee Acm T Network, volume: 23, issue: 4, pages: 1078 - 1091
  » show abstract« hide abstract
  Abstract

  Given a set of positions for wireless nodes, the interference minimization problem is to assign a transmission radius (i.e., a power level) to each node such that the resulting communication graph is connected while minimizing the maximum (respectively, average) interference. We consider the model introduced by von Rickenbach (2005), in which each wireless node is represented by a point in Euclidean space on which is centered a transmission range represented by a ball, and edges in the corresponding graph are symmetric. The problem is NP-complete in two or more dimensions (Buchin 2008), and no polynomial-time approximation algorithm is known. We show how to solve the problem efficiently in settings typical for wireless ad hoc networks. If nodes are represented by a set P of n points selected uniformly and independently at random over a d-dimensional rectangular region, then the topology given by the closure of the Euclidean minimum spanning tree of P has O(log n) maximum interference with high probability and O(1) expected interference. We extend the first bound to a general class of communication graphs over a broad set of probability distributions. We present a local algorithm that constructs a graph from this class; this is the first local algorithm to provide an upper bound on expected maximum interference. Finally, we disprove a conjecture of Devroye and Morin (2012) relating the maximum interference of the Euclidean minimum spanning tree to the optimal maximum interference attainable.

• Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan
  Distributed computation in dynamic networks via random walks.
  2015 Theor Comput Sci, volume: 581, pages: 45 - 66
  » show abstract« hide abstract
  Abstract

  The paper investigates efficient distributed computation in dynamic networks in which the network topology changes (arbitrarily) from round to round. Our first contribution is a rigorous framework for design and analysis of distributed random walk algorithms in dynamic networks. We then develop a fast distributed random walk based algorithm that runs in O~(τΦ−−−√) rounds (with high probability), where τ is the dynamic mixing time and Φ is the dynamic diameter of the network respectively, and returns a sample close to a suitably defined stationary distribution of the dynamic network. We also apply our fast random walk algorithm to devise fast distributed algorithms for two key problems, namely, information dissemination and decentralized computation of spectral properties in a dynamic network. Our next contribution is a fast distributed algorithm for the fundamental problem of information dissemination (also called as gossip) in a dynamic network. In gossip, or more generally, k-gossip, there are k pieces of information (or tokens) that are initially present in some nodes and the problem is to disseminate the k tokens to all nodes. We present a random-walk based algorithm that runs in O~(min{n1/3k2/3(τΦ)1/3,nk}) rounds (with high probability). To the best of our knowledge, this is the first o(nk)-time fully-distributed token forwarding algorithm that improves over the previous-best O(nk) round distributed algorithm [Kuhn et al., STOC 2010], although in an oblivious adversary model. Our final contribution is a simple and fast distributed algorithm for estimating the dynamic mixing time and related spectral properties of the underlying dynamic network.

• Franziska Humair, Luc Humair, Fabian Kuhn, Christoph Kueffer
  E-commerce trade in invasive plants
  2015 Conserv Biol, volume: 29, issue: 6, pages: 1658 - 1665

• Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan
  Efficient random walk sampling in distributed networks.
  2015 J Parallel Distr Com, volume: 77, pages: 84 - 94
  » show abstract« hide abstract
  Abstract

  Performing random walks in networks is a fundamental primitive that has found numerous applications in communication networks such as token management, load balancing, network topology discovery and construction, search, and peer-to-peer membership management. While several such algorithms are ubiquitous, and use numerous random walk samples, the walks themselves have always been performed naively. In this paper, we focus on the problem of performing random walk sampling efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds and messages required to obtain several random walk samples in a continuous online fashion. We present the first round and message optimal distributed algorithms that present a significant improvement on all previous approaches. The theoretical analysis and comprehensive simulations of our algorithms show that they perform very well in different types of networks of differing topologies. In particular, our results show how several random walks can be performed continuously (when source nodes are provided only at runtime, i.e., online), such that each walk of length ℓℓ can be performed exactly in just View the MathML sourceÕ(ℓD) rounds1 (where DD is the diameter of the network), and O(ℓ)O(ℓ) messages. This significantly improves upon both, the naive technique that requires O(ℓ)O(ℓ) rounds and O(ℓ)O(ℓ) messages, and the sophisticated algorithm of Das Sarma et al. (2013) that has the same round complexity as this paper but requires View the MathML sourceΩ(mℓ) messages (where mm is the number of edges in the network). Our theoretical results are corroborated through extensive simulations on various topological data sets. Our algorithms are fully decentralized, lightweight, and easily implementable, and can serve as building blocks in the design of topologically-aware networks.

• Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan, Eli Upfal
  Fast distributed PageRank computation.
  2015 Theor Comput Sci, volume: 561, pages: 113 - 121
  » show abstract« hide abstract
  Abstract

  Over the last decade, PageRank has gained importance in a wide range of applications and domains, ever since it first proved to be effective in determining node importance in large graphs (and was a pioneering idea behind Google's search engine). In distributed computing alone, PageRank vectors, or more generally random walk based quantities have been used for several different applications ranging from determining important nodes, load balancing, search, and identifying connectivity structures. Surprisingly, however, there has been little work towards designing provably efficient fully-distributed algorithms for computing PageRank. The difficulty is that traditional matrix-vector multiplication style iterative methods may not always adapt well to the distributed setting owing to communication bandwidth restrictions and convergence rates. In this paper, we present fast random walk-based distributed algorithms for computing PageRank in general graphs and prove strong bounds on the round complexity. We first present an algorithm that takes $O(\log n/\eps)$ rounds with high probability on any graph (directed or undirected), where n is the network size and $\eps$ is the reset probability used in the PageRank computation. We then present a faster algorithm that takes $O(\sqrt{\log n}/\eps)$ rounds in undirected graphs. Both of the above algorithms are scalable, as each node processes and sends only small (polylogarithmic in n, the network size) number of bits per round and hence work in the {\sc CONGEST} distributed computing model. For directed graphs, we present an algorithm that has a running time of $O(\sqrt{\log n/\eps})$, but it requires a polynomial number of bits to processed and sent per node in a round. To the best of our knowledge, these are the first fully distributed algorithms for computing PageRank vectors with provably efficient running time.

2014

• Andrew Drucker, Fabian Kuhn, Rotem Oshman
  On the Power of the Congested Clique Model
  2014 33rd ACM Symp. on Principles of Distributed Computing (PODC), Paris, France
  » show abstract« hide abstract
  Abstract

  We study the computation power of the congested clique, a model of distributed computation where n players communicate with each other over a complete network in order to compute some function of their inputs. The number of bits that can be sent on any edge in a round is bounded by a parameter b We consider two versions of the model: in the first, the players communicate by unicast, allowing them to send a different message on each of their links in one round; in the second, the players communicate by broadcast, sending one message to all their neighbors. It is known that the unicast version of the model is quite powerful; to date, no lower bounds for this model are known. In this paper we provide a partial explanation by showing that the unicast congested clique can simulate powerful classes of bounded-depth circuits, implying that even slightly super-constant lower bounds for the congested clique would give new lower bounds in circuit complexity. Moreover, under a widely-believed conjecture on matrix multiplication, the triangle detection problem, studied in [8], can be solved in O(nε) time for any ε > 0. The broadcast version of the congested clique is the well-known multi-party shared-blackboard model of communication complexity (with number-in-hand input). This version is more amenable to lower bounds, and in this paper we show that the subgraph detection problem studied in [8] requires polynomially many rounds for several classes of subgraphs. We also give upper bounds for the subgraph detection problem, and relate the hardness of triangle detection in the broadcast congested clique to the communication complexity of set disjointness in the 3-party number-on-forehead model.
• Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn
  Distributed Connectivity Decomposition
  2014 33rd ACM Symp. on Principles of Distributed Computing (PODC), Paris, France
  » show abstract« hide abstract
  Abstract

  A fundamental problem in distributed network algorithms is to manage congestion and obtain information flow matching the graph's connectivity. In this paper, we present time-efficient distributed algorithms for decomposing graphs with large edge or vertex connectivity into multiple spanning or dominating trees, respectively. These decompositions allow us to achieve a flow with size close to the connectivity by parallelizing it along the trees. More specifically, our distributed decomposition algorithms are as follows: - A decomposition of each undirected graph with vertex-connectivity k into (fractionally) vertex-disjoint weighted dominating trees with total weight Omega(k/log n), in \tilde{O}(D+\sqrt{n}) rounds. - A decomposition of each undirected graph with edge-connectivity \lambda into (fractionally) edge-disjoint weighted spanning trees with total weight (1-eps)(\lambda/2), in \tilde{O}(D+\sqrt{n\lambda}) rounds. We also show round complexity lower bounds of \tilde{Omega}(D+\sqrt{n/k}) and \tilde{Omega}(D+\sqrt{n/\lambda}) for the above two decompositions, using techniques of [Das Sarma et al., STOC'11]. Moreover, our vertex-connectivity decomposition extends to centralized algorithms and improves the time complexity of [Censor-Hillel et al., SODA'14] from O(n^3) to near-optimal \tilde{O}(m). Additional implications of our results are: a near-linear time centralized approximation of vertex connectivity which can be seen as a step towards a conjecture of Aho, Hopcroft and Ullman), the first distributed approximating of vertex connectivity, and distributed algorithms with near-optimal competitiveness for oblivious broadcast routing.
• Karl Bringman, Fabian Kuhn, Konstantinos Panagiotou, Ueli Peter, Henning Thomas
  Internal DLA: Efficient Simulation of a Physical Growth Model
  2014 41st Int.l Colloquium on Automata, Languages, and Programming (ICALP), Copenhagen, Denmark
  » show abstract« hide abstract
  Abstract

  The internal diffusion limited aggregation (IDLA) process places n particles on the two dimensional integer grid. The first particle is placed on the origin; every subsequent particle starts at the origin and performs an unbiased random walk until it reaches an unoccupied position. In this work we study the computational complexity of determining the subset that is generated after n particles have been placed. We develop the first algorithm that provably outperforms the naive step-by-step simulation of all particles. Particularly, our algorithm has a running time of O(n log^2 n) and a sublinear space requirement of O(\sqrt{n} log n), both in expectation and with high probability. In contrast to some speedups proposed for similar models in the physics community, our algorithm samples from the exact distribution. To simulate a single particle fast we have to develop techniques for combining multiple steps of a random walk to large jumps without hitting a forbidden set of grid points. These techniques might be of independent interest for speeding up other problems based on random walks.
• Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn
  A New Perspective on Vertex Connectivity
  2014 25th ACM-SIAM Symp. on Discrete Algorithms (SODA), Portland OR, USA
  » show abstract« hide abstract
  Abstract

  Edge connectivity and vertex connectivity are two fundamental concepts in graph theory. Although by now there is a good understanding of the structure of graphs based on their edge connectivity, our knowledge in the case of vertex connectivity is much more limited. An essential tool in capturing edge connectivity are the classical results of Tutte and Nash-Williams from 1961 which show that a $\lambda$-edge-connected graph contains $\ceil{(\lambda-1)/2}$ edge-disjoint spanning trees. We argue that connected dominating set partitions and packings are the natural analogues of edge-disjoint spanning trees in the context of vertex connectivity and we use them to obtain structural results about vertex connectivity in the spirit of those for edge connectivity. More specifically, connected dominating set (CDS) partitions and packings are counterparts of edge-disjoint spanning trees, focusing on vertex-disjointness rather than edge-disjointness, and their sizes are always upper bounded by the vertex connectivity $k$. We constructively show that every $k$-vertex-connected graph with $n$ nodes has CDS packings and partitions with sizes, respectively, $\Omega(k/\log n)$ and $\Omega(k/\log^5 n )$, and we prove that the former bound is existentially optimal. Beautiful results by Karger show that when edges of a $\lambda$-edge-connected graph are independently sampled with probability $p$, the sampled graph has edge connectivity $\tilde{\Omega}(\lambda p)$. Obtaining such a result for vertex sampling remained open. We illustrate the strength of our approach by proving that when vertices of a $k$-vertex-connected graph are independently sampled with probability $p$, the graph induced by the sampled vertices has vertex connectivity $\tilde{\Omega}(kp^2)$. This bound is optimal up to poly-log factors and is proven by building an $\tilde{\Omega}(kp^2)$ size CDS packing on the sampled vertices while sampling happens. As an additional important application, we show CDS packings to be tightly related to the throughput of routing-based algorithms and use our new toolbox to yield a routing-based broadcast algorithm with optimal throughput $\Omega(k/\log n + 1)$, improving the (previously best-known) trivial throughput of $\Theta(1)$.

• Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, Nancy Lynch
  Decomposing Broadcast Algorithms Using Abstract MAC Layers
  2014 Ad Hoc Netw, volume: 12, pages: 219 - 242

• Leonid Barenboim, Michael Elkin, Fabian Kuhn
  Distributed (Delta+1)-Coloring in Linear (in Delta) Time
  2014 Siam J Comput, volume: 43, issue: 1, pages: 72 - 95
  » show abstract« hide abstract
  Abstract

  The distributed $(\Delta + 1)$-coloring problem is one of the most fundamental and well-studied problems in distributed algorithms. Starting with the work of Cole and Vishkin in 1986, a long line of gradually improving algorithms has been published. The state-of-the-art running time, prior to our work, is $O(\Delta \log \Delta + \log^* n)$, due to Kuhn and Wattenhofer [Proceedings of the $25$th Annual ACM Symposium on Principles of Distributed Computing, Denver, CO, 2006, pp. 7--15]. Linial [Proceedings of the $28$th Annual IEEE Symposium on Foundation of Computer Science, Los Angeles, CA, 1987, pp. 331--335] proved a lower bound of $\frac{1}{2} \log^* n$ for the problem, and Szegedy and Vishwanathan [Proceedings of the 25th Annual ACM Symposium on Theory of Computing, San Diego, CA, 1993, pp. 201--207] provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve a running time smaller than $\Theta(\Delta \log \Delta)$. We present a deterministic $(\Delta + 1)$-coloring distributed algorithm with running time $O(\Delta) + \frac{1}{2} \log^* n$. We also present a trade-off between the running time and the number of colors, and devise an $O(\lambda\cdot\Delta)$-coloring algorithm, with running time $O(\Delta / \lambda + \log^* n)$, for any parameter $\lambda > 1$. Our algorithm breaks the heuristic barrier of Szegedy and Vishwanathan and achieves running time which is linear in the maximum degree $\Delta$. On the other hand, the conjecture of Szegedy and Vishwanathan may still be true, as our algorithm does not belong to the family of locally iterative algorithms. On the way to this result we study a generalization of the notion of graph coloring, which is called defective coloring [L. Cowen, R. Cowen, and D. Woodall, J. Graph Theory, 10 (1986), pp. 187--195]. In an $m$-defective $p$-coloring the vertices are colored with $p$ colors so that each vertex has up to $m$ neighbors with the same color. We show that an $m$-defective $p$-coloring with reasonably small $m$ and $p$ can be computed very efficiently in the distributed setting. We also develop a technique to employ multiple defective colorings of various subgraphs of the original graph $G$ for computing a $(\Delta+1)$-coloring of $G$. We believe that these techniques are of independent interest.

• Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch, Calvin Newport
  Structuring Unreliable Radio Networks
  2014 Distrib Comput, volume: 27, issue: 1, pages: 1 - 19

2013

• Sebastian Daum, Seth Gilbert, Fabian Kuhn, Calvin Newport
  Broadcast in the Ad Hoc SINR Model
  2013 27th Int. Symp. on Distributed Computing (DISC), Jerusalem, Israel , pages: 358 - 372
  » show abstract« hide abstract
  Abstract

  An increasing amount of attention is being turned toward the study of distributed algorithms in wireless network models based on calculations of the signal to noise and interference ratio (SINR). In this paper we introduce the ad hoc SINR model, which, we argue, reduces the gap between theory results and real world deployment. We then use it to study upper and lower bounds for the canonical problem of broadcast on the graph induced by both strong and weak links. For strong connectivity broadcast, we present a new randomized algorithm that solves the problem in O(Dlog(n)polylog(R)) rounds in networks of size n, with link graph diameter D, and a ratio between longest and shortest links bounded by R. We then show that for back-off style algorithms (a common type of algorithm where nodes do not explicitly coordinate with each other) and compact networks (a practice-motivated model variant that treats the distance from very close nodes as equivalent), there exist networks in which centralized algorithms can solve broadcast in O(1) rounds, but distributed solutions require Ω(n) rounds. We then turn our attention to weak connectivity broadcast, where we show a similar Ω(n) lower bound for all types of algorithms, which we (nearly) match with a back-off style O(nlog^2 n)-round upper bound. Our broadcast algorithms are the first known for SINR-style models that do not assume synchronous starts, as well as the first known not to depend on power control, tunable carrier sensing, geographic information and/or exact knowledge of network parameters.
• Mohsen Ghaffari, Fabian Kuhn
  Distributed Minimum Cut Approximation (best paper award)
  2013 27th Int. Symp. on Distributed Computing (DISC), Jerusalem, Israel , pages: 1 - 15
  » show abstract« hide abstract
  Abstract

  We study the problem of computing approximate minimum edge cuts by distributed algorithms. We use a standard synchronous message passing model where in each round, O(logn) bits can be transmitted over each edge (a.k.a. the CONGEST model). The first algorithm is based on a simple and new approach for analyzing random edge sampling, which we call the random layering technique. For any weighted graph and any ε ∈ (0, 1), the algorithm with high probability finds a cut of size at most O(ε^(-1)λ) in O(D)+\tilde{O}(n^(1/2+ϵ)) rounds, where λ is the size of the minimum cut and the \tilde{O}-notation hides poly-logarithmic factors in n. In addition, based on a centralized algorithm due to Matula [SODA ’93], we present a randomized distributed algorithm that with high probability computes a cut of size at most (2 + ε)λ in \tilde{O}((D+\sqrt{n})/ϵ^5) rounds for any ε > 0. The time complexities of our algorithms almost match the \tilde{Ω}(D+\sqrt{n}) lower bound of Das Sarma et al. [STOC ’11], thus leading to an answer to an open question raised by Elkin [SIGACT-News ’04] and Das Sarma et al. [STOC ’11]. To complement our upper bound results, we also strengthen the \tilde{\Omega}(D+\sqrt{n}) lower bound of Das Sarma et al. by extending it to unweighted graphs. We show that the same lower bound also holds for unweighted multigraphs (or equivalently for weighted graphs in which O(w logn) bits can be transmitted in each round over an edge of weight w). For unweighted simple graphs, we show that computing an α-approximate minimum cut requires time at least \tilde{Ω}(D+\sqrt{n/α}). Full version (fixes some issues with the lower bounds in the conference version): http://arxiv.org/abs/1305.5520
• Sebastian Daum, Mohsen Ghaffari, Seth Gilbert, Fabian Kuhn, Calvin Newport
  Maximal Independent Sets in Multichannel Radio Networks
  2013 32nd ACM Symp. on Principles of Distributed Computing (PODC), Montreal, Canada , pages: 335 - 344
  » show abstract« hide abstract
  Abstract

  We present new upper bounds for fundamental problems in multichannel wireless networks. These bounds address the benefits of dynamic spectrum access, i.e., to what extent multiple communication channels can be used to improve performance. In more detail, we study a multichannel generalization of the standard graph-based wireless model without collision detection, and assume the network topology satisfies polynomially bounded independence. Our core technical result is an algorithm that constructs a maximal independent set (MIS) in O(log^2(n)/F)+ Õ(log n) rounds, in networks of size n with F channels, where the Õ-notation hides polynomial factors in loglog n. Moreover, we use this MIS algorithm as a subroutine to build a constant-degree connected dominating set in the same asymptotic time. Leveraging this structure, we are able to solve global broadcast and leader election within O(D + log^2(n)/F) + Õ(logn) rounds, where D is the diameter of the graph, and k-message multi-message broadcast in O(D + k + log^2(n)/F)+Õ(logn) rounds for unrestricted message size (with a slow down of only a log factor on the k term under the assumption of restricted message size). In all five cases above, we prove: (a) our results hold with high probability (i.e., at least 1-1/n); (b) our results are within polyloglog factors of the relevant lower bounds for multichannel networks; and (c) our results beat the relevant lower bounds for single channel networks. These new (near) optimal algorithms significantly expand the number of problems now known to be solvable faster in multichannel versus single channel wireless networks.

• Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn
  Beeping a Maximal Independent Set
  2013 Distrib Comput, volume: 26, issue: 4, pages: 195 - 208
  » show abstract« hide abstract
  Abstract

  We consider the problem of computing a maximal independent set (MIS) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that an adversary chooses at which time slot each node wakes up. At each time slot a node can either beep, that is, emit a signal, or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and find an MIS in polylogarithmic time. First, we show that if a polynomial upper bound on the network size is known, it is possible to find an MIS in O(log^3 n) time. Second, if we assume sleeping nodes are awoken by neighboring beeps, then we can also find an MIS in O(log^3 n) time. Third, if in addition to this wakeup assumption we allow sender-side collision detection, that is, beeping nodes can distinguish whether at least one neighboring node is beeping concurrently or not, we can find an MIS in O(log^2 n) time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to find an MIS in O(log^2 n) time.

• Fabian Kuhn, Monaldo Mastrolilli
  Vertex Cover in Graphs with Locally Few Colors
  2013 Inform Comput, volume: 222, pages: 265 - 277
  » show abstract« hide abstract
  Abstract

  Erdős et al. defined the local chromatic number of a graph as the minimum number of colors that must appear within distance 1 of a vertex. For any Δ⩾2, there are graphs with arbitrarily large chromatic number that can be colored so that (i) no vertex neighborhood contains more than Δ different colors (bounded local colorability), and (ii) adjacent vertices from two color classes induce a complete bipartite graph (biclique coloring). We investigate the weighted vertex cover problem in graphs when a locally bounded coloring is given. This generalizes the vertex cover problem in bounded degree graphs to a class of graphs with arbitrarily large chromatic number. Assuming the Unique Game Conjecture (UGC), we provide a tight characterization. We prove that it is UGC-hard to improve the approximation ratio of 2−2/(Δ+1) on (Δ+1)-locally (but not necessarily biclique) colorable graphs. A matching upper bound is also provided. Vice versa, when properties (i) and (ii) hold, we present a randomized algorithm with approximation ratio of 2-Omega(loglog(Δ)/log(Δ)). This matches known inapproximability results for the special case of bounded degree graphs. Moreover, we show that when both the above two properties (i) and (ii) hold, the obtained result finds a natural application in a classical scheduling problem, namely the precedence constrained single machine scheduling problem to minimize the total weighted completion time, denoted as 1|prec|∑wjCj in standard scheduling notation. In a series of recent papers it was established that this scheduling problem is a special case of the minimum weighted vertex cover in graphs GP of incomparable pairs defined in the dimension theory of partial orders. We show that GP satisfies properties (i) and (ii) where Δ−1 is the maximum number of predecessors (or successors) of each job.

2012

• Sebastian Daum, Fabian Kuhn, Calvin Newport
  Efficient Symmetry Breaking in Multi-Channel Radio Networks
  2012 26th Int. Symp. on Distributed Computing (DISC), Salvador, Bahia, Brazil , pages: 238 - 252
• Bernhard Haeupler, Fabian Kuhn
  Lower Bounds on Information Dissemination in Dynamic Networks
  2012 26th International Symposium on Distributed Computing (DISC), Salvador, Bahia, Brazil , pages: 166 - 180
• Sebastian Daum, Seth Gilbert, Fabian Kuhn, Calvin Newport
  Leader Election in Shared Spectrum Radio Networks
  2012 31st ACM Symp. on Principles of Distributed Computing (PODC), Madeira, Portugal , pages: 215 - 224
• Andrew Drucker, Fabian Kuhn, Rotem Oshman
  The Communication Complexity of Distributed Task Allocation
  2012 31st ACM Symp. on Principles of Distributed Computing (PODC), Madeira, Portugal , pages: 67 - 76
• Antonio Carzaniga, Koorosh Khazaei, Fabian Kuhn
  Oblivious Low-Congestion Multicast Routing in Wireless Networks
  2012 13th ACM Int. Symp. on Mobile Ad Hoc Networking and Computing (MOBIHOC) , Hilton Head Island, SC, USA , pages: 155 - 164

2011

• Fabian Kuhn, Rotem Oshman
  The Complexity of Data Aggregation in Directed Networks
  2011 25th Int. Symp. on Distributed Computing (DISC), Rome, Italy , pages: 416 - 431
• Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn
  Beeping a Maximal Independent Set
  2011 25th Int. Symp. on Distributed Computing (DISC), Rome, Italy , pages: 32 - 50
• Fabian Kuhn, Monaldo Mastrolilli
  Vertex Cover in Graphs with Locally Few Colors
  2011 38th Int. Colloquium on Automata, Languages and Programming (ICALP), Zurich, Switzerland , pages: 498 - 509
• Majid Khabbazian, Fabian Kuhn, Nancy Lynch, Muriel Médard, Ali ParandehGheibi
  MAC Design for Analog Network Coding
  2011 7th ACM Workshop on Foundations of Mobile Computing (FOMC), San Jose CA, USA , pages: 42 - 51
• Fabian Kuhn, Yoram Moses, Rotem Oshman
  Coordinated Consensus in Dynamic Networks
  2011 30th ACM Symp. on Principles of Distributed Computing (PODC), San Jose CA, USA , pages: 1 - 10
• Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch, Calvin Newport
  Structuring Unreliable Radio Networks
  2011 30th ACM Symp. on Principles of Distributed Computing (PODC), San Jose CA, USA , pages: 79 - 88

• Sebastian Daum, Ralf Werner
  A Novel Feasible Discretization Method for Linear Semi-infinite Programming Applied to Basket Option Pricing
  2011 Optimization, volume: 60, issue: 10, pages: 1379 - 1398
  » show abstract« hide abstract
  Abstract

  In this exposition a novel feasible version of traditional discretization methods for linear semi-infinite programming problems is presented. It will be shown that each – usually infeasible – iterate can be easily supplemented with a feasible iterate based on the knowledge of a Slater point. The effectiveness of the method is demonstrated on the problem of finding model free bounds to basket option prices which has gained a significant interest in the last years. For this purpose a fresh look is taken on the upper bound problem and on some of its structure, which needs to be exploited to yield an efficient solution by the feasible discretization method. The presented approach allows the generalization of the problem setting by including exotic options (like power options, log-contracts, binary options, etc.) within the super-replicating portfolio.

• Fabian Kuhn, Rotem Oshman
  Dynamic Networks: Models and Algorithms
  2011 ACM SIGACT News, volume: Volume 42, issue: 1

• Fabian Kuhn, Thomas Locher, Rotem Oshman
  Gradient Clock Synchronization in Dynamic Networks
  2011 Theor Comput Syst, volume: 49, issue: 4, pages: 781 - 816

• Fabian Kuhn, Nancy Lynch, Calvin Newport
  The Abstract MAC Layer
  2011 Distrib Comput (Distributed Computing), volume: 24, issue: 3-4, pages: 187 - 206

2010

• Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, Nancy Lynch
  Decomposing Broadcast Algorithms Using Abstract MAC Layers
  2010 6th ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cambridge MA, USA , pages: 13 - 22
• Alejandro Cornejo, Fabian Kuhn
  Deploying Wireless Networks with Beeps
  2010 24th Int. Symp. on Distributed Computing (DISC), Cambridge MA, USA , pages: 148 - 162
• Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, Andrea Richa
  Broadcasting in Unreliable Radio Networks
  2010 29th ACM Symp. on Principles of Distributed Computing (PODC), Zurich, Switzerland , pages: 336 - 345
• Fabian Kuhn, Christoph Lenzen, Thomas Locher, Rotem Oshman
  Optimal Gradient Clock Synchronization in Dynamic Networks
  2010 29th ACM Symp. on Principles of Distributed Computing (PODC), Zurich, Switzerland , pages: 430 - 439
• Fabian Kuhn, Nancy Lynch, Rotem Oshman
  Distributed Computation in Dynamic Networks
  2010 42nd ACM Symp. on Theory of Computing (STOC), Cambridge MA, USA , pages: 513 - 522
• Fabian Kuhn, Konstantinos Panagiotou, Joel Spencer, Angelika Steger.
  Synchrony and Asynchrony in Neural Networks
  2010 21st ACM-SIAM Symp. on Discrete Algorithms (SODA), Atlanta GA, USA , pages: 949 - 964

• Fabian Kuhn, Thomas Moscibroda
  Distributed Approximation of Capacitated Dominating Sets
  2010 Theor Comput Syst, volume: 47, issue: 4, pages: 811 - 836

• Fabian Kuhn, Stefan Schmid, Roger Wattenhofer
  Towards Worst-Case Churn Resistant Peer-to-Peer Systems
  2010 Distrib Comput, volume: Volume 22, issue: 4, pages: 249 - 267

2009

• Fabian Kuhn, Rotem Oshman
  Gradient Clock Synchronization Using Reference Broadcasts
  2009 13th Int. Conf. on Principles of Distributed Systems (OPODIS), Nîmes, France , pages: 204 - 218
• Alejandro Cornejo, Fabian Kuhn, Ruy Ley-Wild, Nancy Lynch
  Keeping Mobile Robot Swarms Connected
  2009 23rd Int. Symp. on Distributed Computing (DISC), Elche, Spain , pages: 496 - 511
• Fabian Kuhn, Nancy Lynch, Calvin Newport
  The Abstract MAC Layer
  2009 23rd Int. Symp. on Distributed Computing (DISC), Elche, Spain , pages: 48 - 62
• Fabian Kuhn, Thomas Locher, Rotem Oshman
  Gradient Clock Synchronization in Dynamic Networks
  2009 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), Calgary, Canada , pages: 270 - 279
• Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Fabian Kuhn, Calvin Newport
  The Wireless Synchronization Problem
  2009 28th ACM Symp. on Principles of Distributed Computing (PODC), Calgary, Canada , pages: 190 - 199
• Fabian Kuhn
  Weak Graph Coloring: Distributed Algorithms and Applications
  2009 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), Calgary, Canada , pages: 138 - 144
• Venugopalan Ramasubramanian, Dahlia Malkhi, Fabian Kuhn, Mahesh Balakrishnan, Archit Gupta, Aditya Akella
  On the Treeness of Internet Latency and Bandwidth
  2009 11th ACM Joint Conf. on Measurement and Modeling of Computer Systems (SIGMETRICS/Performance), Seattle WA, USA , pages: 61 - 72
• Fabian Kuhn
  Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
  2009 26th Symp. on Theoretical Aspects of Computer Science (STACS), Freiburg, Germany , pages: 613 - 624

2008

• Fabian Kuhn, Thomas Locher, Stefan Schmid
  Distributed Computation of the Mode
  2008 27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada
• Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, Kunal Talwar
  Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings
  2008 27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada
• Torsten Muetze, Patrick Stuedi, Fabian Kuhn, Gustavo Alonso
  Understanding Radio Irregularity in Wireless Networks
  2008 5th IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), San Francisco, California, USA
  » show abstract« hide abstract
  Abstract

  In an effort to better understand connectivity and capacity in wireless networks, the log-normal shadowing ra dio propagation model is used to capture radio irregularities a nd ob- stacles in the transmission path. Existing results indicat e that log- normal shadowing results in higher connectivity and interf erence levels as shadowing (i.e., the radio irregularity) increas es. In this paper we demonstrate that such a behavior is mainly caused by an unnatural bias of the log-normal shadowing radio propaga tion model that results in a larger transmission range as shadowi ng increases. To avoid this effect, we analyze connectivity an d interference under log-normal shadowing using a normaliza tion that compensates for the enlarged radio transmission range . Our analysis shows that log-normal shadowing still improve s the connectivity of a wireless network and even reduces interfe rence. We explain this behavior by studying in detail what network parameters are affected by shadowing. Our results indicate that, when it comes to connectivity and interference, an analysis based on a circular transmission range leads to worst case results

• Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
  Ad hoc networks beyond unit disk graphs
  2008 Wirel Netw, volume: 14, issue: 5, pages: 715 - 729
  » show abstract« hide abstract
  Abstract

  In this paper, we study an algorithmic model for wireless ad hoc and sensor networks that aims to be sufficiently close to reality as to represent practical realworld networks while at the same time being concise enough to promote strong theoretical results. The quasi unit disk graph model contains all edges shorter than a parameter d between 0 and 1 and no edges longer than 1. We show that—in comparison to the cost known for unit disk graphs—the complexity results of geographic routing in this model contain the additional factor 1/d 2. We prove that in quasi unit disk graphs flooding is an asymptotically message-optimal routing technique, we provide a geographic routing algorithm being most efficient in dense networks, and we show that classic geographic routing is possible with the same asymptotic performance guarantees as for unit disk graphs if d≥1/√2.

• Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
  An Algorithmic Approach to Geographic Routing in Ad Hoc and Sensor Networks
  2008 Ieee Acm T Network, volume: 16, issue: 1, pages: 51 - 62
  » show abstract« hide abstract
  Abstract

  The one type of routing in ad hoc and sensor networks that currently appears to be most amenable to algorithmic analysis is geographic routing. This paper contains an introduction to the problem field of geographic routing, presents a specific routing algorithm based on a synthesis of the greedy forwarding and face routing approaches, and provides an algorithmic analysis of the presented algorithm from both a worst-case and an average-case perspective.

• Fabian Kuhn, Thomas Locher, Roger Wattenhofer
  Distributed selection: a missing piece of data aggregation
  2008 Commun Acm, volume: 51, issue: 9, pages: 93 - 99
  » show abstract« hide abstract
  Abstract

  In this article, we study the problem of distributed selection from a theoretical point of view. Given a general connected graph of diameter D consisting of n nodes in which each node holds a numeric element, the goal of a k-selection algorithm is to determine the kth smallest of these elements. We prove that distributed selection indeed requires more work than other aggregation functions such as, e.g., the computation of the average or the maximum of all elements. On the other hand, we show that the kth smallest element can be computed efficiently by providing both a randomized and a deterministic k-selection algorithm, dispelling the misconception that solving distributed selection through in-network aggregation is infeasible.

2007

• Ittai Abraham, Mahesh Balakrishnan, Fabian Kuhn, Dahlia Malkhi, Venugopalan Ramasubramanian, Kunal Talwar
  Reconstructing Approximate Tree Metrics
  2007 26th ACM Symposium on Principles of Distributed Computing (PODC), Portland, Oregon, USA
• Fabian Kuhn, Thomas Moscibroda
  Distributed Approximation of Capacitated Dominating Sets
  2007 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego, California, USA
  » show abstract« hide abstract
  Abstract

  We study local, distributed algorithms for the capacitated minimum dominating set (CapMDS) problem, which arises in various dis- tributed network applications. Given a network graph G = ( V; E ) , and a capacity cap ( v ) 2 N for each node v 2 V , the CapMDS problem asks for a subset S μ V of minimal cardinality, such that every network node not in S is covered by at least one neighbor in S , and every node v 2 S covers at most cap ( v ) of its neighbors. We prove that in general graphs and even with uniform capacities, the problem is inherently non-local , i.e., every distributed algorithm achieving a non-trivial approximation ratio must have a time com- plexity that essentially grows linearly with the network diameter. On the other hand, if for some parameter ≤ > 0 , capacities can be vi- olated by a factor of 1 + ≤ , CapMDS becomes much more local. Particularly, based on a novel distributed randomized rounding tech- nique, we present a distributed bi-criteria algorithm that achieves an O(log ¢) -approximation in time O(log 3 n + log( n ) =≤ ) , where n and ¢ denote the number of nodes and the maximal degree in G , respectively. Finally, we prove that in geometric network graphs typically arising in wireless settings, the uniform problem can be ap- proximated within a constant factor in logarithmic time, whereas the non-uniform problem remains entirely non-local.
• Fabian Kuhn, Thomas Locher, Roger Wattenhofer
  Tight Bounds for Distributed Selection (SPAA Best Paper Award)
  2007 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego, California, USA
  » show abstract« hide abstract
  Abstract

  We revisit the problem of distributed k -selection where, given a general connected graph of diameter D consisting of n nodes in which each node holds a numeric element, the goal is to determine the k th smallest of these elements. In our model, there is no imposed relation between the magnitude of the stored elements and the number of nodes in the graph. We propose a randomized algorithm whose time complexity is O ( D log D n ) with high probability. Additionally, a de- terministic algorithm with a worst-case time complexity of O ( D log 2 D n ) is presented which considerably improves the best known bound for deterministic algorithms. Moreover, we prove a lower bound of ≠( D log D n ) for any randomized or deterministic algorithm, implying that the randomized algorithm is asymptotically optimal.

• Stefan Funke, Alex Kesselman, Fabian Kuhn, Zvi Lotker, Michael Segal
  Improved approximation algorithms for connected sensor cover
  2007 Wirel Netw, volume: 13, issue: 2, pages: 153 - 164
  » show abstract« hide abstract
  Abstract

  Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and it is infeasible to replenish energy via replacing batteries. An effective approach for energy conservation is scheduling sleep intervals for some sensors, while the remaining sensors stay active providing continuous service. In this paper we consider the problem of selecting a set of active sensors of minimum cardinality so that sensing coverage and network connectivity are maintained. We show that the greedy algorithm that provides complete coverage has an approximation factor no better than Ω(log n), where n is the number of sensor nodes. Then we present algorithms that provide approximate coverage while the number of nodes selected is a constant factor far from the optimal solution. Finally, we show how to connect a set of sensors that already provides coverage.

2006

• Fabian Kuhn, Roger Wattenhofer
  On the Complexity of Distributed Graph Coloring
  2006 25th ACM Symposium on Principles of Distributed Computing (PODC), Denver, Colorado, USA
• Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
  Fault-Tolerant Clustering in Ad Hoc and Sensor Networks
  2006 26th International Conference on Distributed Computing Systems (ICDCS), Lisbon, Portugal
• Fabian Kuhn, Stefan Schmid, Joest Smit, Roger Wattenhofer
  A Blueprint for Constructing Peer-to-Peer Systems Robust to Dynamic Worst-Case Joins and Leaves
  2006 14th IEEE International Workshop on Quality of Service (IWQoS), Yale University, New Haven, Connectitut, USA
• Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
  The Price of Being Near-Sighted
  2006 17th ACM-SIAM Symposium on Discrete Algorithms (SODA) Miami, Florida, USA

• Maurice Herlihy, Fabian Kuhn, Srikanta Tirthapura, Roger Wattenhofer
  Dynamic Analysis of the Arrow Distributed Protocol
  2006 Theor Comput Syst, volume: 39, issue: 6, pages: 875 - 901
  » show abstract« hide abstract
  Abstract

  Distributed queuing is a fundamental coordination problem that arises in a variety of applications, including distributed directories, totally ordered multicast, and distributed mutual exclusion. The arrow protocol is a solution to distributed queuing that is based on path reversal on a pre-selected spanning tree of the network. We present a novel and comprehensive competitive analysis of the arrow protocol. We consider the total cost of handling a finite number of queuing requests, which may or may not be issued concurrently, and show that the arrow protocol is O(s⋅logD)-competitive to the optimal queuing protocol, where s and D are the stretch and the diameter, respectively, of the spanning tree. In addition, we show that our analysis is almost tight by proving that for every spanning tree chosen for execution, the arrow protocol is Ω(s⋅log(D/s)/loglog(D/s))-competitive to the optimal queuing protocol. Our analysis reveals an intriguing connection between the arrow protocol and the nearest neighbor traveling salesperson tour on an appropriately defined graph.

• Hagit Attiya, Fabian Kuhn, C. Greg Plaxton, Mirjam Wattenhofer, Roger Wattenhofer
  Efficient adaptive collect using randomization
  2006 Distrib Comput, volume: 18, issue: 3, pages: 179 - 188
  » show abstract« hide abstract
  Abstract

  An adaptive algorithm, whose step complexity adjusts to the number of active processes, is attractive for distributed systems with a highly-variable number of processes. The cornerstone of many adaptive algorithms is an adaptive mechanism to collect up-to-date information from all participating processes. To date, all known collect algorithms either have non-linear step complexity or they are impractical because of unrealistic memory overhead. This paper presents new randomized collect algorithms with asymptotically optimal O(k) step complexity and linear memory overhead only. In addition we present a new deterministic collect algorithm that beats the best step complexity for previous polynomial-memory algorithms.

2005

• Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, Roger Wattenhofer
  Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs
  2005 19th International Symposium on Distributed Computing (DISC), Cracow, Poland
  » show abstract« hide abstract
  Abstract

  The distributed complexity of computing a maximal inde- pendent set in a graph is of both practical and theoretical importance. While there exists an elegant O (log n ) time randomized algorithm for general graphs [20], no deterministic polylogarithmic algorithm is known. In this paper, we study the problem in graphs with bounded growth, an important family of graphs which includes the well-known unit disk graph and many variants thereof. Particularly, we propose a deterministic algo- rithm that computes a maximal independent set in time O (log ¢ ¢ log § n ) in graphs with bounded growth, where n and ¢ denote the number of nodes and the maximal degree in G , respectively.
• Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, Roger Wattenhofer
  Local Approximation Schemes for Ad Hoc and Sensor Networks
  2005 3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, Germany
  » show abstract« hide abstract
  Abstract

  We present two local approaches that yield polynomial-time approximation schemes (PTAS) for the Maximum Indepen- dent Set and Minimum Dominating Set problem in unit disk graphs. The algorithms run locally in each node and com- pute a (1 + " )-approximation to the problems at hand for any given " > 0. The time complexity of both algorithms is O ( T MIS + log § n=" O (1) ), where T MIS is the time required to compute a maximal independent set in the graph, and n de- notes the number of nodes. We then extend these results to a more general class of graphs in which the maximum num- ber of pair-wise independent nodes in every r -neighborhood is at most polynomial in r . Such graphs of polynomially bounded growth are introduced as a more realistic model for wireless networks and they generalize existing models, such as unit disk graphs or coverage area graphs.
• Fabian Kuhn, Pascal von Rickenbach, Roger Wattenhofer, Emo Welzl, Aaron Zollinger
  Interference in Cellular Networks: The Minimum Membership Set Cover Problem
  2005 11th International Computing and Combinatorics Conference (COCOON), Kunming, Yunnan, China
  » show abstract« hide abstract
  Abstract

  The infrastructure for mobile distributed tasks is often formed by cel- lular networks. One of the major issues in such networks is interference. In this paper we tackle interference reduction by suitable assignment of transmission power levels to base stations. This task is formalized introducing the Minimum Membership Set Cover combinatorial optimization problem. On the one hand we prove that in polynomial time the optimal solution of the problem cannot be ap- proximated more closely than with a factor ln n . On the other hand we present an algorithm exploiting linear programming relaxation techniques which asymptot- ically matches this lower bound.
• Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
  On the Locality of Bounded Growth
  2005 24th ACM Symposium on the Principles of Distributed Computing (PODC), Las Vegas, Nevada, USA
  » show abstract« hide abstract
  Abstract

  Many large-scale networks such as ad hoc and sensor net- works, peer-to-peer networks, or the Internet have the prop- erty that the number of independent nodes does not grow arbitrarily when looking at neighborhoods of increasing size. Due to this bounded “volume growth,” one could expect that distributed algorithms are able to solve many problems more efficiently than on general graphs. The goal of this paper is to help understanding the distributed complexity of problems on “bounded growth” graphs. We show that on the widely used unit disk graph, covering and packing linear programs can be approximated by constant factors in con- stant time. For a more general network model which is based on the assumption that nodes are in a metric space of con- stant doubling dimension, we show that in O(log ∗ n ) rounds it is possible to construct a (O(1) , O(1))-network decompo- sition. This results in asymptotically optimal O(log ∗ n ) time algorithms for many important problems.
• Fabian Kuhn, Stefan Schmid, Roger Wattenhofer
  A Self-Repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn
  2005 4th International Workshop on Peer-To-Peer Systems (IPTPS), Cornell University, Ithaca, New York, USA
  » show abstract« hide abstract
  Abstract

  We present a dynamic distributed hash table where peers may join and leave at any time. Our system tolerates a powerful ad- versary which has complete visibility of the entire state of the system and can continuously add and remove peers. Our system provides worst- case fault-tolerance, maintaining desirable properties such as a low peer degree and a low network diameter.

• Fabian Kuhn, Roger Wattenhofer
  Constant-time distributed dominating set approximation
  2005 Distrib Comput, volume: 17, issue: 4, pages: 303 - 310
  » show abstract« hide abstract
  Abstract

  Finding a small dominating set is one of the most fundamental problems of classical graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary, possibly constant parameter k and maximum node degree Δ, our algorithm computes a dominating set of expected size O(kΔ2/klog(Δ)|DSOPT|) in O(k2) rounds. Each node has to send O(k2Δ) messages of size O(logΔ). This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds.

2004

• Hagit Attiya, Fabian Kuhn, Mirjam Wattenhofer, Roger Wattenhofer
  Efficient Adaptive Collect using Randomization (DISC Best Student Paper Award)
  2004 18th Annual Conference on Distributed Computing (DISC), Amsterdam, Netherlands
  » show abstract« hide abstract
  Abstract

  An adaptive algorithm, whose step complexity adjusts to the number of active processes, is attractive for distributed systems with a highly-variable number of processes. The cornerstone of many adaptive algorithms is an adaptive mechanism to collect up-to-date information from all participating processes. To date, all known collect algorithms either have non-linear step complexity or they are impractical because of unrealistic memory overhead. This paper presents new randomized collect algorithms with asymptotically op- timal O( k ) step complexity and polynomial memory overhead only. In addition we present a new deterministic collect algorithm which beats the best step com- plexity for previous polynomial-memory algorithms.
• Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
  Unit Disk Graph Approximation
  2004 ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Philadelphia, Pennsylvania, USA
  » show abstract« hide abstract
  Abstract

  Finding a good embedding of a unit disk graph given by its connectivity information is a problem of practical impor- tance in a variety of Øelds. In wireless ad hoc and sensor networks, such an embedding can be used to obtain virtual coordinates. In this paper, we prove a non-approximability result for the problem of embedding a given unit disk graph. Particularly, we show that if non-neighboring nodes are not allowed to be closer to each other than distance 1, then two neighbors can be as far apart as p 3 = 2 ° ≤ , where ≤ goes to 0 as n goes to inØnity, unless P = NP . We further show that Ønding a realization of a d -quasi unit disk graph with d ∏ 1 = p 2 is NP -hard.
• Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
  Initializing Newly Deployed Ad Hoc and Sensor Networks
  2004 10th Annual International Conference on Mobile Computing and Networking (MOBICOM), Philadelphia, Pennsylvania, USA
  » show abstract« hide abstract
  Abstract

  A newly deployed multi-hop radio network is unstructured and lacks a reliable and e±cient communication scheme. In this paper, we take a step towards analyzing the problems existing during the initialization phase of ad hoc and sensor networks. Particularly, we model the network as a multi- hop quasi unit disk graph and allow nodes to wake up asyn- chronously at any time. Further, nodes do not feature a reliable collision detection mechanism, and they have only limited knowledge about the network topology. We show that even for this restricted model, a good clustering can be computed e±ciently. Our algorithm e±ciently computes an asymptotically optimal clustering. Based on this algorithm, we describe a protocol for quickly establishing synchronized sleep and listen schedule between nodes within a cluster. Additionally, we provide simulation results in a variety of settings.
• Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
  Radio Network Clustering from Scratch
  2004 12nd Annual European Symposium on Algorithms (ESA), Bergen, Norway
  » show abstract« hide abstract
  Abstract

  We propose a novel randomized algorithm for computing a dominat- ing set based clustering in wireless ad-hoc and sensor networks. The algorithm works under a model which captures the characteristics of the set-up phase of such multi-hop radio networks: asynchronous wake-up, the hidden terminal prob- lem, and scarce knowledge about the topology of the network graph. When mod- elling the network as a unit disk graph, the algorithm computes a dominating set in polylogarithmic time and achieves a constant approximation ratio.
• Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
  What Cannot Be Computed Locally! (PODC Best Student Paper Award)
  2004 23rd ACM Symposium on the Principles of Distributed Computing (PODC), St. John's, Newfoundland, Canada
• Fabian Kuhn, Roger Wattenhofer
  Dynamic Analysis of the Arrow Distributed Protocol
  2004 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Barcelona, Spain
  » show abstract« hide abstract
  Abstract

  Arro w is a prominen t distributed proto col whic h globally orders requests initiated by the nodes in a distributed sys- tem. In this pap er we presen t a dynamic analysis of the Ar- row proto col. We pro ve that Arro w is O (log D )-comp etitiv e, where D is the diameter of the spanning tree on whic h Arro w operates. In addition, we sho w that our analysis is almost tigh t by pro ving that for all trees the comp etitiv e ratio of Arro w is (log D= log log D ).

2003

• Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
  Ad-Hoc Networks Beyond Unit Disk Graphs
  2003 1st ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), San Diego, California, USA
• Fabian Kuhn, Roger Wattenhofer
  Constant-Time Distributed Dominating Set Approximation (PODC Best Student Paper Award)
  2003 22nd ACM Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA
• Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Aaron Zollinger
  Geometric Ad-Hoc Routing: Of Theory and Practice
  2003 22nd ACM Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA
• Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
  Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing
  2003 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), Annapolis, Maryland, USA

2002

• Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
  Asymptotically Optimal Geometric Mobile Ad-Hoc Routing
  2002 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), Atlanta, Georgia, USA

2001

• Fabian Kuhn, René Struik
  Random Walks Revisited: Extensions of Pollard’s Rho Algorithm for Computing Multiple Discrete Logarithms
  2001 8th Annual Workshop on Selected Areas in Cryptography (SAC), Toronto, Ontario, Canada
  » show abstract« hide abstract
  Abstract

  This paper extends the analysis of Pollard’s rho algorithm for solving a single instance of the discrete logarithm problem in a finite cyclic group G to the case of solving more than one instance of the discrete logarithm problem in the same group G . We analyze Pollard’s rho algorithm when used to iteratively solve all the instances. We also analyze the situation when the goal is to solve any one of the multiple instances using any DLP algorithm.