---
res:
bibo_abstract:
- We study two-party communication in the context of directed dynamic networks that
are controlled by an adaptive adversary. This adversary is able to change all
edges as long as the networks stay strongly-connected in each round. In this work,
we establish a relation between counting the total number of nodes in the network
and the problem of exchanging tokens between two communication partners which
communicate through a dynamic network. We show that the communication problem
for a constant fraction of n tokens in a dynamic network with n nodes is at most
as hard as counting the number of nodes in a dynamic network with at most 4n+3
nodes. For the proof, we construct a family of directed dynamic networks and apply
a lower bound from two-party communication complexity.
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sebastian
foaf_name: Abshoff, Sebastian
foaf_surname: Abshoff
- foaf_Person:
foaf_givenName: Markus
foaf_name: Benter, Markus
foaf_surname: Benter
- foaf_Person:
foaf_givenName: Manuel
foaf_name: Malatyali, Manuel
foaf_surname: Malatyali
- foaf_Person:
foaf_givenName: Friedhelm
foaf_name: Meyer auf der Heide, Friedhelm
foaf_surname: Meyer auf der Heide
foaf_workInfoHomepage: http://www.librecat.org/personId=15523
bibo_doi: 10.1007/978-3-319-03850-6_2
dct_date: 2013^xs_gYear
dct_title: On Two-Party Communication Through Dynamic Networks@
...