[{"date_updated":"2025-04-15T06:53:15Z","quality_controlled":"1","fulldoi":"https://doi.org/10.1007/s00446-018-0342-6","isi":1,"oa_version":"Published Version","day":"12","year":"2018","corr_author":"1","title":"Near-optimal self-stabilising counting and firing squads","doi":"10.1007/s00446-018-0342-6","publisher":"Springer","_id":"76","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","month":"09","date_created":"2018-12-11T11:44:30Z","type":"journal_article","author":[{"full_name":"Lenzen, Christoph","first_name":"Christoph","last_name":"Lenzen"},{"orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","first_name":"Joel","last_name":"Rybicki","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"}],"file_date_updated":"2020-07-14T12:48:01Z","citation":{"chicago":"Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting and Firing Squads.” <i>Distributed Computing</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s00446-018-0342-6\">https://doi.org/10.1007/s00446-018-0342-6</a>.","mla":"Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting and Firing Squads.” <i>Distributed Computing</i>, Springer, 2018, doi:<a href=\"https://doi.org/10.1007/s00446-018-0342-6\">10.1007/s00446-018-0342-6</a>.","ama":"Lenzen C, Rybicki J. Near-optimal self-stabilising counting and firing squads. <i>Distributed Computing</i>. 2018. doi:<a href=\"https://doi.org/10.1007/s00446-018-0342-6\">10.1007/s00446-018-0342-6</a>","ieee":"C. Lenzen and J. Rybicki, “Near-optimal self-stabilising counting and firing squads,” <i>Distributed Computing</i>. Springer, 2018.","ista":"Lenzen C, Rybicki J. 2018. Near-optimal self-stabilising counting and firing squads. Distributed Computing.","short":"C. Lenzen, J. Rybicki, Distributed Computing (2018).","apa":"Lenzen, C., &#38; Rybicki, J. (2018). Near-optimal self-stabilising counting and firing squads. <i>Distributed Computing</i>. Springer. <a href=\"https://doi.org/10.1007/s00446-018-0342-6\">https://doi.org/10.1007/s00446-018-0342-6</a>"},"file":[{"content_type":"application/pdf","file_name":"2018_DistributedComputing_Lenzen.pdf","access_level":"open_access","file_size":799337,"creator":"dernst","date_updated":"2020-07-14T12:48:01Z","relation":"main_file","date_created":"2018-12-17T14:21:22Z","checksum":"872db70bba9b401500abe3c6ae2f1a61","file_id":"5711"}],"project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"publication_status":"published","publist_id":"7978","publication":"Distributed Computing","status":"public","ddc":["000"],"scopus_import":"1","has_accepted_license":"1","abstract":[{"lang":"eng","text":"Consider a fully-connected synchronous distributed system consisting of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous C-counting problem, all nodes need to eventually agree on a counter that is increased by one modulo C in each round for given C&gt;1. In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience f&lt;n/3, asymptotically optimal stabilisation and response time O(f), and message size O(log f). As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions."}],"date_published":"2018-09-12T00:00:00Z","department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"external_id":{"isi":["000475627800005"]},"oa":1,"article_processing_charge":"Yes (via OA deal)"},{"scopus_import":"1","has_accepted_license":"1","ddc":["000"],"status":"public","publication":"6th International Conference on Learning Representations","article_processing_charge":"No","external_id":{"arxiv":["1802.05668"]},"oa":1,"language":[{"iso":"eng"}],"date_published":"2018-05-01T00:00:00Z","department":[{"_id":"DaAl"}],"abstract":[{"lang":"eng","text":"Deep neural networks (DNNs) continue to make significant advances, solving tasks from image classification to translation or reinforcement learning. One aspect of the field receiving considerable attention is efficiently executing deep models in resource-constrained environments, such as mobile or embedded devices. This paper focuses on this problem, and proposes two new compression methods, which jointly leverage weight quantization and distillation of larger teacher networks into smaller student networks. The first method we propose is called quantized distillation and leverages distillation during the training process, by incorporating distillation loss, expressed with respect to the teacher, into the training of a student network whose weights are quantized to a limited set of levels. The second method,  differentiable quantization, optimizes the location of quantization points through stochastic gradient descent, to better fit the behavior of the teacher model.  We validate both methods through experiments on convolutional and recurrent architectures. We show that quantized shallow students can reach similar accuracy levels to full-precision teacher models, while providing order of magnitude compression, and inference speedup that is linear in the depth reduction. In sum, our results enable DNNs for resource-constrained environments to leverage architecture and accuracy advances developed on more powerful devices."}],"arxiv":1,"file_date_updated":"2020-07-14T12:48:03Z","author":[{"last_name":"Polino","first_name":"Antonio","full_name":"Polino, Antonio"},{"last_name":"Pascanu","first_name":"Razvan","full_name":"Pascanu, Razvan"},{"last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian"}],"type":"conference","date_created":"2020-05-10T22:00:51Z","publication_status":"published","file":[{"file_size":308339,"access_level":"open_access","creator":"dernst","content_type":"application/pdf","file_name":"2018_ICLR_Polino.pdf","date_updated":"2020-07-14T12:48:03Z","file_id":"7894","checksum":"a4336c167978e81891970e4e4517a8c3","date_created":"2020-05-26T13:02:00Z","relation":"main_file"}],"citation":{"ista":"Polino A, Pascanu R, Alistarh D-A. 2018. Model compression via distillation and quantization. 6th International Conference on Learning Representations. ICLR: International Conference on Learning Representations.","ama":"Polino A, Pascanu R, Alistarh D-A. Model compression via distillation and quantization. In: <i>6th International Conference on Learning Representations</i>. ; 2018.","chicago":"Polino, Antonio, Razvan Pascanu, and Dan-Adrian Alistarh. “Model Compression via Distillation and Quantization.” In <i>6th International Conference on Learning Representations</i>, 2018.","mla":"Polino, Antonio, et al. “Model Compression via Distillation and Quantization.” <i>6th International Conference on Learning Representations</i>, 2018.","ieee":"A. Polino, R. Pascanu, and D.-A. Alistarh, “Model compression via distillation and quantization,” in <i>6th International Conference on Learning Representations</i>, Vancouver, Canada, 2018.","apa":"Polino, A., Pascanu, R., &#38; Alistarh, D.-A. (2018). Model compression via distillation and quantization. In <i>6th International Conference on Learning Representations</i>. Vancouver, Canada.","short":"A. Polino, R. Pascanu, D.-A. Alistarh, in:, 6th International Conference on Learning Representations, 2018."},"conference":{"location":"Vancouver, Canada","end_date":"2018-05-03","start_date":"2018-04-30","name":"ICLR: International Conference on Learning Representations"},"acknowledgement":"We would like to thank Ce Zhang (ETH Zurich), Hantian Zhang (ETH Zurich) and Martin Jaggi ´\r\n(EPFL) for their support with experiments and valuable feedback.\r\n","_id":"7812","title":"Model compression via distillation and quantization","year":"2018","day":"01","month":"05","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","date_updated":"2025-06-30T10:04:44Z","oa_version":"Published Version"},{"file_date_updated":"2020-07-14T12:48:14Z","type":"conference","alternative_title":["LNCS"],"author":[{"full_name":"Gilad, Eran","first_name":"Eran","last_name":"Gilad"},{"full_name":"Brown, Trevor A","first_name":"Trevor A","last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Oskin","first_name":"Mark","full_name":"Oskin, Mark"},{"last_name":"Etsion","full_name":"Etsion, Yoav","first_name":"Yoav"}],"page":"465 - 479","date_created":"2018-12-11T11:44:33Z","publication_status":"published","project":[{"name":"NSERC Postdoctoral fellowship","_id":"26450934-B435-11E9-9278-68D0E5697425"}],"citation":{"short":"E. Gilad, T.A. Brown, M. Oskin, Y. Etsion, in:, Springer, 2018, 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>","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.","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>.","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>.","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>","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."},"file":[{"date_updated":"2020-07-14T12:48:14Z","file_id":"5954","checksum":"13a3f250be8878405e791b53c19722ad","relation":"main_file","date_created":"2019-02-12T07:40:40Z","content_type":"application/pdf","file_name":"2018_Brown.pdf","file_size":665372,"access_level":"open_access","creator":"dernst"}],"conference":{"end_date":"2018-08-31","location":"Turin, Italy","name":"Euro-Par: European Conference on Parallel Processing","start_date":"2018-08-27"},"ddc":["000"],"has_accepted_license":"1","scopus_import":"1","publist_id":"7969","status":"public","external_id":{"isi":["000851042300031"]},"oa":1,"language":[{"iso":"eng"}],"article_processing_charge":"No","intvolume":"     11014","abstract":[{"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.","lang":"eng"}],"date_published":"2018-08-01T00:00:00Z","department":[{"_id":"DaAl"}],"fulldoi":"https://doi.org/10.1007/978-3-319-96983-1_33","publication_identifier":{"issn":["0302-9743"]},"quality_controlled":"1","date_updated":"2026-04-16T09:53:41Z","volume":11014,"oa_version":"Preprint","isi":1,"doi":"10.1007/978-3-319-96983-1_33","acknowledgement":"Trevor Brown was supported in part by the ISF (grants 2005/17 & 1749/14) and by a NSERC post-doctoral fellowship.","_id":"85","publisher":"Springer","title":"Snapshot based synchronization: A fast replacement for Hand-over-Hand locking","day":"01","year":"2018","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","month":"08"},{"volume":2018,"date_updated":"2026-06-18T19:08:25Z","quality_controlled":"1","isi":1,"oa_version":"Published Version","day":"01","year":"2018","title":"Byzantine stochastic gradient descent","publisher":"Neural Information Processing Systems Foundation","_id":"6558","month":"12","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"4613-4623","date_created":"2019-06-13T08:22:37Z","type":"conference","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"full_name":"Allen-Zhu, Zeyuan","first_name":"Zeyuan","last_name":"Allen-Zhu"},{"first_name":"Jerry","full_name":"Li, Jerry","last_name":"Li"}],"conference":{"name":"NeurIPS: Conference on Neural Information Processing Systems","start_date":"2018-12-02","end_date":"2018-12-08","location":"Montreal, Canada"},"citation":{"apa":"Alistarh, D.-A., Allen-Zhu, Z., &#38; Li, J. (2018). Byzantine stochastic gradient descent. In <i>Advances in Neural Information Processing Systems</i> (Vol. 2018, pp. 4613–4623). Montreal, Canada: Neural Information Processing Systems Foundation.","short":"D.-A. Alistarh, Z. Allen-Zhu, J. Li, in:, Advances in Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2018, pp. 4613–4623.","ista":"Alistarh D-A, Allen-Zhu Z, Li J. 2018. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems. NeurIPS: Conference on Neural Information Processing Systems vol. 2018, 4613–4623.","mla":"Alistarh, Dan-Adrian, et al. “Byzantine Stochastic Gradient Descent.” <i>Advances in Neural Information Processing Systems</i>, vol. 2018, Neural Information Processing Systems Foundation, 2018, pp. 4613–23.","ama":"Alistarh D-A, Allen-Zhu Z, Li J. Byzantine stochastic gradient descent. In: <i>Advances in Neural Information Processing Systems</i>. Vol 2018. Neural Information Processing Systems Foundation; 2018:4613-4623.","ieee":"D.-A. Alistarh, Z. Allen-Zhu, and J. Li, “Byzantine stochastic gradient descent,” in <i>Advances in Neural Information Processing Systems</i>, Montreal, Canada, 2018, vol. 2018, pp. 4613–4623.","chicago":"Alistarh, Dan-Adrian, Zeyuan Allen-Zhu, and Jerry Li. “Byzantine Stochastic Gradient Descent.” In <i>Advances in Neural Information Processing Systems</i>, 2018:4613–23. Neural Information Processing Systems Foundation, 2018."},"publication_status":"published","publication":"Advances in Neural Information Processing Systems","status":"public","ddc":["000"],"scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1803.08917","open_access":"1"}],"arxiv":1,"abstract":[{"text":"This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of m machines which allegedly compute stochastic gradients every iteration, an α-fraction are Byzantine, and may behave adversarially. Our main result is a variant of stochastic gradient descent (SGD) which finds ε-approximate minimizers of convex functions in T=O~(1/ε²m+α²/ε²) iterations. In contrast, traditional mini-batch SGD needs T=O(1/ε²m) iterations, but cannot tolerate Byzantine failures. Further, we provide a lower bound showing that, up to logarithmic factors, our algorithm is information-theoretically optimal both in terms of sample complexity and time complexity.","lang":"eng"}],"intvolume":"      2018","department":[{"_id":"DaAl"}],"date_published":"2018-12-01T00:00:00Z","oa":1,"external_id":{"arxiv":["1803.08917"],"isi":["000461823304061"]},"language":[{"iso":"eng"}],"article_processing_charge":"No"},{"day":"26","year":"2018","corr_author":"1","title":"Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study","doi":"10.5441/002/EDBT.2018.14","publisher":"OpenProceedings","_id":"7116","tmp":{"short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"03","date_updated":"2024-10-09T20:59:05Z","quality_controlled":"1","publication_identifier":{"isbn":["9783893180783"],"issn":["2367-2005"]},"fulldoi":"https://doi.org/10.5441/002/EDBT.2018.14","oa_version":"Published Version","status":"public","publication":"Proceedings of the 21st International Conference on Extending Database Technology","ddc":["000"],"scopus_import":1,"has_accepted_license":"1","abstract":[{"lang":"eng","text":"Training deep learning models has received tremendous research interest recently. In particular, there has been intensive research on reducing the communication cost of training when using multiple computational devices, through reducing the precision of the underlying data representation. Naturally, such methods induce system trade-offs—lowering communication precision could de-crease communication overheads and improve scalability; but, on the other hand, it can also reduce the accuracy of training. In this paper, we study this trade-off space, and ask:Can low-precision communication consistently improve the end-to-end performance of training modern neural networks, with no accuracy loss?From the performance point of view, the answer to this question may appear deceptively easy: compressing communication through low precision should help when the ratio between communication and computation is high. However, this answer is less straightforward when we try to generalize this principle across various neural network architectures (e.g., AlexNet vs. ResNet),number of GPUs (e.g., 2 vs. 8 GPUs), machine configurations(e.g., EC2 instances vs. NVIDIA DGX-1), communication primitives (e.g., MPI vs. NCCL), and even different GPU architectures(e.g., Kepler vs. Pascal). Currently, it is not clear how a realistic realization of all these factors maps to the speed up provided by low-precision communication. In this paper, we conduct an empirical study to answer this question and report the insights."}],"date_published":"2018-03-26T00:00:00Z","department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"oa":1,"article_processing_charge":"No","page":"145-156","date_created":"2019-11-26T14:19:11Z","type":"conference","author":[{"first_name":"Demjan","full_name":"Grubic, Demjan","last_name":"Grubic"},{"first_name":"Leo","full_name":"Tam, Leo","last_name":"Tam"},{"last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian"},{"last_name":"Zhang","full_name":"Zhang, Ce","first_name":"Ce"}],"file_date_updated":"2020-07-14T12:47:49Z","conference":{"start_date":"2018-03-26","name":"EDBT: Conference on Extending Database Technology","end_date":"2018-03-29","location":"Vienna, Austria"},"citation":{"short":"D. Grubic, L. Tam, D.-A. Alistarh, C. Zhang, in:, Proceedings of the 21st International Conference on Extending Database Technology, OpenProceedings, 2018, pp. 145–156.","apa":"Grubic, D., Tam, L., Alistarh, D.-A., &#38; Zhang, C. (2018). Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study. In <i>Proceedings of the 21st International Conference on Extending Database Technology</i> (pp. 145–156). Vienna, Austria: OpenProceedings. <a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">https://doi.org/10.5441/002/EDBT.2018.14</a>","mla":"Grubic, Demjan, et al. “Synchronous Multi-GPU Training for Deep Learning with Low-Precision Communications: An Empirical Study.” <i>Proceedings of the 21st International Conference on Extending Database Technology</i>, OpenProceedings, 2018, pp. 145–56, doi:<a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">10.5441/002/EDBT.2018.14</a>.","chicago":"Grubic, Demjan, Leo Tam, Dan-Adrian Alistarh, and Ce Zhang. “Synchronous Multi-GPU Training for Deep Learning with Low-Precision Communications: An Empirical Study.” In <i>Proceedings of the 21st International Conference on Extending Database Technology</i>, 145–56. OpenProceedings, 2018. <a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">https://doi.org/10.5441/002/EDBT.2018.14</a>.","ama":"Grubic D, Tam L, Alistarh D-A, Zhang C. Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study. In: <i>Proceedings of the 21st International Conference on Extending Database Technology</i>. OpenProceedings; 2018:145-156. doi:<a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">10.5441/002/EDBT.2018.14</a>","ieee":"D. Grubic, L. Tam, D.-A. Alistarh, and C. Zhang, “Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study,” in <i>Proceedings of the 21st International Conference on Extending Database Technology</i>, Vienna, Austria, 2018, pp. 145–156.","ista":"Grubic D, Tam L, Alistarh D-A, Zhang C. 2018. Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study. Proceedings of the 21st International Conference on Extending Database Technology. EDBT: Conference on Extending Database Technology, 145–156."},"file":[{"file_size":1603204,"access_level":"open_access","creator":"dernst","file_name":"2018_OpenProceedings_Grubic.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:47:49Z","file_id":"7118","checksum":"ec979b56abc71016d6e6adfdadbb4afe","date_created":"2019-11-26T14:23:04Z","relation":"main_file"}],"publication_status":"published"},{"citation":{"short":"D.-A. Alistarh, J. Aspnes, R. Gelashvili, in:, Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, 2018, pp. 2221–2239.","apa":"Alistarh, D.-A., Aspnes, J., &#38; Gelashvili, R. (2018). Space-optimal majority in population protocols. In <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 2221–2239). New Orleans, LA, United States: ACM. <a href=\"https://doi.org/10.1137/1.9781611975031.144\">https://doi.org/10.1137/1.9781611975031.144</a>","chicago":"Alistarh, Dan-Adrian, James Aspnes, and Rati Gelashvili. “Space-Optimal Majority in Population Protocols.” In <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2221–39. ACM, 2018. <a href=\"https://doi.org/10.1137/1.9781611975031.144\">https://doi.org/10.1137/1.9781611975031.144</a>.","ieee":"D.-A. Alistarh, J. Aspnes, and R. Gelashvili, “Space-optimal majority in population protocols,” in <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, New Orleans, LA, United States, 2018, pp. 2221–2239.","ama":"Alistarh D-A, Aspnes J, Gelashvili R. Space-optimal majority in population protocols. In: <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. ACM; 2018:2221-2239. doi:<a href=\"https://doi.org/10.1137/1.9781611975031.144\">10.1137/1.9781611975031.144</a>","mla":"Alistarh, Dan-Adrian, et al. “Space-Optimal Majority in Population Protocols.” <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, ACM, 2018, pp. 2221–39, doi:<a href=\"https://doi.org/10.1137/1.9781611975031.144\">10.1137/1.9781611975031.144</a>.","ista":"Alistarh D-A, Aspnes J, Gelashvili R. 2018. Space-optimal majority in population protocols. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2221–2239."},"conference":{"start_date":"2018-01-07","name":"SODA: Symposium on Discrete Algorithms","end_date":"2018-01-10","location":"New Orleans, LA, United States"},"publication_status":"published","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"last_name":"Aspnes","first_name":"James","full_name":"Aspnes, James"},{"last_name":"Gelashvili","first_name":"Rati","full_name":"Gelashvili, Rati"}],"type":"conference","date_created":"2019-11-26T15:10:55Z","page":"2221-2239","arxiv":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1704.04947"}],"article_processing_charge":"No","external_id":{"arxiv":["1704.04947"],"isi":["000483921200145"]},"language":[{"iso":"eng"}],"oa":1,"date_published":"2018-01-30T00:00:00Z","department":[{"_id":"DaAl"}],"abstract":[{"lang":"eng","text":"Population protocols are a popular model of distributed computing, in which n agents with limited local state interact randomly, and cooperate to collectively compute global predicates. Inspired by recent developments in DNA programming, an extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. Majority, or consensus, is a central task in this model, in which agents need to collectively reach a decision as to which one of two states A or B had a higher initial count. Two metrics are important: the time that a protocol requires to stabilize to an output decision, and the state space size that each agent requires to do so. It is known that majority requires Ω(log log n) states per agent to allow for fast (poly-logarithmic time) stabilization, and that O(log2 n) states are sufficient. Thus, there is an exponential gap between the space upper and lower bounds for this problem. This paper addresses this question.\r\n\r\nOn the negative side, we provide a new lower bound of Ω(log n) states for any protocol which stabilizes in O(n1–c) expected time, for any constant c > 0. This result is conditional on monotonicity and output assumptions, satisfied by all known protocols. Technically, it represents a departure from previous lower bounds, in that it does not rely on the existence of dense configurations. Instead, we introduce a new generalized surgery technique to prove the existence of incorrect executions for any algorithm which would contradict the lower bound. Subsequently, our lower bound also applies to general initial configurations, including ones with a leader. On the positive side, we give a new algorithm for majority which uses O(log n) states, and stabilizes in O(log2 n) expected time. Central to the algorithm is a new leaderless phase clock technique, which allows agents to synchronize in phases of Θ(n log n) consecutive interactions using O(log n) states per agent, exploiting a new connection between population protocols and power-of-two-choices load balancing mechanisms. We also employ our phase clock to build a leader election algorithm with a state space of size O(log n), which stabilizes in O(log2 n) expected time."}],"publication":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms","status":"public","scopus_import":"1","isi":1,"oa_version":"Preprint","date_updated":"2024-10-21T06:02:41Z","fulldoi":"https://doi.org/10.1137/1.9781611975031.144","publication_identifier":{"isbn":["9781611975031"]},"quality_controlled":"1","month":"01","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"Space-optimal majority in population protocols","year":"2018","day":"30","publisher":"ACM","_id":"7123","doi":"10.1137/1.9781611975031.144"},{"fulldoi":"https://doi.org/10.1145/3178487.3178489","publication_identifier":{"isbn":["978-1-4503-4982-6"]},"quality_controlled":"1","date_updated":"2023-09-11T14:10:25Z","volume":53,"oa_version":"None","isi":1,"doi":"10.1145/3178487.3178489","_id":"397","publisher":"ACM","title":"Harnessing epoch-based reclamation for efficient range queries","day":"10","year":"2018","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","month":"02","alternative_title":["PPoPP"],"type":"conference","author":[{"last_name":"Arbel Raviv","full_name":"Arbel Raviv, Maya","first_name":"Maya"},{"full_name":"Brown, Trevor A","first_name":"Trevor A","last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87"}],"issue":"1","page":"14 - 27","date_created":"2018-12-11T11:46:14Z","publication_status":"published","citation":{"chicago":"Arbel Raviv, Maya, and Trevor A Brown. “Harnessing Epoch-Based Reclamation for Efficient Range Queries,” 53:14–27. ACM, 2018. <a href=\"https://doi.org/10.1145/3178487.3178489\">https://doi.org/10.1145/3178487.3178489</a>.","ama":"Arbel Raviv M, Brown TA. Harnessing epoch-based reclamation for efficient range queries. In: Vol 53. ACM; 2018:14-27. doi:<a href=\"https://doi.org/10.1145/3178487.3178489\">10.1145/3178487.3178489</a>","ieee":"M. Arbel Raviv and T. A. Brown, “Harnessing epoch-based reclamation for efficient range queries,” presented at the PPoPP: Principles and Practice of Parallel Programming, Vienna, Austria, 2018, vol. 53, no. 1, pp. 14–27.","mla":"Arbel Raviv, Maya, and Trevor A. Brown. <i>Harnessing Epoch-Based Reclamation for Efficient Range Queries</i>. Vol. 53, no. 1, ACM, 2018, pp. 14–27, doi:<a href=\"https://doi.org/10.1145/3178487.3178489\">10.1145/3178487.3178489</a>.","ista":"Arbel Raviv M, Brown TA. 2018. Harnessing epoch-based reclamation for efficient range queries. PPoPP: Principles and Practice of Parallel Programming, PPoPP, vol. 53, 14–27.","short":"M. Arbel Raviv, T.A. Brown, in:, ACM, 2018, pp. 14–27.","apa":"Arbel Raviv, M., &#38; Brown, T. A. (2018). Harnessing epoch-based reclamation for efficient range queries (Vol. 53, pp. 14–27). Presented at the PPoPP: Principles and Practice of Parallel Programming, Vienna, Austria: ACM. <a href=\"https://doi.org/10.1145/3178487.3178489\">https://doi.org/10.1145/3178487.3178489</a>"},"conference":{"start_date":"2018-02-24","name":"PPoPP: Principles and Practice of Parallel Programming","end_date":"2018-02-28","location":"Vienna, Austria"},"scopus_import":"1","status":"public","publist_id":"7430","language":[{"iso":"eng"}],"external_id":{"isi":["000446161100002"]},"article_processing_charge":"No","abstract":[{"text":"Concurrent sets with range query operations are highly desirable in applications such as in-memory databases. However, few set implementations offer range queries. Known techniques for augmenting data structures with range queries (or operations that can be used to build range queries) have numerous problems that limit their usefulness. For example, they impose high overhead or rely heavily on garbage collection. In this work, we show how to augment data structures with highly efficient range queries, without relying on garbage collection. We identify a property of epoch-based memory reclamation algorithms that makes them ideal for implementing range queries, and produce three algorithms, which use locks, transactional memory and lock-free techniques, respectively. Our algorithms are applicable to more data structures than previous work, and are shown to be highly efficient on a large scale Intel system. ","lang":"eng"}],"intvolume":"        53","department":[{"_id":"DaAl"}],"date_published":"2018-02-10T00:00:00Z"},{"date_created":"2018-12-11T11:44:19Z","page":"10690 - 10695","issue":"42","author":[{"full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","first_name":"Joel","last_name":"Rybicki","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kisdi, Eva","first_name":"Eva","last_name":"Kisdi"},{"last_name":"Anttila","first_name":"Jani","full_name":"Anttila, Jani"}],"type":"journal_article","file_date_updated":"2020-07-14T12:46:26Z","file":[{"date_updated":"2020-07-14T12:46:26Z","relation":"main_file","date_created":"2019-04-09T08:02:50Z","file_id":"6258","checksum":"df7ac544a587c06b75692653b9fabd18","access_level":"open_access","file_size":4070777,"creator":"dernst","content_type":"application/pdf","file_name":"2018_PNAS_Rybicki.pdf"}],"pubrep_id":"1063","citation":{"short":"J. Rybicki, E. Kisdi, J. Anttila, Proceedings of the National Academy of Sciences of the United States of America 115 (2018) 10690–10695.","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>","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.","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>.","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>."},"project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"publication_status":"published","status":"public","publication":"Proceedings of the National Academy of Sciences of the United States of America","publist_id":"8011","scopus_import":"1","has_accepted_license":"1","ddc":["570","577"],"department":[{"_id":"DaAl"}],"date_published":"2018-10-02T00:00:00Z","intvolume":"       115","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."}],"ec_funded":1,"article_processing_charge":"No","external_id":{"isi":["000447491300057"]},"oa":1,"language":[{"iso":"eng"}],"volume":115,"date_updated":"2025-06-03T11:16:28Z","publication_identifier":{"issn":["0027-8424"],"eissn":["1091-6490"]},"quality_controlled":"1","fulldoi":"https://doi.org/10.1073/pnas.1721061115","isi":1,"oa_version":"Submitted Version","year":"2018","day":"02","title":"Model of bacterial toxin-dependent pathogenesis explains infective dose","publisher":"National Academy of Sciences","_id":"43","acknowledgement":"J.R. and J.V.A. were also supported by the Academy of Finland Grants 1273253 and 267541.","doi":"10.1073/pnas.1721061115","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"10"},{"author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X"},{"first_name":"Torsten","full_name":"Hoefler, Torsten","last_name":"Hoefler"},{"first_name":"Mikael","full_name":"Johansson, Mikael","last_name":"Johansson"},{"id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87","last_name":"Konstantinov","first_name":"Nikola H","orcid":"0009-0009-5204-7621","full_name":"Konstantinov, Nikola H"},{"first_name":"Sarit","full_name":"Khirirat, Sarit","last_name":"Khirirat"},{"first_name":"Cedric","full_name":"Renggli, Cedric","last_name":"Renggli"}],"alternative_title":["Advances in Neural Information Processing Systems"],"type":"conference","date_created":"2019-06-27T09:32:55Z","page":"5973-5983","citation":{"mla":"Alistarh, Dan-Adrian, et al. “The Convergence of Sparsified Gradient Methods.” <i>32nd Conference on Neural Information Processing Systems</i>, Neural Information Processing Systems Foundation, 2018, pp. 5973–83.","chicago":"Alistarh, Dan-Adrian, Torsten Hoefler, Mikael Johansson, Nikola H Konstantinov, Sarit Khirirat, and Cedric Renggli. “The Convergence of Sparsified Gradient Methods.” In <i>32nd Conference on Neural Information Processing Systems</i>, 5973–83. Neural Information Processing Systems Foundation, 2018.","ama":"Alistarh D-A, Hoefler T, Johansson M, Konstantinov NH, Khirirat S, Renggli C. The convergence of sparsified gradient methods. In: <i>32nd Conference on Neural Information Processing Systems</i>. Neural Information Processing Systems Foundation; 2018:5973-5983.","ieee":"D.-A. Alistarh, T. Hoefler, M. Johansson, N. H. Konstantinov, S. Khirirat, and C. Renggli, “The convergence of sparsified gradient methods,” in <i>32nd Conference on Neural Information Processing Systems</i>, Montreal, Canada, 2018, pp. 5973–5983.","ista":"Alistarh D-A, Hoefler T, Johansson M, Konstantinov NH, Khirirat S, Renggli C. 2018. The convergence of sparsified gradient methods. 32nd Conference on Neural Information Processing Systems. NeurIPS: Conference on Neural Information Processing Systems, Advances in Neural Information Processing Systems, , 5973–5983.","short":"D.-A. Alistarh, T. Hoefler, M. Johansson, N.H. Konstantinov, S. Khirirat, C. Renggli, in:, 32nd Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2018, pp. 5973–5983.","apa":"Alistarh, D.-A., Hoefler, T., Johansson, M., Konstantinov, N. H., Khirirat, S., &#38; Renggli, C. (2018). The convergence of sparsified gradient methods. In <i>32nd Conference on Neural Information Processing Systems</i> (pp. 5973–5983). Montreal, Canada: Neural Information Processing Systems Foundation."},"conference":{"end_date":"2018-12-08","location":"Montreal, Canada","start_date":"2018-12-02","name":"NeurIPS: Conference on Neural Information Processing Systems"},"publication_status":"published","project":[{"grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"International IST Doctoral Program"}],"publication":"32nd Conference on Neural Information Processing Systems","status":"public","scopus_import":"1","arxiv":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1809.10505"}],"ec_funded":1,"article_processing_charge":"No","language":[{"iso":"eng"}],"oa":1,"external_id":{"arxiv":["1809.10505"],"isi":["000461852000047"]},"department":[{"_id":"DaAl"},{"_id":"ChLa"}],"date_published":"2018-12-01T00:00:00Z","abstract":[{"text":"Distributed training of massive machine learning models, in particular deep neural networks, via Stochastic Gradient Descent (SGD) is becoming commonplace. Several families of communication-reduction methods, such as quantization, large-batch methods, and gradient sparsification, have been proposed. To date, gradient sparsification methods--where each node sorts gradients by magnitude, and only communicates a subset of the components, accumulating the rest locally--are known to yield some of the largest practical gains. Such methods can reduce the amount of communication per step by up to \\emph{three orders of magnitude}, while preserving model accuracy. Yet, this family of methods currently has no theoretical justification. This is the question we address in this paper. We prove that, under analytic assumptions, sparsifying gradients by magnitude with local error correction provides convergence guarantees, for both convex and non-convex smooth objectives, for data-parallel SGD. The main insight is that sparsification methods implicitly maintain bounds on the maximum impact of stale updates, thanks to selection by magnitude. Our analysis and empirical validation also reveal that these methods do require analytical conditions to converge well, justifying existing heuristics.","lang":"eng"}],"das_tickbox":"1","date_updated":"2026-07-08T05:48:21Z","quality_controlled":"1","publication_identifier":{"issn":["1049-5258"]},"isi":1,"oa_version":"Preprint","title":"The convergence of sparsified gradient methods","corr_author":"1","year":"2018","day":"01","_id":"6589","publisher":"Neural Information Processing Systems Foundation","month":"12","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"type":"conference","author":[{"full_name":"Baig, Ghufran","first_name":"Ghufran","last_name":"Baig"},{"full_name":"Radunovic, Bozidar","first_name":"Bozidar","last_name":"Radunovic"},{"first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh"},{"last_name":"Balkwill","full_name":"Balkwill, Matthew","first_name":"Matthew"},{"full_name":"Karagiannis, Thomas","first_name":"Thomas","last_name":"Karagiannis"},{"full_name":"Qiu, Lili","first_name":"Lili","last_name":"Qiu"}],"page":"2 - 14","date_created":"2018-12-11T11:46:45Z","citation":{"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.","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>.","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.","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>.","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>","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."},"conference":{"end_date":"2017-12-15","location":"Incheon, South Korea","start_date":"2017-12-12","name":"CoNEXT: Conference on emerging Networking EXperiments and Technologies"},"publication_status":"published","publist_id":"7333","status":"public","publication":"Proceedings of the 2017 13th International Conference on emerging Networking EXperiments and Technologies","scopus_import":"1","language":[{"iso":"eng"}],"external_id":{"isi":["000526087500002"]},"article_processing_charge":"No","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","department":[{"_id":"DaAl"}],"date_updated":"2025-09-18T09:50:43Z","fulldoi":"https://doi.org/10.1145/3143361.3143367","publication_identifier":{"isbn":["978-145035422-6"]},"quality_controlled":"1","isi":1,"oa_version":"None","corr_author":"1","title":"Towards unlicensed cellular networks in TV white spaces","day":"28","year":"2017","doi":"10.1145/3143361.3143367","_id":"487","publisher":"ACM","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","month":"11"},{"page":"283 - 292","date_created":"2018-12-11T11:48:31Z","type":"conference","author":[{"last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian"},{"last_name":"Kopinsky","first_name":"Justin","full_name":"Kopinsky, Justin"},{"last_name":"Li","first_name":"Jerry","full_name":"Li, Jerry"},{"last_name":"Nadiradze","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","full_name":"Nadiradze, Giorgi","orcid":"0000-0001-5634-0731","first_name":"Giorgi"}],"publication_status":"published","conference":{"name":"PODC: Principles of Distributed Computing","start_date":"2017-07-25","location":"Washington, WA, USA","end_date":"2017-07-27"},"citation":{"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>.","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>.","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>","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.","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.","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.","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>"},"scopus_import":"1","status":"public","publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","publist_id":"6864","abstract":[{"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.","lang":"eng"}],"department":[{"_id":"DaAl"}],"date_published":"2017-07-26T00:00:00Z","oa":1,"external_id":{"isi":["000462995000035"],"arxiv":["1706.04178"]},"language":[{"iso":"eng"}],"article_processing_charge":"No","main_file_link":[{"url":"https://arxiv.org/abs/1706.04178","open_access":"1"}],"arxiv":1,"publication_identifier":{"isbn":["978-145034992-5"]},"quality_controlled":"1","fulldoi":"https://doi.org/10.1145/3087801.3087810","volume":"Part F129314","date_updated":"2025-06-04T09:44:47Z","oa_version":"Submitted Version","isi":1,"doi":"10.1145/3087801.3087810","publisher":"ACM","_id":"791","day":"26","year":"2017","title":"The power of choice in priority scheduling","month":"07","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"date_created":"2018-12-11T11:46:26Z","page":"1710-1721","author":[{"last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian"},{"first_name":"Demjan","full_name":"Grubic, Demjan","last_name":"Grubic"},{"last_name":"Li","first_name":"Jerry","full_name":"Li, Jerry"},{"full_name":"Tomioka, Ryota","first_name":"Ryota","last_name":"Tomioka"},{"full_name":"Vojnović, Milan","first_name":"Milan","last_name":"Vojnović"}],"type":"conference","alternative_title":["Advances in Neural Information Processing Systems"],"conference":{"name":"NIPS: Neural Information Processing System","start_date":"2017-12-04","end_date":"2017-12-09","location":"Long Beach, CA, United States"},"citation":{"short":"D.-A. Alistarh, D. Grubic, J. Li, R. Tomioka, M. Vojnović, in:, Neural Information Processing Systems Foundation, 2017, pp. 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.","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.","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.","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.","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.","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."},"publication_status":"published","publist_id":"7392","status":"public","main_file_link":[{"url":"https://arxiv.org/abs/1610.02132","open_access":"1"}],"arxiv":1,"department":[{"_id":"DaAl"}],"date_published":"2017-01-01T00:00:00Z","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"}],"intvolume":"      2017","article_processing_charge":"No","oa":1,"language":[{"iso":"eng"}],"external_id":{"isi":["000452649401072"],"arxiv":["1610.02132"]},"volume":2017,"date_updated":"2025-09-18T10:07:20Z","quality_controlled":"1","publication_identifier":{"issn":["1049-5258"]},"isi":1,"oa_version":"Submitted Version","year":"2017","day":"01","title":"QSGD: Communication-efficient SGD via gradient quantization and encoding","corr_author":"1","_id":"431","publisher":"Neural Information Processing Systems Foundation","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","month":"01"},{"file":[{"date_updated":"2020-07-14T12:46:26Z","file_id":"5869","checksum":"86156ba7f4318e47cef3eb9092593c10","relation":"main_file","date_created":"2019-01-22T08:23:58Z","file_size":849345,"access_level":"open_access","creator":"dernst","content_type":"application/pdf","file_name":"2017_ICML_Zhang.pdf"}],"citation":{"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.","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.","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.","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.","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.","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."},"conference":{"name":"ICML: International Conference on Machine Learning","start_date":"2017-08-06","location":"Sydney, Australia","end_date":"2017-08-11"},"publication_status":"published","author":[{"last_name":"Zhang","first_name":"Hantian","full_name":"Zhang, Hantian"},{"last_name":"Li","first_name":"Jerry","full_name":"Li, Jerry"},{"first_name":"Kaan","full_name":"Kara, Kaan","last_name":"Kara"},{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Liu, Ji","first_name":"Ji","last_name":"Liu"},{"full_name":"Zhang, Ce","first_name":"Ce","last_name":"Zhang"}],"type":"conference","alternative_title":["PMLR Press"],"date_created":"2018-12-11T11:46:26Z","page":"4035 - 4043","file_date_updated":"2020-07-14T12:46:26Z","article_processing_charge":"No","language":[{"iso":"eng"}],"oa":1,"external_id":{"isi":["000683309504015"]},"department":[{"_id":"DaAl"}],"date_published":"2017-01-01T00:00:00Z","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. "}],"publication":"Proceedings of Machine Learning Research","status":"public","publist_id":"7391","has_accepted_license":"1","scopus_import":"1","ddc":["000"],"isi":1,"oa_version":"Submitted Version","date_updated":"2025-09-18T10:06:02Z","volume":" 70","publication_identifier":{"isbn":["978-151085514-4"]},"quality_controlled":"1","month":"01","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning","corr_author":"1","year":"2017","day":"01","publisher":"ML Research Press","_id":"432"}]