The Cost of Unknown Diameter in Dynamic Networks *
No Thumbnail Available
Date
2016-04-25
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
For dynamic networks with unknown diameter, we prove novel lower bounds on the time complexity of a range of basic distributed computing problems. Together with trivial upper bounds under dynamic networks with known diameter for these problems, our lower bounds show that the complexitiesof all these problems are sensitive to whether the diameter is known to the protocol beforehand: Not knowing the diameter increases the time complexities by a large
poly(N) factor as compared to when the diameter is known, resulting in an exponential gap. Our lower bounds are obtained via communication complexity arguments and by reducing from the two-party DisjointnessCP problem. We further prove that sometimes this large poly(N) cost can be completely avoided if the protocol is given a good estimate on N. In other words, having such an estimate makes some problems no longer sensitive to unknown diameter.
Description
Keywords
unknown network diameter, dynamic networks, communication complexity, lower bounds