On Two-Party Communication Through Dynamic Networks

S. Abshoff, M. Benter, M. Malatyali, F. Meyer auf der Heide, in: Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS), 2013, pp. 11–22.

Download
Restricted 507-on-two-party-communication-through-dynamic-networks_01.pdf 181.40 KB
Conference Paper
Author
; ; ;
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.
Publishing Year
Proceedings Title
Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS)
Page
11-22
LibreCat-ID

Cite this

Abshoff S, Benter M, Malatyali M, Meyer auf der Heide F. On Two-Party Communication Through Dynamic Networks. In: Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS). LNCS. ; 2013:11-22. doi:10.1007/978-3-319-03850-6_2
Abshoff, S., Benter, M., Malatyali, M., & Meyer auf der Heide, F. (2013). On Two-Party Communication Through Dynamic Networks. In Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS) (pp. 11–22). https://doi.org/10.1007/978-3-319-03850-6_2
@inproceedings{Abshoff_Benter_Malatyali_Meyer auf der Heide_2013, series={LNCS}, title={On Two-Party Communication Through Dynamic Networks}, DOI={10.1007/978-3-319-03850-6_2}, booktitle={Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS)}, author={Abshoff, Sebastian and Benter, Markus and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2013}, pages={11–22}, collection={LNCS} }
Abshoff, Sebastian, Markus Benter, Manuel Malatyali, and Friedhelm Meyer auf der Heide. “On Two-Party Communication Through Dynamic Networks.” In Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS), 11–22. LNCS, 2013. https://doi.org/10.1007/978-3-319-03850-6_2.
S. Abshoff, M. Benter, M. Malatyali, and F. Meyer auf der Heide, “On Two-Party Communication Through Dynamic Networks,” in Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS), 2013, pp. 11–22.
Abshoff, Sebastian, et al. “On Two-Party Communication Through Dynamic Networks.” Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS), 2013, pp. 11–22, doi:10.1007/978-3-319-03850-6_2.
Main File(s)
File Name
507-on-two-party-communication-through-dynamic-networks_01.pdf 181.40 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-15T10:47:31Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar