On the Power of Preprocessing in Decentralized Network Optimization

Klaus Tycho Foerster, Juho Hirvonen, Stefan Schmid, Jukka Suomela

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

8 Sitaatiot (Scopus)


As communication networks are growing at a fast pace, the need for more scalable approaches to operate such networks is pressing. Decentralization and locality are key concepts to provide scalability. Existing models for which local algorithms are designed fail to model an important aspect of many modern communication networks such as software-defined networks: the possibility to precompute distributed network state. We take this as an opportunity to study the fundamental question of how and to what extent local algorithms can benefit from preprocessing. In particular, we show that preprocessing allows for significant speedups of various networking problems. A main benefit is the precomputation of structural primitives, where purely distributed algorithms have to start from scratch. Maybe surprisingly, we also show that there are strict limitations on how much preprocessing can help in different scenarios. To this end, we provide approximation bounds for the maximum independent set problem - which however show that our obtained speedups are asymptotically optimal. Even though we show that physical link failures in general hinder the power of preprocessing, we can still facilitate the precomputation of symmetry breaking processes to bypass various runtime barriers. We believe that our model and results are of interest beyond the scope of this paper and apply to other dynamic networks as well.

OtsikkoINFOCOM 2019 - IEEE Conference on Computer Communications
ISBN (elektroninen)9781728105154
DOI - pysyväislinkit
TilaJulkaistu - 1 huhtik. 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaIEEE Conference on Computer Communications - Paris, Ranska
Kesto: 29 huhtik. 20192 toukok. 2019
Konferenssinumero: 38


NimiProceedings - IEEE INFOCOM
ISSN (painettu)0743-166X


ConferenceIEEE Conference on Computer Communications


Sukella tutkimusaiheisiin 'On the Power of Preprocessing in Decentralized Network Optimization'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä