1,720,982 research outputs found
Distributed tree comparison with nodes of limited memory
No full textWe consider the task of comparing two rooted trees with port labels. Roots of the trees are joined by an edge and the comparison has to be performed distributedly, by exchanging messages among nodes. If the two trees are isomorphic, all nodes must finish in a state YES; otherwise they have to finish in a state NO and break symmetry, nodes of one tree getting label 0 and nodes of the other getting label 1. Nodes are modeled as identical automata, and our goal is to establish trade-offs between the memory size of such an automaton and the efficiency of distributed tree comparison, measured either by the time or by the number of messages used for communication between nodes. We consider both the synchronous and the asynchronous communication and establish exact trade-offs in both scenarios. For the synchronous scenario, we are concerned with memory versus time trade-offs. We show that if the automaton has x bits of memory, where x ≥ c log n, for a small constant c, then the optimal time to accomplish the comparison task in the class of trees of size at most n and of height at most h > 1 is θ(h + n/x). For the asynchronous scenario, we study memory versus number of messages trade-offs. We show that if the automaton has x bits of memory, where n ≥ x ≥ c log n, then the optimal number of messages to accomplish the comparison task in the class of trees of size at most n is θ(n 2/x)
Broadcasting in UDG Radio Networks with Missing and Inaccurate Information
No full textWe study broadcasting time in radio networks, modeled as unit disk graphs (UDG). Emek et al. showed that broadcasting time depends on two parameters of the UDG network, namely, its diameter D (in hops) and its granularity g. The latter is the inverse of the density d of the network which is the minimum Euclidean distance between any two stations. They proved that the minimum broadcasting time is Θ(min {D + g2, D log g}), assuming that each node knows the density of the network and knows exactly its own position in the plane. In many situations these assumptions are unrealistic. Does removing them influence broadcasting time? The aim of this paper is to answer this question, hence we assume that density is unknown and nodes perceive their position with some unknown error margin ε. It turns out that this combination of missing and inaccurate information substantially changes the problem: the main new challenge becomes fast broadcasting in sparse networks (with constant density), when optimal time is O(D). Nevertheless, under our very weak scenario, we construct a broadcasting algorithm that maintains optimal time O(min {D + g2, D log g}) for all networks with at least 2 nodes, of diameter D and granularity g, if each node perceives its position with error margin ε = αd, for any (unknown) constant α < 1/2. Rather surprisingly, the minimum time of an algorithm stopping if the source is alone, turns out to be Θ(D + g2). Thus, the mere stopping requirement for the special case of the lonely source causes an exponential increase in broadcasting time, for networks of any density and any small diameter. Finally, broadcasting is impossible if ε ≥ d/2. © 2008 Springer-Verlag Berlin Heidelberg
Acknowledged broadcasting in ad hoc radio networks
No full textWe consider ad hoc radio networks in which each node knows only its own identity but is unaware of the topology of the network, or of any bound on its size or diameter. Acknowledged broadcasting (AB) is a communication task consisting in transmitting a message from a distinguished source to all other nodes of the network and making this fact common knowledge among all nodes. To do this, the underlying directed graph must be strongly connected. Working in a model allowing all nodes to transmit spontaneously even before getting the Source message, Chlebus et al. [B. Chlebus. L. Gasieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks. Distrib. Comput. 15 (2002) 27-38] proved that AB is impossible, if collision detection is not available, and gave an AB algorithm using collision detection that works in time O(nD) where n is the number of nodes and D is the eccentricity of the source. Uchida et al. U. Uchida, W. Chen, K. Wada, Acknowledged broadcasting and gossiping in ad hoc radio networks, Theoret. Comput. Sci. 377 (2007) 43-54] showed an AB algorithm without collision detection working in time O (n(4/3) log(10/3) n) for all strongly connected networks of size at least 2. In particular, it follows that the impossibility result from [B. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] is really caused by the singleton network for which AB amounts to realize that the source is alone. We improve those two results by presenting two generic AB algorithms using a broadcasting algorithm without acknowledgement, as a procedure. For a large class of broadcasting algorithms the resulting AB algorithm has the same time complexity. Using the Currently best known broadcasting algorithms, we obtain an AB algorithm with collision detection working in time O(min{nlog(2)D, nlognloglogn}), for arbitrary strongly connected networks, and an AB algorithm without collision detection working in time O(nlognloglogn) for all strongly connected networks of size n >= 2. Moreover, we show that in the model in which only nodes that already got the source message can transmit, AB is infeasible in a strong sense: for any AB algorithm there exists an infinite family of networks for which this algorithm is incorrect. (C) 2008 Elsevier B.V. All rights reserved
Broadcasting in UDG radio networks with missing and inaccurate information
No full textWe study broadcasting time in radio networks, modeled as unit disk graphs (UDG). Network stations are represented by points in the plane and a station is connected to all stations at distance at most 1 from it. Stations are unaware of the network topology. Each station can send messages from the beginning of the broadcasting process, even before getting the source message. Emek et al. showed that broadcasting time depends on two parameters of the UDG network, namely, its diameter D (in hops) and its granularity g. The latter is the inverse of the density d of the network which is the minimum Euclidean distance between any two stations. They proved that the minimum broadcasting time is Θ(min {D + g 2, D log g}), assuming that each node knows the density of the network and knows exactly its own position in the plane. In many situations these assumptions are unrealistic. Does removing them influence broadcasting time? The aim of this paper is to answer this question, hence we assume that density is unknown and nodes perceive their position with some unknown error margin e. It turns out that this combination of missing and inaccurate information substantially changes the problem: the main new challenge becomes fast broadcasting in sparse networks (with constant density), when optimal time is O(D). Nevertheless, under our very weak scenario, we construct a broadcasting algorithm that maintains optimal time O (min {D + g 2, D log g}) for all networks with at least 2 nodes, of diameter D and granularity g (previously obtained with exact positions and known density), if each node perceives its position with error margin e=α, for any (unknown) constant α < 1/2. Rather surprisingly, the minimum time of an algorithm working correctly for all networks, and hence stopping if the source is alone, turns out to be Θ(D + g 2). Thus, the mere stopping requirement for the special case of the lonely source causes an exponential increase in broadcasting time, for networks of any density and any small diameter. Finally, if e ≥ d/2}, then broadcasting is impossible. © 2010 Springer-Verlag
On the number of labeled k-arch graphs
No full textIn this paper we deal with k-arch graphs, a superclass of trees and k-trees. We give a recursive function counting the number of labeled k-arch graphs. Our result relies on a generalization of the well-known Prüfer code for labeled trees. In order to guarantee the generalized code to be a bijection, we characterize the valid code strings. A previous attempt at counting the number of labeled k-arch graphs was made by Lamathe. We point out an error in his work, and prove it by giving a counterexample
Clique counting in MapReduce: Algorithms and experiments
No full textWe tackle the problem of counting the number qk of k-cliques in large-scale graphs, for any constant k ≥ 3.
Clique counting is essential in a variety of applications, including social network analysis. Our algorithms
make it possible to compute qk for several real-world graphs and shed light on its growth rate as a function
of k. Even for small values of k, the number qk of k-cliques can be in the order of tens or hundreds of trillions.
As k increases, different graph instances show different behaviors: while on some graphs qk+1 < qk, on other
benchmarks qk+1 qk, up to two orders of magnitude in our observations. Graphs with steep clique growth
rates represent particularly tough instances in practice.
Due to the computationally intensive nature of the clique counting problem, we settle for parallel solutions
in the MapReduce framework, which has become in the last few years a de facto standard for batch processing
of massive datasets. We give both theoretical and experimental contributions.
On the theory side, we design the first exact scalable algorithm for counting (and listing) k-cliques in
MapReduce. Our algorithm uses O(m3/2) total space and O(mk/2) work, where m is the number of graph
edges. This matches the best-known bounds for triangle listing when k = 3 and is work optimal in the
worst case for any k, while keeping the communication cost independent of k. We also design sampling-based
estimators that can dramatically reduce the running time and space requirements of the exact approach,
while providing very accurate solutions with high probability.
We then assess the effectiveness of different clique counting approaches through an extensive experimental
analysis over the Amazon EC2 platform, considering both our algorithms and their state-of-the-art competitors. The experimental results clearly highlight the algorithm of choice in different scenarios and prove our
exact approach to be the most effective when the number of k-cliques is large, gracefully scaling to nontrivial
values of k even on clusters of small/medium size. Our approximation algorithms achieve extremely accurate
estimates and large speedups, especially on the toughest instances for the exact algorithm
Bijective Linear Time Coding and Decoding for k-Trees
No full textThe problem of coding labeled trees has been widely studied in the literature and several bijective codes that realize associations between labeled trees and sequences of labels have been presented. k-trees are one of the most natural and interesting generalizations of trees and there is considerable interest in developing efficient tools to manipulate this class of graphs, since many NP-Complete problems have been shown to be polynomially solvable on k-trees and partial k-trees. In 1970 R,nyi and R,nyi generalized the Prufer code, the first bijective code for trees, to a subset of labeled k-trees. Subsequently, non redundant codes that realize bijection between k-trees (or R,nyi k-trees) and a well defined set of strings were produced. In this paper we introduce a new bijective code for labeled k-trees which, to the best of our knowledge, produces the first coding and decoding algorithms running in linear time with respect to the size of the k-tree
Distributed tree comparison with nodes of limited memory
No full textWe consider the task of comparing two rooted trees with port labelings. Roots of the trees are joined by an edge and the comparison has to be carried out distributedly, by exchanging messages among nodes. If the two trees are isomorphic, all nodes must finish in a state YES, otherwise they have to finish in a state NO and break symmetry, nodes of one tree getting label 0 and of the other - label 1. Nodes are modeled as identical automata, and our goal is to establish trade-offs between the memory size of such an automaton and the efficiency of distributed tree comparison, measured either by the time or by the number of messages used for communication between nodes. We consider both the synchronous and the asynchronous communication and establish exact trade-offs in both scenarios. For the synchronous scenario we are concerned with memory vs. time trade-offs. We show that if the automaton has x bits of memory, where x ≤ c log n, for a small constant c, then the optimal time to accomplish the comparison task in the class of trees of size at most n and of height at most h < 1 is Θ(max (h,n/x)). For the asynchronous scenario we study memory vs. number of messages trade-offs. We show that if the automaton has x bits of memory, where n ≤ x ≤ c log Δ, then the optimal number of messages to accomplish the comparison task in the class of trees of size at most n and of maximum degree at most Δ is Θ(n2/x)
- …
