License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.29
URN: urn:nbn:de:0030-drops-79690
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7969/
Go to the corresponding LIPIcs Volume Portal

Jahja, Irvan ; Yu, Haifeng ; Zhao, Yuda

Some Lower Bounds in Dynamic Networks with Oblivious Adversaries

pdf-format:
LIPIcs-DISC-2017-29.pdf (0.7 MB)

Abstract

This paper considers several closely-related problems in synchronous dynamic networks with oblivious adversaries, and proves novel Omega(d + poly(m)) lower bounds on their time complexity (in rounds). Here d is the dynamic diameter of the dynamic network and m is the total number of nodes. Before this work, the only known lower bounds on these problems under oblivious adversaries were the trivial Omega(d) lower bounds. Our novel lower bounds are hence the first non-trivial lower bounds and also the first lower bounds with a poly(m) term. Our proof relies on a novel reduction from a certain two-party communication complexity problem. Our central proof technique is unique in the sense that we consider the communication complexity with a special leaker. The leaker helps Alice and Bob in the two-party problem, by disclosing to Alice and Bob certain "non-critical" information about the problem instance that they are solving.

BibTeX - Entry

@InProceedings{jahja_et_al:LIPIcs:2017:7969,
  author =	{Irvan Jahja and Haifeng Yu and Yuda Zhao},
  title =	{{Some Lower Bounds in Dynamic Networks with Oblivious Adversaries}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7969},
  URN =		{urn:nbn:de:0030-drops-79690},
  doi =		{10.4230/LIPIcs.DISC.2017.29},
  annote =	{Keywords: dynamic networks, oblivious adversary, adaptive adversary, lower bounds, communication complexity}
}

Keywords: dynamic networks, oblivious adversary, adaptive adversary, lower bounds, communication complexity
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI