10.1007/978-3-319-03850-6_2
Abshoff, Sebastian
Sebastian
Abshoff
Benter, Markus
Markus
Benter
Malatyali, Manuel
Manuel
Malatyali
Meyer auf der Heide, Friedhelm
Friedhelm
Meyer auf der Heide
On Two-Party Communication Through Dynamic Networks
2013
2017-10-17T12:42:31Z
2019-01-03T13:16:42Z
conference
https://ris.uni-paderborn.de/record/507
https://ris.uni-paderborn.de/record/507.json
181398 bytes
application/pdf
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.