{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:10Z","timestamp":1750220650418,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,5,27]],"date-time":"2020-05-27T00:00:00Z","timestamp":1590537600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"IBM"},{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1409130, CCF-1617653, CCF-1844939, CCF-1617724, CCF-1733873, CCF-1725543, CCF-1408784, CCF-1637397, IIS-1447554, CCF-1421508, CCF-1535755"],"award-info":[{"award-number":["CCF-1409130, CCF-1617653, CCF-1844939, CCF-1617724, CCF-1733873, CCF-1725543, CCF-1408784, CCF-1637397, IIS-1447554, CCF-1421508, CCF-1535755"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-19-1-226"],"award-info":[{"award-number":["N00014-19-1-226"]}],"id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Facebook"},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Adobe"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2020,5,27]]},"abstract":"<jats:p>In this paper, we consider the following dynamic fair allocation problem: Given a sequence of job arrivals and departures, the goal is to maintain an approximately fair allocation of the resource against a target fair allocation policy, while minimizing the total number of \\em disruptions, which is the number of times the allocation of any job is changed. We consider a rich class of fair allocation policies that significantly generalize those considered in previous work. We first consider the models where jobs only arrive, or jobs only depart. We present tight upper and lower bounds for the number of disruptions required to maintain a constant approximate fair allocation every time step. In particular, for the canonical case where jobs have weights and the resource allocation is proportional to the job's weight, we show that maintaining a constant approximate fair allocation requires \u0398(\u0142og^* n) disruptions per job, almost matching the bounds in prior work for the unit weight case. For the more general setting where the allocation policy only decreases the allocation to a job when new jobs arrive, we show that maintaining a constant approximate fair allocation requires \u0398(\u0142og n) disruptions per job. We then consider the model where jobs can both arrive and depart. We first show strong lower bounds on the number of disruptions required to maintain constant approximate fairness for arbitrary instances. In contrast we then show that there there is an algorithm that can maintain constant approximate fairness with $O(1)$ expected disruptions per job if the weights of the jobs are independent of the jobs arrival and departure order. We finally show how our results can be extended to the setting with multiple resources.<\/jats:p>","DOI":"10.1145\/3379485","type":"journal-article","created":{"date-parts":[[2020,5,28]],"date-time":"2020-05-28T04:29:21Z","timestamp":1590640161000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic Weighted Fairness with Minimal Disruptions"],"prefix":"10.1145","volume":"4","author":[{"given":"Sungjin","family":"Im","sequence":"first","affiliation":[{"name":"University of California, Merced, Merced, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kamesh","family":"Munagala","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kirk","family":"Pruhs","sequence":"additional","affiliation":[{"name":"University of Pittsburgh, pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,5,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219179"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2523616.2523637"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603019"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090243"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496845"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/639"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602889"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764495"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085123"},{"key":"e_1_2_1_10_1","first-page":"323","volume-title":"Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, NSDI'11","author":"Ghodsi Ali","year":"2011","unstructured":"Ali Ghodsi , Matei Zaharia , Benjamin Hindman , Andy Konwinski , Scott Shenker , and Ion Stoica . Dominant resource fairness: Fair allocation of multiple resource types . In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, NSDI'11 , pages 323 -- 336 , Berkeley, CA, USA , 2011 . USENIX Association. Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, NSDI'11, pages 323--336, Berkeley, CA, USA, 2011. USENIX Association."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1086\/260757"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591814"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629601"},{"key":"e_1_2_1_15_1","first-page":"351","volume-title":"Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS '13","author":"Kash Ian","year":"2013","unstructured":"Ian Kash , Ariel D. Procaccia , and Nisarg Shah . No agent left behind: Dynamic fair division of multiple resources . In Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS '13 , pages 351 -- 358 , Richland, SC , 2013 . International Foundation for Autonomous Agents and Multiagent Systems. Ian Kash, Ariel D. Procaccia, and Nisarg Shah. No agent left behind: Dynamic fair division of multiple resources. In Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS '13, pages 351--358, Richland, SC, 2013. International Foundation for Autonomous Agents and Multiagent Systems."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3304415.3304469"},{"key":"e_1_2_1_17_1","volume-title":"Dynamic fair division problem with general valuations. CoRR, abs\/1802.05294","author":"Li Bo","year":"2018","unstructured":"Bo Li and Yingkai Li . Dynamic fair division problem with general valuations. CoRR, abs\/1802.05294 , 2018 . Bo Li and Yingkai Li. Dynamic fair division problem with general valuations. CoRR, abs\/1802.05294, 2018."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/367701.367728"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2739040"},{"key":"e_1_2_1_20_1","volume-title":"Omega: flexible, scalable schedulers for large compute clusters","author":"Schwarzkopf Malte","year":"2013","unstructured":"Malte Schwarzkopf , Andy Konwinski , Michael Abd-El-Malek , and John Wilkes . Omega: flexible, scalable schedulers for large compute clusters . 2013 . Malte Schwarzkopf, Andy Konwinski, Michael Abd-El-Malek, and John Wilkes. Omega: flexible, scalable schedulers for large compute clusters. 2013."},{"key":"e_1_2_1_21_1","volume-title":"envy, and efficiency. Journal of Economic Theory, 9(1):63 -- 91","author":"Varian Hal R","year":"1974","unstructured":"Hal R Varian . Equity , envy, and efficiency. Journal of Economic Theory, 9(1):63 -- 91 , 1974 . Hal R Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63 -- 91, 1974."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741964"},{"key":"e_1_2_1_23_1","volume-title":"June","author":"Walsh T.","year":"2011","unstructured":"T. Walsh . Online Cake Cutting (published version). ArXiv e-prints , June 2011 . T. Walsh. Online Cake Cutting (published version). ArXiv e-prints, June 2011."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6847983"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2015.49"}],"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\/3379485","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3379485","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3379485","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:22Z","timestamp":1750197742000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379485"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,27]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,5,27]]}},"alternative-id":["10.1145\/3379485"],"URL":"https:\/\/doi.org\/10.1145\/3379485","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2020,5,27]]},"assertion":[{"value":"2020-05-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}