DSpace Repository

The Cost of Unknown Diameter in Dynamic Networks *

Show simple item record

dc.contributor.author YU, Haifeng en_US
dc.contributor.author ZHAO, Yuda en_US
dc.contributor.author JAHJA, Irvan en_US
dc.date.accessioned 2016-04-29T08:22:37Z en_US
dc.date.accessioned 2017-01-23T06:59:41Z
dc.date.available 2016-04-29T08:22:37Z en_US
dc.date.available 2017-01-23T06:59:41Z
dc.date.issued 2016-04-25 en_US
dc.identifier.uri http://hdl.handle.net/1900.100/5439 en_US
dc.description.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. en_US
dc.language.iso en en_US
dc.relation.ispartofseries ;TRA4/16 en_US
dc.subject unknown network diameter en_US
dc.subject dynamic networks en_US
dc.subject communication complexity en_US
dc.subject lower bounds en_US
dc.title The Cost of Unknown Diameter in Dynamic Networks * en_US
dc.type Technical Report en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


My Account