[{"acknowledgement":"J.R. and J.V.A. were also supported by the Academy of Finland Grants 1273253 and 267541.","pubrep_id":"1063","file_date_updated":"2020-07-14T12:46:26Z","publication_identifier":{"eissn":["1091-6490"],"issn":["0027-8424"]},"year":"2018","isi":1,"language":[{"iso":"eng"}],"publication":"Proceedings of the National Academy of Sciences of the United States of America","quality_controlled":"1","publist_id":"8011","author":[{"orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","last_name":"Rybicki"},{"full_name":"Kisdi, Eva","first_name":"Eva","last_name":"Kisdi"},{"first_name":"Jani","full_name":"Anttila, Jani","last_name":"Anttila"}],"issue":"42","file":[{"content_type":"application/pdf","creator":"dernst","access_level":"open_access","file_id":"6258","date_updated":"2020-07-14T12:46:26Z","file_size":4070777,"relation":"main_file","date_created":"2019-04-09T08:02:50Z","file_name":"2018_PNAS_Rybicki.pdf","checksum":"df7ac544a587c06b75692653b9fabd18"}],"abstract":[{"lang":"eng","text":"The initial amount of pathogens required to start an infection within a susceptible host is called the infective dose and is known to vary to a large extent between different pathogen species. We investigate the hypothesis that the differences in infective doses are explained by the mode of action in the underlying mechanism of pathogenesis: Pathogens with locally acting mechanisms tend to have smaller infective doses than pathogens with distantly acting mechanisms. While empirical evidence tends to support the hypothesis, a formal theoretical explanation has been lacking. We give simple analytical models to gain insight into this phenomenon and also investigate a stochastic, spatially explicit, mechanistic within-host model for toxin-dependent bacterial infections. The model shows that pathogens secreting locally acting toxins have smaller infective doses than pathogens secreting diffusive toxins, as hypothesized. While local pathogenetic mechanisms require smaller infective doses, pathogens with distantly acting toxins tend to spread faster and may cause more damage to the host. The proposed model can serve as a basis for the spatially explicit analysis of various virulence factors also in the context of other problems in infection dynamics."}],"page":"10690 - 10695","external_id":{"isi":["000447491300057"]},"article_processing_charge":"No","date_published":"2018-10-02T00:00:00Z","date_created":"2018-12-11T11:44:19Z","status":"public","ddc":["570","577"],"title":"Model of bacterial toxin-dependent pathogenesis explains infective dose","month":"10","date_updated":"2025-06-03T11:16:28Z","_id":"43","ec_funded":1,"type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"02","oa_version":"Submitted Version","doi":"10.1073/pnas.1721061115","project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"scopus_import":"1","has_accepted_license":"1","volume":115,"intvolume":"       115","publication_status":"published","department":[{"_id":"DaAl"}],"publisher":"National Academy of Sciences","oa":1,"citation":{"mla":"Rybicki, Joel, et al. “Model of Bacterial Toxin-Dependent Pathogenesis Explains Infective Dose.” <i>Proceedings of the National Academy of Sciences of the United States of America</i>, vol. 115, no. 42, National Academy of Sciences, 2018, pp. 10690–95, doi:<a href=\"https://doi.org/10.1073/pnas.1721061115\">10.1073/pnas.1721061115</a>.","ieee":"J. Rybicki, E. Kisdi, and J. Anttila, “Model of bacterial toxin-dependent pathogenesis explains infective dose,” <i>Proceedings of the National Academy of Sciences of the United States of America</i>, vol. 115, no. 42. National Academy of Sciences, pp. 10690–10695, 2018.","apa":"Rybicki, J., Kisdi, E., &#38; Anttila, J. (2018). Model of bacterial toxin-dependent pathogenesis explains infective dose. <i>Proceedings of the National Academy of Sciences of the United States of America</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.1721061115\">https://doi.org/10.1073/pnas.1721061115</a>","ista":"Rybicki J, Kisdi E, Anttila J. 2018. Model of bacterial toxin-dependent pathogenesis explains infective dose. Proceedings of the National Academy of Sciences of the United States of America. 115(42), 10690–10695.","ama":"Rybicki J, Kisdi E, Anttila J. Model of bacterial toxin-dependent pathogenesis explains infective dose. <i>Proceedings of the National Academy of Sciences of the United States of America</i>. 2018;115(42):10690-10695. doi:<a href=\"https://doi.org/10.1073/pnas.1721061115\">10.1073/pnas.1721061115</a>","short":"J. Rybicki, E. Kisdi, J. Anttila, Proceedings of the National Academy of Sciences of the United States of America 115 (2018) 10690–10695.","chicago":"Rybicki, Joel, Eva Kisdi, and Jani Anttila. “Model of Bacterial Toxin-Dependent Pathogenesis Explains Infective Dose.” <i>Proceedings of the National Academy of Sciences of the United States of America</i>. National Academy of Sciences, 2018. <a href=\"https://doi.org/10.1073/pnas.1721061115\">https://doi.org/10.1073/pnas.1721061115</a>."}},{"citation":{"ieee":"D.-A. Alistarh, T. A. Brown, J. Kopinsky, J. Z. Li, and G. Nadiradze, “Distributionally linearizable data structures,” in <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, Vienna, Austria, 2018, pp. 133–142.","ista":"Alistarh D-A, Brown TA, Kopinsky J, Li JZ, Nadiradze G. 2018. Distributionally linearizable data structures. Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18. SPAA: Symposium on Parallelism in Algorithms and Architectures, 133–142.","apa":"Alistarh, D.-A., Brown, T. A., Kopinsky, J., Li, J. Z., &#38; Nadiradze, G. (2018). Distributionally linearizable data structures. In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i> (pp. 133–142). Vienna, Austria: ACM. <a href=\"https://doi.org/10.1145/3210377.3210411\">https://doi.org/10.1145/3210377.3210411</a>","mla":"Alistarh, Dan-Adrian, et al. “Distributionally Linearizable Data Structures.” <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, ACM, 2018, pp. 133–42, doi:<a href=\"https://doi.org/10.1145/3210377.3210411\">10.1145/3210377.3210411</a>.","chicago":"Alistarh, Dan-Adrian, Trevor A Brown, Justin Kopinsky, Jerry Z. Li, and Giorgi Nadiradze. “Distributionally Linearizable Data Structures.” In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, 133–42. ACM, 2018. <a href=\"https://doi.org/10.1145/3210377.3210411\">https://doi.org/10.1145/3210377.3210411</a>.","short":"D.-A. Alistarh, T.A. Brown, J. Kopinsky, J.Z. Li, G. Nadiradze, in:, Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18, ACM, 2018, pp. 133–142.","ama":"Alistarh D-A, Brown TA, Kopinsky J, Li JZ, Nadiradze G. Distributionally linearizable data structures. In: <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>. ACM; 2018:133-142. doi:<a href=\"https://doi.org/10.1145/3210377.3210411\">10.1145/3210377.3210411</a>"},"oa":1,"publisher":"ACM","department":[{"_id":"DaAl"}],"arxiv":1,"publication_status":"published","scopus_import":"1","conference":{"start_date":"2018-07-16","end_date":"2018-07-18","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures","location":"Vienna, Austria"},"doi":"10.1145/3210377.3210411","day":"16","main_file_link":[{"url":"https://arxiv.org/abs/1804.01018","open_access":"1"}],"oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","_id":"5965","date_updated":"2026-04-08T07:00:45Z","month":"07","title":"Distributionally linearizable data structures","status":"public","date_created":"2019-02-13T10:17:19Z","date_published":"2018-07-16T00:00:00Z","article_processing_charge":"No","external_id":{"isi":["000545269600016"],"arxiv":["1804.01018"]},"related_material":{"record":[{"relation":"dissertation_contains","id":"10429","status":"public"}]},"page":"133-142","abstract":[{"text":"Relaxed concurrent data structures have become increasingly popular, due to their scalability in graph processing and machine learning applications (\\citeNguyen13, gonzalez2012powergraph ). Despite considerable interest, there exist families of natural, high performing randomized relaxed concurrent data structures, such as the popular MultiQueue~\\citeMQ pattern for implementing relaxed priority queue data structures, for which no guarantees are known in the concurrent setting~\\citeAKLN17. Our main contribution is in showing for the first time that, under a set of analytic assumptions, a family of relaxed concurrent data structures, including variants of MultiQueues, but also a new approximate counting algorithm we call the MultiCounter, provides strong probabilistic guarantees on the degree of relaxation with respect to the sequential specification, in arbitrary concurrent executions. We formalize these guarantees via a new correctness condition called distributional linearizability, tailored to concurrent implementations with randomized relaxations. Our result is based on a new analysis of an asynchronous variant of the classic power-of-two-choices load balancing algorithm, in which placement choices can be based on inconsistent, outdated information (this result may be of independent interest). We validate our results empirically, showing that the MultiCounter algorithm can implement scalable relaxed timestamps.","lang":"eng"}],"author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"},{"last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","first_name":"Trevor A","full_name":"Brown, Trevor A"},{"last_name":"Kopinsky","full_name":"Kopinsky, Justin","first_name":"Justin"},{"last_name":"Li","first_name":"Jerry Z.","full_name":"Li, Jerry Z."},{"last_name":"Nadiradze","full_name":"Nadiradze, Giorgi","first_name":"Giorgi"}],"quality_controlled":"1","isi":1,"publication":"Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA '18","language":[{"iso":"eng"}],"year":"2018","publication_identifier":{"isbn":["9781450357999"]}},{"date_updated":"2026-04-16T09:53:54Z","_id":"536","month":"11","title":"Communication-efficient randomized consensus","ddc":["000"],"corr_author":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","has_accepted_license":"1","scopus_import":"1","volume":31,"project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"oa_version":"Published Version","day":"01","doi":"10.1007/s00446-017-0315-1","oa":1,"citation":{"ista":"Alistarh D-A, Aspnes J, King V, Saia J. 2018. Communication-efficient randomized consensus. Distributed Computing. 31(6), 489–501.","ieee":"D.-A. Alistarh, J. Aspnes, V. King, and J. Saia, “Communication-efficient randomized consensus,” <i>Distributed Computing</i>, vol. 31, no. 6. Springer, pp. 489–501, 2018.","apa":"Alistarh, D.-A., Aspnes, J., King, V., &#38; Saia, J. (2018). Communication-efficient randomized consensus. <i>Distributed Computing</i>. Springer. <a href=\"https://doi.org/10.1007/s00446-017-0315-1\">https://doi.org/10.1007/s00446-017-0315-1</a>","mla":"Alistarh, Dan-Adrian, et al. “Communication-Efficient Randomized Consensus.” <i>Distributed Computing</i>, vol. 31, no. 6, Springer, 2018, pp. 489–501, doi:<a href=\"https://doi.org/10.1007/s00446-017-0315-1\">10.1007/s00446-017-0315-1</a>.","ama":"Alistarh D-A, Aspnes J, King V, Saia J. Communication-efficient randomized consensus. <i>Distributed Computing</i>. 2018;31(6):489-501. doi:<a href=\"https://doi.org/10.1007/s00446-017-0315-1\">10.1007/s00446-017-0315-1</a>","short":"D.-A. Alistarh, J. Aspnes, V. King, J. Saia, Distributed Computing 31 (2018) 489–501.","chicago":"Alistarh, Dan-Adrian, James Aspnes, Valerie King, and Jared Saia. “Communication-Efficient Randomized Consensus.” <i>Distributed Computing</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s00446-017-0315-1\">https://doi.org/10.1007/s00446-017-0315-1</a>."},"publisher":"Springer","publication_status":"published","department":[{"_id":"DaAl"}],"intvolume":"        31","isi":1,"language":[{"iso":"eng"}],"publication":"Distributed Computing","year":"2018","publication_identifier":{"issn":["0178-2770"]},"file_date_updated":"2020-07-14T12:46:38Z","publist_id":"7281","author":[{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"},{"full_name":"Aspnes, James","first_name":"James","last_name":"Aspnes"},{"full_name":"King, Valerie","first_name":"Valerie","last_name":"King"},{"first_name":"Jared","full_name":"Saia, Jared","last_name":"Saia"}],"issue":"6","quality_controlled":"1","abstract":[{"text":"We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary. We describe a new randomized consensus protocol with expected message complexity O(n2log2n) when fewer than n / 2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known Ω(n2) message lower bound. The protocol further ensures that no process sends more than O(nlog3n) messages in expectation, which is again within logarithmic factors of optimal. We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected O(nt+t2log2t) total messages. Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model.","lang":"eng"}],"page":"489-501","file":[{"relation":"main_file","checksum":"69b46e537acdcac745237ddb853fcbb5","file_name":"2017_DistribComp_Alistarh.pdf","date_created":"2019-01-22T07:25:51Z","creator":"dernst","access_level":"open_access","content_type":"application/pdf","file_size":595707,"date_updated":"2020-07-14T12:46:38Z","file_id":"5867"}],"status":"public","article_processing_charge":"Yes (via OA deal)","date_created":"2018-12-11T11:47:01Z","date_published":"2018-11-01T00:00:00Z","external_id":{"isi":["000443832300005"]},"license":"https://creativecommons.org/licenses/by/4.0/"},{"month":"08","_id":"85","date_updated":"2026-04-16T09:53:41Z","alternative_title":["LNCS"],"title":"Snapshot based synchronization: A fast replacement for Hand-over-Hand locking","ddc":["000"],"type":"conference","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","project":[{"name":"NSERC Postdoctoral fellowship","_id":"26450934-B435-11E9-9278-68D0E5697425"}],"conference":{"start_date":"2018-08-27","end_date":"2018-08-31","name":"Euro-Par: European Conference on Parallel Processing","location":"Turin, Italy"},"volume":11014,"scopus_import":"1","has_accepted_license":"1","doi":"10.1007/978-3-319-96983-1_33","day":"01","oa_version":"Preprint","publisher":"Springer","citation":{"short":"E. Gilad, T.A. Brown, M. Oskin, Y. Etsion, in:, Springer, 2018, pp. 465–479.","ama":"Gilad E, Brown TA, Oskin M, Etsion Y. Snapshot based synchronization: A fast replacement for Hand-over-Hand locking. In: Vol 11014. Springer; 2018:465-479. doi:<a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">10.1007/978-3-319-96983-1_33</a>","chicago":"Gilad, Eran, Trevor A Brown, Mark Oskin, and Yoav Etsion. “Snapshot Based Synchronization: A Fast Replacement for Hand-over-Hand Locking,” 11014:465–79. Springer, 2018. <a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">https://doi.org/10.1007/978-3-319-96983-1_33</a>.","ista":"Gilad E, Brown TA, Oskin M, Etsion Y. 2018. Snapshot based synchronization: A fast replacement for Hand-over-Hand locking. Euro-Par: European Conference on Parallel Processing, LNCS, vol. 11014, 465–479.","ieee":"E. Gilad, T. A. Brown, M. Oskin, and Y. Etsion, “Snapshot based synchronization: A fast replacement for Hand-over-Hand locking,” presented at the Euro-Par: European Conference on Parallel Processing, Turin, Italy, 2018, vol. 11014, pp. 465–479.","apa":"Gilad, E., Brown, T. A., Oskin, M., &#38; Etsion, Y. (2018). Snapshot based synchronization: A fast replacement for Hand-over-Hand locking (Vol. 11014, pp. 465–479). Presented at the Euro-Par: European Conference on Parallel Processing, Turin, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">https://doi.org/10.1007/978-3-319-96983-1_33</a>","mla":"Gilad, Eran, et al. <i>Snapshot Based Synchronization: A Fast Replacement for Hand-over-Hand Locking</i>. Vol. 11014, Springer, 2018, pp. 465–79, doi:<a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">10.1007/978-3-319-96983-1_33</a>."},"oa":1,"intvolume":"     11014","department":[{"_id":"DaAl"}],"publication_status":"published","publication_identifier":{"issn":["0302-9743"]},"isi":1,"language":[{"iso":"eng"}],"year":"2018","file_date_updated":"2020-07-14T12:48:14Z","acknowledgement":"Trevor Brown was supported in part by the ISF (grants 2005/17 & 1749/14) and by a NSERC post-doctoral fellowship.","quality_controlled":"1","author":[{"last_name":"Gilad","first_name":"Eran","full_name":"Gilad, Eran"},{"last_name":"Brown","full_name":"Brown, Trevor A","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","first_name":"Trevor A"},{"full_name":"Oskin, Mark","first_name":"Mark","last_name":"Oskin"},{"last_name":"Etsion","full_name":"Etsion, Yoav","first_name":"Yoav"}],"publist_id":"7969","file":[{"file_id":"5954","file_size":665372,"date_updated":"2020-07-14T12:48:14Z","content_type":"application/pdf","access_level":"open_access","creator":"dernst","date_created":"2019-02-12T07:40:40Z","file_name":"2018_Brown.pdf","checksum":"13a3f250be8878405e791b53c19722ad","relation":"main_file"}],"page":"465 - 479","abstract":[{"lang":"eng","text":"Concurrent accesses to shared data structures must be synchronized to avoid data races. Coarse-grained synchronization, which locks the entire data structure, is easy to implement but does not scale. Fine-grained synchronization can scale well, but can be hard to reason about. Hand-over-hand locking, in which operations are pipelined as they traverse the data structure, combines fine-grained synchronization with ease of use. However, the traditional implementation suffers from inherent overheads. This paper introduces snapshot-based synchronization (SBS), a novel hand-over-hand locking mechanism. SBS decouples the synchronization state from the data, significantly improving cache utilization. Further, it relies on guarantees provided by pipelining to minimize synchronization that requires cross-thread communication. Snapshot-based synchronization thus scales much better than traditional hand-over-hand locking, while maintaining the same ease of use."}],"date_published":"2018-08-01T00:00:00Z","date_created":"2018-12-11T11:44:33Z","article_processing_charge":"No","status":"public","external_id":{"isi":["000851042300031"]}},{"publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","isi":1,"language":[{"iso":"eng"}],"year":"2017","publication_identifier":{"isbn":["978-145034992-5"]},"publist_id":"6864","author":[{"last_name":"Alistarh","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"full_name":"Kopinsky, Justin","first_name":"Justin","last_name":"Kopinsky"},{"full_name":"Li, Jerry","first_name":"Jerry","last_name":"Li"},{"first_name":"Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5634-0731","full_name":"Nadiradze, Giorgi","last_name":"Nadiradze"}],"quality_controlled":"1","abstract":[{"lang":"eng","text":"Consider the following random process: we are given n queues, into which elements of increasing labels are inserted uniformly at random. To remove an element, we pick two queues at random, and remove the element of lower label (higher priority) among the two. The cost of a removal is the rank of the label removed, among labels still present in any of the queues, that is, the distance from the optimal choice at each step. Variants of this strategy are prevalent in state-of-the-art concurrent priority queue implementations. Nonetheless, it is not known whether such implementations provide any rank guarantees, even in a sequential model. We answer this question, showing that this strategy provides surprisingly strong guarantees: Although the single-choice process, where we always insert and remove from a single randomly chosen queue, has degrading cost, going to infinity as we increase the number of steps, in the two choice process, the expected rank of a removed element is O(n) while the expected worst-case cost is O(n log n). These bounds are tight, and hold irrespective of the number of steps for which we run the process. The argument is based on a new technical connection between &quot;heavily loaded&quot; balls-into-bins processes and priority scheduling. Our analytic results inspire a new concurrent priority queue implementation, which improves upon the state of the art in terms of practical performance."}],"page":"283 - 292","external_id":{"isi":["000462995000035"],"arxiv":["1706.04178"]},"status":"public","article_processing_charge":"No","date_created":"2018-12-11T11:48:31Z","date_published":"2017-07-26T00:00:00Z","title":"The power of choice in priority scheduling","date_updated":"2025-06-04T09:44:47Z","_id":"791","month":"07","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","oa_version":"Submitted Version","day":"26","main_file_link":[{"url":"https://arxiv.org/abs/1706.04178","open_access":"1"}],"doi":"10.1145/3087801.3087810","scopus_import":"1","volume":"Part F129314","conference":{"start_date":"2017-07-25","end_date":"2017-07-27","name":"PODC: Principles of Distributed Computing","location":"Washington, WA, USA"},"arxiv":1,"publication_status":"published","department":[{"_id":"DaAl"}],"oa":1,"citation":{"short":"D.-A. Alistarh, J. Kopinsky, J. Li, G. Nadiradze, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, ACM, 2017, pp. 283–292.","ama":"Alistarh D-A, Kopinsky J, Li J, Nadiradze G. The power of choice in priority scheduling. In: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Vol Part F129314. ACM; 2017:283-292. doi:<a href=\"https://doi.org/10.1145/3087801.3087810\">10.1145/3087801.3087810</a>","chicago":"Alistarh, Dan-Adrian, Justin Kopinsky, Jerry Li, and Giorgi Nadiradze. “The Power of Choice in Priority Scheduling.” In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Part F129314:283–92. ACM, 2017. <a href=\"https://doi.org/10.1145/3087801.3087810\">https://doi.org/10.1145/3087801.3087810</a>.","ista":"Alistarh D-A, Kopinsky J, Li J, Nadiradze G. 2017. The power of choice in priority scheduling. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing vol. Part F129314, 283–292.","apa":"Alistarh, D.-A., Kopinsky, J., Li, J., &#38; Nadiradze, G. (2017). The power of choice in priority scheduling. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i> (Vol. Part F129314, pp. 283–292). Washington, WA, USA: ACM. <a href=\"https://doi.org/10.1145/3087801.3087810\">https://doi.org/10.1145/3087801.3087810</a>","ieee":"D.-A. Alistarh, J. Kopinsky, J. Li, and G. Nadiradze, “The power of choice in priority scheduling,” in <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Washington, WA, USA, 2017, vol. Part F129314, pp. 283–292.","mla":"Alistarh, Dan-Adrian, et al. “The Power of Choice in Priority Scheduling.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, vol. Part F129314, ACM, 2017, pp. 283–92, doi:<a href=\"https://doi.org/10.1145/3087801.3087810\">10.1145/3087801.3087810</a>."},"publisher":"ACM"},{"conference":{"location":"Incheon, South Korea","name":"CoNEXT: Conference on emerging Networking EXperiments and Technologies","start_date":"2017-12-12","end_date":"2017-12-15"},"scopus_import":"1","doi":"10.1145/3143361.3143367","day":"28","oa_version":"None","publisher":"ACM","citation":{"mla":"Baig, Ghufran, et al. “Towards Unlicensed Cellular Networks in TV White Spaces.” <i>Proceedings of the 2017 13th International Conference on Emerging Networking EXperiments and Technologies</i>, ACM, 2017, pp. 2–14, doi:<a href=\"https://doi.org/10.1145/3143361.3143367\">10.1145/3143361.3143367</a>.","ista":"Baig G, Radunovic B, Alistarh D-A, Balkwill M, Karagiannis T, Qiu L. 2017. Towards unlicensed cellular networks in TV white spaces. Proceedings of the 2017 13th International Conference on emerging Networking EXperiments and Technologies. CoNEXT: Conference on emerging Networking EXperiments and Technologies, 2–14.","apa":"Baig, G., Radunovic, B., Alistarh, D.-A., Balkwill, M., Karagiannis, T., &#38; Qiu, L. (2017). Towards unlicensed cellular networks in TV white spaces. In <i>Proceedings of the 2017 13th International Conference on emerging Networking EXperiments and Technologies</i> (pp. 2–14). Incheon, South Korea: ACM. <a href=\"https://doi.org/10.1145/3143361.3143367\">https://doi.org/10.1145/3143361.3143367</a>","ieee":"G. Baig, B. Radunovic, D.-A. Alistarh, M. Balkwill, T. Karagiannis, and L. Qiu, “Towards unlicensed cellular networks in TV white spaces,” in <i>Proceedings of the 2017 13th International Conference on emerging Networking EXperiments and Technologies</i>, Incheon, South Korea, 2017, pp. 2–14.","short":"G. Baig, B. Radunovic, D.-A. Alistarh, M. Balkwill, T. Karagiannis, L. Qiu, in:, Proceedings of the 2017 13th International Conference on Emerging Networking EXperiments and Technologies, ACM, 2017, pp. 2–14.","ama":"Baig G, Radunovic B, Alistarh D-A, Balkwill M, Karagiannis T, Qiu L. Towards unlicensed cellular networks in TV white spaces. In: <i>Proceedings of the 2017 13th International Conference on Emerging Networking EXperiments and Technologies</i>. ACM; 2017:2-14. doi:<a href=\"https://doi.org/10.1145/3143361.3143367\">10.1145/3143361.3143367</a>","chicago":"Baig, Ghufran, Bozidar Radunovic, Dan-Adrian Alistarh, Matthew Balkwill, Thomas Karagiannis, and Lili Qiu. “Towards Unlicensed Cellular Networks in TV White Spaces.” In <i>Proceedings of the 2017 13th International Conference on Emerging Networking EXperiments and Technologies</i>, 2–14. ACM, 2017. <a href=\"https://doi.org/10.1145/3143361.3143367\">https://doi.org/10.1145/3143361.3143367</a>."},"department":[{"_id":"DaAl"}],"publication_status":"published","month":"11","_id":"487","date_updated":"2025-09-18T09:50:43Z","corr_author":"1","title":"Towards unlicensed cellular networks in TV white spaces","type":"conference","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","page":"2 - 14","abstract":[{"text":"In this paper we study network architecture for unlicensed cellular networking for outdoor coverage in TV white spaces. The main technology proposed for TV white spaces is 802.11af, a Wi-Fi variant adapted for TV frequencies. However, 802.11af is originally designed for improved indoor propagation. We show that long links, typical for outdoor use, exacerbate known Wi-Fi issues, such as hidden and exposed terminal, and significantly reduce its efficiency. Instead, we propose CellFi, an alternative architecture based on LTE. LTE is designed for long-range coverage and throughput efficiency, but it is also designed to operate in tightly controlled and centrally managed networks. CellFi overcomes these problems by designing an LTE-compatible spectrum database component, mandatory for TV white space networking, and introducing an interference management component for distributed coordination. CellFi interference management is compatible with existing LTE mechanisms, requires no explicit communication between base stations, and is more efficient than CSMA for long links. We evaluate our design through extensive real world evaluation on of-the-shelf LTE equipment and simulations. We show that, compared to 802.11af, it increases coverage by 40% and reduces median flow completion times by 2.3x.","lang":"eng"}],"date_published":"2017-11-28T00:00:00Z","date_created":"2018-12-11T11:46:45Z","article_processing_charge":"No","status":"public","external_id":{"isi":["000526087500002"]},"publication_identifier":{"isbn":["978-145035422-6"]},"publication":"Proceedings of the 2017 13th International Conference on emerging Networking EXperiments and Technologies","language":[{"iso":"eng"}],"isi":1,"year":"2017","quality_controlled":"1","author":[{"full_name":"Baig, Ghufran","first_name":"Ghufran","last_name":"Baig"},{"first_name":"Bozidar","full_name":"Radunovic, Bozidar","last_name":"Radunovic"},{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"},{"last_name":"Balkwill","first_name":"Matthew","full_name":"Balkwill, Matthew"},{"first_name":"Thomas","full_name":"Karagiannis, Thomas","last_name":"Karagiannis"},{"first_name":"Lili","full_name":"Qiu, Lili","last_name":"Qiu"}],"publist_id":"7333"},{"external_id":{"arxiv":["1610.02132"],"isi":["000452649401072"]},"date_created":"2018-12-11T11:46:26Z","date_published":"2017-01-01T00:00:00Z","article_processing_charge":"No","status":"public","page":"1710-1721","abstract":[{"text":"Parallel implementations of stochastic gradient descent (SGD) have received significant research attention, thanks to its excellent scalability properties. A fundamental barrier when parallelizing SGD is the high bandwidth cost of communicating gradient updates between nodes; consequently, several lossy compresion heuristics have been proposed, by which nodes only communicate quantized gradients. Although effective in practice, these heuristics do not always converge. In this paper, we propose Quantized SGD (QSGD), a family of compression schemes with convergence guarantees and good practical performance. QSGD allows the user to smoothly trade off communication bandwidth and convergence time: nodes can adjust the number of bits sent per iteration, at the cost of possibly higher variance. We show that this trade-off is inherent, in the sense that improving it past some threshold would violate information-theoretic lower bounds. QSGD guarantees convergence for convex and non-convex objectives, under asynchrony, and can be extended to stochastic variance-reduced techniques. When applied to training deep neural networks for image classification and automated speech recognition, QSGD leads to significant reductions in end-to-end training time. For instance, on 16GPUs, we can train the ResNet-152 network to full accuracy on ImageNet 1.8 × faster than the full-precision variant. ","lang":"eng"}],"quality_controlled":"1","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"},{"last_name":"Grubic","first_name":"Demjan","full_name":"Grubic, Demjan"},{"full_name":"Li, Jerry","first_name":"Jerry","last_name":"Li"},{"last_name":"Tomioka","first_name":"Ryota","full_name":"Tomioka, Ryota"},{"first_name":"Milan","full_name":"Vojnović, Milan","last_name":"Vojnović"}],"publist_id":"7392","publication_identifier":{"issn":["1049-5258"]},"language":[{"iso":"eng"}],"year":"2017","isi":1,"intvolume":"      2017","department":[{"_id":"DaAl"}],"arxiv":1,"publication_status":"published","publisher":"Neural Information Processing Systems Foundation","citation":{"ama":"Alistarh D-A, Grubic D, Li J, Tomioka R, Vojnović M. QSGD: Communication-efficient SGD via gradient quantization and encoding. In: Vol 2017. Neural Information Processing Systems Foundation; 2017:1710-1721.","short":"D.-A. Alistarh, D. Grubic, J. Li, R. Tomioka, M. Vojnović, in:, Neural Information Processing Systems Foundation, 2017, pp. 1710–1721.","chicago":"Alistarh, Dan-Adrian, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnović. “QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding,” 2017:1710–21. Neural Information Processing Systems Foundation, 2017.","mla":"Alistarh, Dan-Adrian, et al. <i>QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding</i>. Vol. 2017, Neural Information Processing Systems Foundation, 2017, pp. 1710–21.","ista":"Alistarh D-A, Grubic D, Li J, Tomioka R, Vojnović M. 2017. QSGD: Communication-efficient SGD via gradient quantization and encoding. NIPS: Neural Information Processing System, Advances in Neural Information Processing Systems, vol. 2017, 1710–1721.","apa":"Alistarh, D.-A., Grubic, D., Li, J., Tomioka, R., &#38; Vojnović, M. (2017). QSGD: Communication-efficient SGD via gradient quantization and encoding (Vol. 2017, pp. 1710–1721). Presented at the NIPS: Neural Information Processing System, Long Beach, CA, United States: Neural Information Processing Systems Foundation.","ieee":"D.-A. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnović, “QSGD: Communication-efficient SGD via gradient quantization and encoding,” presented at the NIPS: Neural Information Processing System, Long Beach, CA, United States, 2017, vol. 2017, pp. 1710–1721."},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1610.02132","open_access":"1"}],"oa_version":"Submitted Version","day":"01","conference":{"end_date":"2017-12-09","start_date":"2017-12-04","name":"NIPS: Neural Information Processing System","location":"Long Beach, CA, United States"},"volume":2017,"type":"conference","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","alternative_title":["Advances in Neural Information Processing Systems"],"title":"QSGD: Communication-efficient SGD via gradient quantization and encoding","month":"01","_id":"431","date_updated":"2025-09-18T10:07:20Z"},{"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","type":"conference","date_updated":"2025-09-18T10:06:02Z","_id":"432","month":"01","title":"ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning","ddc":["000"],"alternative_title":["PMLR Press"],"corr_author":"1","oa":1,"citation":{"ista":"Zhang H, Li J, Kara K, Alistarh D-A, Liu J, Zhang C. 2017. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. Proceedings of Machine Learning Research. ICML: International Conference on Machine Learning, PMLR Press, vol. 70, 4035–4043.","apa":"Zhang, H., Li, J., Kara, K., Alistarh, D.-A., Liu, J., &#38; Zhang, C. (2017). ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. In <i>Proceedings of Machine Learning Research</i> (Vol. 70, pp. 4035–4043). Sydney, Australia: ML Research Press.","ieee":"H. Zhang, J. Li, K. Kara, D.-A. Alistarh, J. Liu, and C. Zhang, “ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning,” in <i>Proceedings of Machine Learning Research</i>, Sydney, Australia, 2017, vol. 70, pp. 4035–4043.","mla":"Zhang, Hantian, et al. “ZipML: Training Linear Models with End-to-End Low Precision, and a Little Bit of Deep Learning.” <i>Proceedings of Machine Learning Research</i>, vol. 70, ML Research Press, 2017, pp. 4035–43.","chicago":"Zhang, Hantian, Jerry Li, Kaan Kara, Dan-Adrian Alistarh, Ji Liu, and Ce Zhang. “ZipML: Training Linear Models with End-to-End Low Precision, and a Little Bit of Deep Learning.” In <i>Proceedings of Machine Learning Research</i>, 70:4035–43. ML Research Press, 2017.","ama":"Zhang H, Li J, Kara K, Alistarh D-A, Liu J, Zhang C. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. In: <i>Proceedings of Machine Learning Research</i>. Vol 70. ML Research Press; 2017:4035-4043.","short":"H. Zhang, J. Li, K. Kara, D.-A. Alistarh, J. Liu, C. Zhang, in:, Proceedings of Machine Learning Research, ML Research Press, 2017, pp. 4035–4043."},"publisher":"ML Research Press","publication_status":"published","department":[{"_id":"DaAl"}],"scopus_import":"1","volume":" 70","has_accepted_license":"1","conference":{"end_date":"2017-08-11","start_date":"2017-08-06","location":"Sydney, Australia","name":"ICML: International Conference on Machine Learning"},"day":"01","oa_version":"Submitted Version","publist_id":"7391","author":[{"last_name":"Zhang","full_name":"Zhang, Hantian","first_name":"Hantian"},{"full_name":"Li, Jerry","first_name":"Jerry","last_name":"Li"},{"first_name":"Kaan","full_name":"Kara, Kaan","last_name":"Kara"},{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"},{"first_name":"Ji","full_name":"Liu, Ji","last_name":"Liu"},{"last_name":"Zhang","first_name":"Ce","full_name":"Zhang, Ce"}],"quality_controlled":"1","language":[{"iso":"eng"}],"year":"2017","isi":1,"publication":"Proceedings of Machine Learning Research","publication_identifier":{"isbn":["978-151085514-4"]},"file_date_updated":"2020-07-14T12:46:26Z","status":"public","article_processing_charge":"No","date_published":"2017-01-01T00:00:00Z","date_created":"2018-12-11T11:46:26Z","external_id":{"isi":["000683309504015"]},"abstract":[{"lang":"eng","text":"Recently there has been significant interest in training machine-learning models at low precision: by reducing precision, one can reduce computation and communication by one order of magnitude. We examine training at reduced precision, both from a theoretical and practical perspective, and ask: is it possible to train models at end-to-end low precision with provable guarantees? Can this lead to consistent order-of-magnitude speedups? We mainly focus on linear models, and the answer is yes for linear models. We develop a simple framework called ZipML based on one simple but novel strategy called double sampling. Our ZipML framework is able to execute training at low precision with no bias, guaranteeing convergence, whereas naive quanti- zation would introduce significant bias. We val- idate our framework across a range of applica- tions, and show that it enables an FPGA proto- type that is up to 6.5 × faster than an implemen- tation using full 32-bit precision. We further de- velop a variance-optimal stochastic quantization strategy and show that it can make a significant difference in a variety of settings. When applied to linear models together with double sampling, we save up to another 1.7 × in data movement compared with uniform quantization. When training deep networks with quantized models, we achieve higher accuracy than the state-of-the- art XNOR-Net. "}],"page":"4035 - 4043","file":[{"file_size":849345,"date_updated":"2020-07-14T12:46:26Z","file_id":"5869","creator":"dernst","access_level":"open_access","content_type":"application/pdf","checksum":"86156ba7f4318e47cef3eb9092593c10","file_name":"2017_ICML_Zhang.pdf","date_created":"2019-01-22T08:23:58Z","relation":"main_file"}]}]