Does preprocessing help under congestion?

K.-T. Foerster, J. Korhonen, J. Rybicki, S. Schmid, in:, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, ACM, 2019, pp. 259–261.


Conference Paper | Published | English
Author
; ; ;
Department
Abstract
This paper investigates the power of preprocessing in the CONGEST model. Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to study the application of distributed algorithms in Software-Defined Networks (SDNs). In this paper, we show that a large class of lower bounds in the CONGEST model still hold in the SUPPORTED model, highlighting the robustness of these bounds. This also raises the question how much does preprocessing help in the CONGEST model.
Publishing Year
Date Published
2019-08-01
Proceedings Title
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
Page
259-261
Conference
PODC: Symposium on Principles of Distributed Computing
Conference Location
Toronto, ON, Canada
Conference Date
2019-07-29 – 2019-08-02
IST-REx-ID

Cite this

Foerster K-T, Korhonen J, Rybicki J, Schmid S. Does preprocessing help under congestion? In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. ACM; 2019:259-261. doi:10.1145/3293611.3331581
Foerster, K.-T., Korhonen, J., Rybicki, J., & Schmid, S. (2019). Does preprocessing help under congestion? In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (pp. 259–261). Toronto, ON, Canada: ACM. https://doi.org/10.1145/3293611.3331581
Foerster, Klaus-Tycho, Janne Korhonen, Joel Rybicki, and Stefan Schmid. “Does Preprocessing Help under Congestion?” In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 259–61. ACM, 2019. https://doi.org/10.1145/3293611.3331581.
K.-T. Foerster, J. Korhonen, J. Rybicki, and S. Schmid, “Does preprocessing help under congestion?,” in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, Toronto, ON, Canada, 2019, pp. 259–261.
Foerster K-T, Korhonen J, Rybicki J, Schmid S. 2019. Does preprocessing help under congestion? Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing 259–261.
Foerster, Klaus-Tycho, et al. “Does Preprocessing Help under Congestion?” Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, ACM, 2019, pp. 259–61, doi:10.1145/3293611.3331581.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1905.03012

Search this title in

Google Scholar
ISBN Search