Paper Info
Title
Efficient distributed source detection with limited bandwidth
Abstract
Given a simple graph G=(V,E) and a set of sources S ⊆ V, denote for each node ν ε V by Lν(∞) the lexicographically ordered list of distance/source pairs (d(s,v),s), where s ∈ S. For integers d,k ∈ N∪{∞}, we consider the source detection, or (S,d,k)-detection task, requiring each node v to learn the first k entries of Lν(∞) (if for all of them d(s,v) ≤ d) or all entries (d(s,v),s) ∈ Lν(∞) satisfying that d(s,v) ≤ d (otherwise). Solutions to this problem provide natural generalizations of concurrent breadth-first search (BFS) tree constructions. For example, the special case of k=∞ requires each source s ∈ S to build a complete BFS tree rooted at s, whereas the special case of d=∞ and S=V requires constructing a partial BFS tree comprising at least k nodes from every node in V. In this work, we give a simple, near-optimal solution for the source detection task in the CONGEST model, where messages contain at most O(log n) bits, running in d+k rounds. We demonstrate its utility for various routing problems, exact and approximate diameter computation, and spanner construction. For those problems, we obtain algorithms in the CONGEST model that are faster and in some cases much simpler than previous solutions.
Year
DOI
Venue
2013
10.1145/2484239.2484262
PODC
Keywords
Field
DocType
detection task,special case,source pair,source detection task,congest model,k entry,k round,k node,complete bfs tree,source detection,limited bandwidth,algorithms
Integer,Binary logarithm,Combinatorics,Generalization,Theoretical computer science,Bandwidth (signal processing),Lexicographical order,Spanner,Mathematics,Special case,Computation,Distributed computing
Conference
Citations 
PageRank 
References 
34
1.00
22
Authors
2
Name
Order
Citations
PageRank
Christoph Lenzen158440.61
David Peleg26662824.19