The Cost of Unknown Diameter in Dynamic Networks *

dc.contributor.authorYU, Haifengen_US
dc.contributor.authorZHAO, Yudaen_US
dc.contributor.authorJAHJA, Irvanen_US
dc.date.accessioned2016-04-29T08:22:37Zen_US
dc.date.accessioned2017-01-23T06:59:41Z
dc.date.available2016-04-29T08:22:37Zen_US
dc.date.available2017-01-23T06:59:41Z
dc.date.issued2016-04-25en_US
dc.description.abstractFor 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.en_US
dc.identifier.urihttps://dl.comp.nus.edu.sg/xmlui/handle/1900.100/5439en_US
dc.language.isoenen_US
dc.relation.ispartofseries;TRA4/16en_US
dc.subjectunknown network diameteren_US
dc.subjectdynamic networksen_US
dc.subjectcommunication complexityen_US
dc.subjectlower boundsen_US
dc.titleThe Cost of Unknown Diameter in Dynamic Networks *en_US
dc.typeTechnical Reporten_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
TRA4-16.pdf
Size:
428.64 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.53 KB
Format:
Plain Text
Description: