{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T08:25:34Z","timestamp":1774599934807,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,8,2]],"date-time":"2016-08-02T00:00:00Z","timestamp":1470096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CNS","award":["1565774"],"award-info":[{"award-number":["1565774"]}]},{"name":"Simons Foundation Chair at UT Austin"},{"name":"NSF ECCS","award":["1202065"],"award-info":[{"award-number":["1202065"]}]},{"name":"US DOT supported D-STOP Tier 1 UTC"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2016,9,21]]},"abstract":"<jats:p>\n            Motivated by emerging big\n            <jats:italic>streaming<\/jats:italic>\n            data processing paradigms (e.g., Twitter Storm, Streaming MapReduce), we investigate the problem of scheduling graphs over a large cluster of servers. Each graph is a job, where nodes represent compute tasks and edges indicate data flows between these compute tasks. Jobs (graphs) arrive randomly over time and, upon completion, leave the system. When a job arrives, the scheduler needs to partition the graph and distribute it over the servers to satisfy load balancing and cost considerations. Specifically, neighboring compute tasks in the graph that are mapped to different servers incur load on the network; thus a mapping of the jobs among the servers incurs a cost that is proportional to the number of \u201cbroken edges.\u201d We propose a low-complexity randomized scheduling algorithm that, without service preemptions, stabilizes the system with graph arrivals\/departures; more importantly, it allows a smooth tradeoff between minimizing average partitioning cost and average queue lengths. Interestingly, to avoid service preemptions, our approach does not rely on a Gibbs sampler; instead, we show that the corresponding limiting invariant measure has an interpretation stemming from a loss system.\n          <\/jats:p>","DOI":"10.1145\/2904080","type":"journal-article","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T13:26:34Z","timestamp":1470317194000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Scheduling Storms and Streams in the Cloud"],"prefix":"10.1145","volume":"1","author":[{"given":"Javad","family":"Ghaderi","sequence":"first","affiliation":[{"name":"Columbia University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjay","family":"Shakkottai","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Srikant","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,8,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1350-7"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488222.2488267"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190095.1190168"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3124-8"},{"key":"e_1_2_1_5_1","volume-title":"Recent advances in graph partitioning. arXiv:1311.3144","author":"Buluc Aydin","year":"2013","unstructured":"Aydin Buluc , Henning Meyerhenke , Ilya Safro , Peter Sanders , and Christian Schulz . 2013. Recent advances in graph partitioning. arXiv:1311.3144 ( 2013 ). Aydin Buluc, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. 2013. Recent advances in graph partitioning. arXiv:1311.3144 (2013)."},{"key":"e_1_2_1_6_1","volume-title":"Johnson","author":"Coffman Edward G.","year":"1996","unstructured":"Edward G. Coffman Jr ., Michael R. Garey , and David S . Johnson . 1996 . Approximation algorithms for bin packing: A survey. In Approximation Algorithms for NP-Hard Problems. PWS Publishing Co. , 46--93. Edward G. Coffman Jr., Michael R. Garey, and David S. Johnson. 1996. Approximation algorithms for bin packing: A survey. In Approximation Algorithms for NP-Hard Problems. PWS Publishing Co., 46--93."},{"key":"e_1_2_1_7_1","first-page":"20","article-title":"MapReduce online","volume":"10","author":"Condie Tyson","year":"2010","unstructured":"Tyson Condie , Neil Conway , Peter Alvaro , Joseph M. Hellerstein , Khaled Elmeleegy , and Russell Sears . 2010 . MapReduce online . In NSDI , Vol. 10. 20 . Tyson Condie, Neil Conway, Peter Alvaro, Joseph M. Hellerstein, Khaled Elmeleegy, and Russell Sears. 2010. MapReduce online. In NSDI, Vol. 10. 20.","journal-title":"NSDI"},{"key":"e_1_2_1_8_1","volume-title":"Woeginger","author":"Csirik J\u00e1nos","year":"1998","unstructured":"J\u00e1nos Csirik and Gerhard J . Woeginger . 1998 . On-Line Packing and Covering Problems. Springer , Berlin. J\u00e1nos Csirik and Gerhard J. Woeginger. 1998. On-Line Packing and Covering Problems. Springer, Berlin."},{"key":"e_1_2_1_9_1","volume-title":"Balanced partitions of trees and applications. Algorithmica","author":"Feldmann Andreas Emil","year":"2012","unstructured":"Andreas Emil Feldmann and Luca Foschini . 2012. Balanced partitions of trees and applications. Algorithmica ( 2012 ), 1--23. Andreas Emil Feldmann and Luca Foschini. 2012. Balanced partitions of trees and applications. Algorithmica (2012), 1--23."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2316028"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745882"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2010.5717965"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2667522.2667543"},{"key":"e_1_2_1_14_1","volume-title":"https:\/\/giraph.apache.org\/. Date accessed","year":"2016","unstructured":"Giraph. 2016. https:\/\/giraph.apache.org\/. Date accessed July 25 2016 . Giraph. 2016. https:\/\/giraph.apache.org\/. Date accessed July 25 2016."},{"key":"e_1_2_1_15_1","volume-title":"https:\/\/turi.com\/products\/create. Date accessed","year":"2016","unstructured":"Graphlab. 2016. https:\/\/turi.com\/products\/create. Date accessed 25 July 2016 . Graphlab. 2016. https:\/\/turi.com\/products\/create. Date accessed 25 July 2016."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.29.3.567"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/224170.224228"},{"key":"e_1_2_1_18_1","volume-title":"http:\/\/www-01.ibm.com\/software\/data\/infosphere. Date accessed","author":"InfoSphere IBM","year":"2016","unstructured":"IBM InfoSphere . 2016. http:\/\/www-01.ibm.com\/software\/data\/infosphere. Date accessed 25 July 2016 . IBM InfoSphere. 2016. http:\/\/www-01.ibm.com\/software\/data\/infosphere. Date accessed 25 July 2016."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195719"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2009.2035046"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.23.4.687"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/wcm.v10:1"},{"key":"e_1_2_1_23_1","volume-title":"Stochastic Network Optimization with Application to Communication and Queueing Systems","author":"Neely Michael J.","unstructured":"Michael J. Neely . 2010. Stochastic Network Optimization with Application to Communication and Queueing Systems . Vol. 3 . Morgan & Claypool Publishers , London , 1--211 pages. Michael J. Neely. 2010. Stochastic Network Optimization with Application to Communication and Queueing Systems. Vol. 3. Morgan & Claypool Publishers, London, 1--211 pages."},{"key":"e_1_2_1_24_1","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman Martin L.","unstructured":"Martin L. Puterman . 2009. Markov Decision Processes: Discrete Stochastic Dynamic Programming . Vol. 414 . John Wiley & Sons , New York, NY . Martin L. Puterman. 2009. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Vol. 414. John Wiley & Sons, New York, NY."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465353"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492101.1555365"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CISIS.2014.94"},{"key":"e_1_2_1_28_1","unstructured":"S4. n.d. S4 distributed stream computing platform. http:\/\/incubator.apache.org\/s4. (n.d.).  S4. n.d. S4 distributed stream computing platform. http:\/\/incubator.apache.org\/s4. (n.d.)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP763"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2013.1184"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-014-9414-x"},{"key":"e_1_2_1_32_1","unstructured":"Storm. n.d. Storm: Distributed and fault-tolerant realtime computation. http:\/\/storm.incubator.apache.org. (n.d.).  Storm. n.d. Storm: Distributed and fault-tolerant realtime computation. http:\/\/storm.incubator.apache.org. (n.d.)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598337373"},{"key":"e_1_2_1_34_1","unstructured":"Wikipedia. n.d. Graph partition problem on Wikipedia. http:\/\/en.wikipedia.org\/wiki\/Graph_partition. (n.d.).  Wikipedia. n.d. Graph partition problem on Wikipedia. http:\/\/en.wikipedia.org\/wiki\/Graph_partition. (n.d.)."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 4th USENIX Conference on Hot Topics in Cloud Ccomputing. USENIX Association, 10--10","author":"Zaharia Matei","year":"2012","unstructured":"Matei Zaharia , Tathagata Das , Haoyuan Li , Scott Shenker , and Ion Stoica . 2012 . Discretized streams: An efficient and fault-tolerant model for stream processing on large clusters . In Proceedings of the 4th USENIX Conference on Hot Topics in Cloud Ccomputing. USENIX Association, 10--10 . Matei Zaharia, Tathagata Das, Haoyuan Li, Scott Shenker, and Ion Stoica. 2012. Discretized streams: An efficient and fault-tolerant model for stream processing on large clusters. In Proceedings of the 4th USENIX Conference on Hot Topics in Cloud Ccomputing. USENIX Association, 10--10."}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2904080","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2904080","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:33Z","timestamp":1750222473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2904080"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,2]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,9,21]]}},"alternative-id":["10.1145\/2904080"],"URL":"https:\/\/doi.org\/10.1145\/2904080","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"value":"2376-3639","type":"print"},{"value":"2376-3647","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,2]]},"assertion":[{"value":"2015-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}