School of Computing

Permanent URI for this community

https://dl.comp.nus.edu.sg/handle/1900.100/1

Browse

Browsing School of Computing by Subject "lower bounds"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    The Cost of Unknown Diameter in Dynamic Networks *
    (2016-04-25) YU, Haifeng; ZHAO, Yuda; JAHJA, Irvan
    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.