{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:06Z","timestamp":1750221006159,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T00:00:00Z","timestamp":1553558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["W1260-N35"],"award-info":[{"award-number":["W1260-N35"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["340506"],"award-info":[{"award-number":["340506"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,3,26]]},"abstract":"<jats:p>Modern networked systems are increasingly reconfigurable, enabling demand-aware infrastructures whose resources can be adjusted according to the workload they currently serve. Such dynamic adjustments can be exploited to improve network utilization and hence performance, by moving frequently interacting communication partners closer, e.g., collocating them in the same server or datacenter. However, dynamically changing the embedding of workloads is algorithmically challenging: communication patterns are often not known ahead of time, but must be learned. During the learning process, overheads related to unnecessary moves (i.e., re-embeddings) should be minimized. This paper studies a fundamental model which captures the tradeoff between the benefits and costs of dynamically collocating communication partners on $\\ell$ servers, in an online manner. Our main contribution is a distributed online algorithm which is asymptotically almost optimal, i.e., almost matches the lower bound (also derived in this paper) on the competitive ratio of any (distributed or centralized) online algorithm. As an application, we show that our algorithm can be used to solve a distributed union find problem in which the sets are stored across multiple servers.<\/jats:p>","DOI":"10.1145\/3322205.3311084","type":"journal-article","created":{"date-parts":[[2020,3,26]],"date-time":"2020-03-26T13:12:37Z","timestamp":1585228357000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Distributed Workload (Re-)Embedding"],"prefix":"10.1145","volume":"3","author":[{"given":"Monika","family":"Henzinger","sequence":"first","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Neumann","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.31219\/osf.io\/6qzxc"},{"key":"e_1_2_1_2_1","first-page":"583","article-title":"Scaling distributed machine learning with the parameter server","volume":"14","author":"Li M.","year":"2014","unstructured":"M. Li , D. G. Andersen , J. W. Park , A. J. Smola , A. Ahmed , V. Josifovski , J. Long , E. J. Shekita , and B. Su , \u201c Scaling distributed machine learning with the parameter server .,\u201d in Proc. USENIX OSDI , vol. 14 , pp. 583 -- 598 , 2014 . M. Li, D. G. Andersen, J. W. Park, A. J. Smola, A. Ahmed, V. Josifovski, J. Long, E. J. Shekita, and B. Su, \u201cScaling distributed machine learning with the parameter server.,\u201d in Proc. USENIX OSDI, vol. 14, pp. 583--598, 2014.","journal-title":"Proc. USENIX OSDI"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2378956.2378964"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3310165.3310170"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934911"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785956.2787472"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879175"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_18"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3184400"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/364099.364331"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(97)00031-7"},{"key":"e_1_2_1_14_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman , 1979 . M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7535"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01383882"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486012"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486019"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486026"},{"key":"e_1_2_1_20_1","first-page":"523","volume-title":"Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI)","author":"Eisenbud D. E.","year":"2016","unstructured":"D. E. Eisenbud , C. Yi , C. Contavalli , C. Smith , R. Kononov , E. Mann-Hielscher , A. Cilingiroglu , B. Cheyney , W. Shang , and J. D. Hosein , \u201c Maglev: A fast and reliable software network load balancer .,\u201d in Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI) , pp. 523 -- 535 , 2016 . D. E. Eisenbud, C. Yi, C. Contavalli, C. Smith, R. Kononov, E. Mann-Hielscher, A. Cilingiroglu, B. Cheyney, W. Shang, and J. D. Hosein, \u201cMaglev: A fast and reliable software network load balancer.,\u201d in Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI), pp. 523--535, 2016."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1672308.1672333"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2591204.2591215"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656877.2656890"},{"key":"e_1_2_1_24_1","volume-title":"Smartnic: Accelerating azure's network with fpgas on ocs servers","author":"Firestone D.","year":"2016","unstructured":"D. Firestone , \u201c Smartnic: Accelerating azure's network with fpgas on ocs servers ,\u201d https:\/\/ocpussummit 2016 .sched.com\/event\/68u4\/, 2016. D. Firestone, \u201cSmartnic: Accelerating azure's network with fpgas on ocs servers,\u201d https:\/\/ocpussummit2016.sched.com\/event\/68u4\/, 2016."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2016.7524466"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2829988.2787508"},{"volume-title":"White Paper","year":"2015","key":"e_1_2_1_27_1","unstructured":"Cisco , \u201c Cisco global cloud index: Forecast and methodology, 2015--2020 ,\u201d White Paper , 2015 . Cisco, \u201cCisco global cloud index: Forecast and methodology, 2015--2020,\u201d White Paper, 2015."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851275.1851192"},{"key":"e_1_2_1_29_1","first-page":"145","volume-title":"Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI)","author":"Judd G.","year":"2015","unstructured":"G. Judd , \u201c Attaining the promise and avoiding the pitfalls of tcp in the datacenter .,\u201d in Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI) , pp. 145 -- 157 , 2015 . G. Judd, \u201cAttaining the promise and avoiding the pitfalls of tcp in the datacenter.,\u201d in Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI), pp. 145--157, 2015."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740070.2626328"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/314161.314178"},{"key":"e_1_2_1_32_1","volume-title":"Competitive algorithms for replication and migration problems","author":"Black D. L.","year":"1989","unstructured":"D. L. Black and D. D. Sleator , \u201c Competitive algorithms for replication and migration problems ,\u201d 1989 . D. L. Black and D. D. Sleator, \u201cCompetitive algorithms for replication and migration problems,\u201d 1989."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/2591204.2591215"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80060-1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28435"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.015"},{"key":"e_1_2_1_38_1","first-page":"241","volume-title":"Proc. of the2ndACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"Young N. E.","year":"1991","unstructured":"N. E. Young , \u201c On-line caching as cache size varies ,\u201d in Proc. of the2ndACM-SIAM Symp. on Discrete Algorithms (SODA) , pp. 241 -- 250 , 1991 . N. E. Young, \u201cOn-line caching as cache size varies,\u201d in Proc. of the2ndACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 241--250, 1991."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095249"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9793-0"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2523616.2525943"},{"issue":"177","key":"e_1_2_1_42_1","first-page":"1","article-title":"Community detection and stochastic block models: Recent developments","volume":"18","author":"Abbe E.","year":"2018","unstructured":"E. Abbe , \u201c Community detection and stochastic block models: Recent developments ,\u201d Journal of Machine Learning Research , vol. 18 , no. 177 , pp. 1 -- 86 , 2018 . E. Abbe, \u201cCommunity detection and stochastic block models: Recent developments,\u201d Journal of Machine Learning Research, vol. 18, no. 177, pp. 1--86, 2018.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701387660"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1350-7"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/050640904"},{"key":"e_1_2_1_46_1","first-page":"211","volume-title":"SODA","volume":"98","author":"Rao S.","year":"1998","unstructured":"S. Rao and A. W. Richa , \u201c New approximation techniques for some ordering problems .,\u201d in SODA , vol. 98 , pp. 211 -- 219 , 1998 . S. Rao and A. W. Richa, \u201cNew approximation techniques for some ordering problems.,\u201d in SODA, vol. 98, pp. 211--219, 1998."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1355734.1355737"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04693-4_19"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103458"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868249"},{"key":"e_1_2_1_51_1","first-page":"186","volume-title":"PPAM","author":"Manne F.","year":"2009","unstructured":"F. Manne and M. M. A. Patwary , \u201cA scalable parallel union-find algorithm for distributed memory computers ,\u201d in PPAM , pp. 186 -- 195 , 2009 . F. Manne and M. M. A. Patwary, \u201cA scalable parallel union-find algorithm for distributed memory computers,\u201d in PPAM, pp. 186--195, 2009."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_35"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.79"},{"key":"e_1_2_1_54_1","first-page":"538","volume-title":"IJCAI","author":"Korf R. E.","year":"2009","unstructured":"R. E. Korf , \u201c Multi-way number partitioning ,\u201d in IJCAI , pp. 538 -- 543 , 2009 . R. E. Korf, \u201cMulti-way number partitioning,\u201d in IJCAI, pp. 538--543, 2009."},{"key":"e_1_2_1_55_1","article-title":"Dynamic balanced graph partitioning","author":"Avin C.","year":"2019","unstructured":"C. Avin , M. Bienkowski , A. Loukas , M. Pacut , and S. Schmid , \u201c Dynamic balanced graph partitioning ,\u201d in SIAM J. Discrete Math (SIDMA) , 2019 . C. Avin, M. Bienkowski, A. Loukas, M. Pacut, and S. Schmid, \u201cDynamic balanced graph partitioning,\u201d in SIAM J. Discrete Math (SIDMA), 2019.","journal-title":"SIAM J. Discrete Math (SIDMA)"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311084","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322205.3311084","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:54Z","timestamp":1750206354000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311084"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,26]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,26]]}},"alternative-id":["10.1145\/3322205.3311084"],"URL":"https:\/\/doi.org\/10.1145\/3322205.3311084","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2019,3,26]]},"assertion":[{"value":"2019-03-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}