[{"oa":1,"acknowledgement":"The authors sincerely thank Nikoli Dryden, Tal Ben-Nun, Torsten Hoefler and Bapi Chatterjee for useful discussions throughout the development of this project.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2111.08617"]},"date_created":"2023-03-31T06:17:00Z","_id":"12780","page":"241-254","publication":"Proceedings of the 23rd ACM/IFIP International Middleware Conference","file_date_updated":"2023-04-03T06:17:58Z","article_processing_charge":"Yes (via OA deal)","date_published":"2022-11-01T00:00:00Z","month":"11","title":"CGX: Adaptive system support for communication-efficient deep learning","date_updated":"2023-04-03T06:21:04Z","ddc":["000"],"citation":{"mla":"Markov, Ilia, et al. “CGX: Adaptive System Support for Communication-Efficient Deep Learning.” <i>Proceedings of the 23rd ACM/IFIP International Middleware Conference</i>, Association for Computing Machinery, 2022, pp. 241–54, doi:<a href=\"https://doi.org/10.1145/3528535.3565248\">10.1145/3528535.3565248</a>.","ista":"Markov I, Ramezanikebrya H, Alistarh D-A. 2022. CGX: Adaptive system support for communication-efficient deep learning. Proceedings of the 23rd ACM/IFIP International Middleware Conference. Middleware: International Middleware Conference, 241–254.","chicago":"Markov, Ilia, Hamidreza Ramezanikebrya, and Dan-Adrian Alistarh. “CGX: Adaptive System Support for Communication-Efficient Deep Learning.” In <i>Proceedings of the 23rd ACM/IFIP International Middleware Conference</i>, 241–54. Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3528535.3565248\">https://doi.org/10.1145/3528535.3565248</a>.","ama":"Markov I, Ramezanikebrya H, Alistarh D-A. CGX: Adaptive system support for communication-efficient deep learning. In: <i>Proceedings of the 23rd ACM/IFIP International Middleware Conference</i>. Association for Computing Machinery; 2022:241-254. doi:<a href=\"https://doi.org/10.1145/3528535.3565248\">10.1145/3528535.3565248</a>","ieee":"I. Markov, H. Ramezanikebrya, and D.-A. Alistarh, “CGX: Adaptive system support for communication-efficient deep learning,” in <i>Proceedings of the 23rd ACM/IFIP International Middleware Conference</i>, Quebec, QC, Canada, 2022, pp. 241–254.","short":"I. Markov, H. Ramezanikebrya, D.-A. Alistarh, in:, Proceedings of the 23rd ACM/IFIP International Middleware Conference, Association for Computing Machinery, 2022, pp. 241–254.","apa":"Markov, I., Ramezanikebrya, H., &#38; Alistarh, D.-A. (2022). CGX: Adaptive system support for communication-efficient deep learning. In <i>Proceedings of the 23rd ACM/IFIP International Middleware Conference</i> (pp. 241–254). Quebec, QC, Canada: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3528535.3565248\">https://doi.org/10.1145/3528535.3565248</a>"},"type":"conference","file":[{"checksum":"1a397746235f245da5468819247ff663","relation":"main_file","file_size":1514169,"date_updated":"2023-04-03T06:17:58Z","content_type":"application/pdf","file_name":"2022_ACMMiddleware_Markov.pdf","access_level":"open_access","success":1,"file_id":"12795","date_created":"2023-04-03T06:17:58Z","creator":"dernst"}],"quality_controlled":"1","has_accepted_license":"1","status":"public","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"The ability to scale out training workloads has been one of the key performance enablers of deep learning. The main scaling approach is data-parallel GPU-based training, which has been boosted by hardware and software support for highly efficient point-to-point communication, and in particular via hardware bandwidth over-provisioning. Overprovisioning comes at a cost: there is an order of magnitude price difference between \"cloud-grade\" servers with such support, relative to their popular \"consumer-grade\" counterparts, although single server-grade and consumer-grade GPUs can have similar computational envelopes.\r\n\r\nIn this paper, we show that the costly hardware overprovisioning approach can be supplanted via algorithmic and system design, and propose a framework called CGX, which provides efficient software support for compressed communication in ML applications, for both multi-GPU single-node training, as well as larger-scale multi-node training. CGX is based on two technical advances: At the system level, it relies on a re-developed communication stack for ML frameworks, which provides flexible, highly-efficient support for compressed communication. At the application level, it provides seamless, parameter-free integration with popular frameworks, so that end-users do not have to modify training recipes, nor significant training code. This is complemented by a layer-wise adaptive compression technique which dynamically balances compression gains with accuracy preservation. CGX integrates with popular ML frameworks, providing up to 3X speedups for multi-GPU nodes based on commodity hardware, and order-of-magnitude improvements in the multi-node setting, with negligible impact on accuracy."}],"publication_status":"published","day":"01","publisher":"Association for Computing Machinery","oa_version":"Published Version","arxiv":1,"doi":"10.1145/3528535.3565248","conference":{"start_date":"2022-11-07","location":"Quebec, QC, Canada","end_date":"2022-11-11","name":"Middleware: International Middleware Conference"},"year":"2022","author":[{"full_name":"Markov, Ilia","last_name":"Markov","first_name":"Ilia","id":"D0CF4148-C985-11E9-8066-0BDEE5697425"},{"first_name":"Hamidreza","full_name":"Ramezanikebrya, Hamidreza","last_name":"Ramezanikebrya"},{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_identifier":{"isbn":["9781450393409"]},"department":[{"_id":"DaAl"}]},{"date_created":"2023-05-23T17:05:40Z","day":"03","publisher":"Zenodo","_id":"13076","oa_version":"Published Version","doi":"10.5281/ZENODO.5733408","date_published":"2022-01-03T00:00:00Z","author":[{"last_name":"Postnikova","full_name":"Postnikova, Anastasiia","first_name":"Anastasiia"},{"last_name":"Koval","full_name":"Koval, Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita"},{"last_name":"Nadiradze","full_name":"Nadiradze, Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","first_name":"Giorgi"},{"last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"}],"article_processing_charge":"No","year":"2022","month":"01","date_updated":"2023-08-03T06:48:34Z","title":"Multi-queues can be state-of-the-art priority schedulers","department":[{"_id":"DaAl"}],"ddc":["510"],"type":"research_data_reference","citation":{"short":"A. Postnikova, N. Koval, G. Nadiradze, D.-A. Alistarh, (2022).","apa":"Postnikova, A., Koval, N., Nadiradze, G., &#38; Alistarh, D.-A. (2022). Multi-queues can be state-of-the-art priority schedulers. Zenodo. <a href=\"https://doi.org/10.5281/ZENODO.5733408\">https://doi.org/10.5281/ZENODO.5733408</a>","ieee":"A. Postnikova, N. Koval, G. Nadiradze, and D.-A. Alistarh, “Multi-queues can be state-of-the-art priority schedulers.” Zenodo, 2022.","chicago":"Postnikova, Anastasiia, Nikita Koval, Giorgi Nadiradze, and Dan-Adrian Alistarh. “Multi-Queues Can Be State-of-the-Art Priority Schedulers.” Zenodo, 2022. <a href=\"https://doi.org/10.5281/ZENODO.5733408\">https://doi.org/10.5281/ZENODO.5733408</a>.","ama":"Postnikova A, Koval N, Nadiradze G, Alistarh D-A. Multi-queues can be state-of-the-art priority schedulers. 2022. doi:<a href=\"https://doi.org/10.5281/ZENODO.5733408\">10.5281/ZENODO.5733408</a>","mla":"Postnikova, Anastasiia, et al. <i>Multi-Queues Can Be State-of-the-Art Priority Schedulers</i>. Zenodo, 2022, doi:<a href=\"https://doi.org/10.5281/ZENODO.5733408\">10.5281/ZENODO.5733408</a>.","ista":"Postnikova A, Koval N, Nadiradze G, Alistarh D-A. 2022. Multi-queues can be state-of-the-art priority schedulers, Zenodo, <a href=\"https://doi.org/10.5281/ZENODO.5733408\">10.5281/ZENODO.5733408</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"status":"public","abstract":[{"text":"The source code for replicating experiments presented in the paper.\r\n\r\nThe implementation of the designed priority schedulers can be found in Galois-2.2.1/include/Galois/WorkList/:\r\nStealingMultiQueue.h is the StealingMultiQueue.\r\nMQOptimized/ contains MQ Optimized variants.\r\n\r\nWe provide images that contain all the dependencies and datasets. Images can be pulled from npostnikova/mq-based-schedulers repository, or downloaded from Zenodo. See readme for more detail.","lang":"eng"}],"main_file_link":[{"url":"https://doi.org/10.5281/zenodo.5813846","open_access":"1"}],"related_material":{"record":[{"relation":"used_in_publication","status":"public","id":"11180"}],"link":[{"relation":"software","url":"https://github.com/npostnikova/mq-based-schedulers/tree/v1.1"}]}},{"citation":{"ista":"Postnikova A, Koval N, Nadiradze G, Alistarh D-A. 2022. Multi-queues can be state-of-the-art priority schedulers. Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPoPP: Sympopsium on Principles and Practice of Parallel Programming, 353–367.","mla":"Postnikova, Anastasiia, et al. “Multi-Queues Can Be State-of-the-Art Priority Schedulers.” <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Association for Computing Machinery, 2022, pp. 353–67, doi:<a href=\"https://doi.org/10.1145/3503221.3508432\">10.1145/3503221.3508432</a>.","chicago":"Postnikova, Anastasiia, Nikita Koval, Giorgi Nadiradze, and Dan-Adrian Alistarh. “Multi-Queues Can Be State-of-the-Art Priority Schedulers.” In <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, 353–67. Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3503221.3508432\">https://doi.org/10.1145/3503221.3508432</a>.","ama":"Postnikova A, Koval N, Nadiradze G, Alistarh D-A. Multi-queues can be state-of-the-art priority schedulers. In: <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. Association for Computing Machinery; 2022:353-367. doi:<a href=\"https://doi.org/10.1145/3503221.3508432\">10.1145/3503221.3508432</a>","ieee":"A. Postnikova, N. Koval, G. Nadiradze, and D.-A. Alistarh, “Multi-queues can be state-of-the-art priority schedulers,” in <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Seoul, Republic of Korea, 2022, pp. 353–367.","short":"A. Postnikova, N. Koval, G. Nadiradze, D.-A. Alistarh, in:, Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery, 2022, pp. 353–367.","apa":"Postnikova, A., Koval, N., Nadiradze, G., &#38; Alistarh, D.-A. (2022). Multi-queues can be state-of-the-art priority schedulers. In <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp. 353–367). Seoul, Republic of Korea: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3503221.3508432\">https://doi.org/10.1145/3503221.3508432</a>"},"type":"conference","publication_status":"published","abstract":[{"lang":"eng","text":"Designing and implementing efficient parallel priority schedulers is an active research area. An intriguing proposed design is the Multi-Queue: given n threads and m ≥ n distinct priority queues, task insertions are performed uniformly at random, while, to delete, a thread picks two queues uniformly at random, and removes the observed task of higher priority. This approach scales well, and has probabilistic rank guarantees: roughly, the rank of each task removed, relative to remaining tasks in all other queues, is O (m) in expectation. Yet, the performance of this pattern is below that of well-engineered schedulers, which eschew theoretical guarantees for practical efficiency.\r\n\r\nWe investigate whether it is possible to design and implement a Multi-Queue-based task scheduler that is both highly-efficient and has analytical guarantees. We propose a new variant called the Stealing Multi-Queue (SMQ), a cache-efficient variant of the Multi-Queue, which leverages both queue affinity---each thread has a local queue, from which tasks are usually removed; but, with some probability, threads also attempt to steal higher-priority tasks from the other queues---and task batching, that is, the processing of several tasks in a single insert / remove step. These ideas are well-known for task scheduling without priorities; our theoretical contribution is showing that, despite relaxations, this design can still provide rank guarantees, which in turn implies bounds on total work performed. We provide a general SMQ implementation which can surpass state-of-the-art schedulers such as OBIM and PMOD in terms of performance on popular graph-processing benchmarks. Notably, the performance improvement comes mainly from the superior rank guarantees provided by our scheduler, confirming that analytically-reasoned approaches can still provide performance improvements for priority task scheduling."}],"status":"public","language":[{"iso":"eng"}],"quality_controlled":"1","doi":"10.1145/3503221.3508432","oa_version":"Preprint","arxiv":1,"publisher":"Association for Computing Machinery","day":"02","publication_identifier":{"isbn":["9781450392044"]},"department":[{"_id":"DaAl"}],"year":"2022","conference":{"name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming","location":"Seoul, Republic of Korea","start_date":"2022-04-02","end_date":"2022-04-06"},"author":[{"last_name":"Postnikova","full_name":"Postnikova, Anastasiia","first_name":"Anastasiia"},{"full_name":"Koval, Nikita","last_name":"Koval","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita"},{"full_name":"Nadiradze, Giorgi","last_name":"Nadiradze","first_name":"Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"}],"isi":1,"scopus_import":"1","related_material":{"record":[{"status":"public","relation":"research_data","id":"13076"}]},"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2109.00657"}],"oa":1,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","acknowledgement":"We would like to thank the anonymous reviewers for their useful comments. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).","publication":"Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","page":"353-367","_id":"11180","project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"external_id":{"arxiv":["2109.00657"],"isi":["000883318200025"]},"date_created":"2022-04-17T22:01:46Z","date_updated":"2023-08-03T06:48:35Z","title":"Multi-queues can be state-of-the-art priority schedulers","month":"04","article_processing_charge":"No","date_published":"2022-04-02T00:00:00Z","ec_funded":1},{"quality_controlled":"1","abstract":[{"text":"To maximize the performance of concurrent data structures, researchers have often turned to highly complex fine-grained techniques, resulting in efficient and elegant algorithms, which can however be often difficult to understand and prove correct. While simpler techniques exist, such as transactional memory, they can have limited performance or portability relative to their fine-grained counterparts. Approaches at both ends of this complexity-performance spectrum have been extensively explored, but relatively less is known about the middle ground: approaches that are willing to sacrifice some performance for simplicity, while remaining competitive with state-of-the-art handcrafted designs. In this paper, we explore this middle ground, and present PathCAS, a primitive that combines ideas from multi-word CAS (KCAS) and transactional memory approaches, while carefully avoiding overhead. We show how PathCAS can be used to implement efficient search data structures relatively simply, using an internal binary search tree as an example, then extending this to an AVL tree. Our best implementations outperform many handcrafted search trees: in search-heavy workloads, it rivals the BCCO tree [5], the fastest known concurrent binary tree in terms of search performance [3]. Our results suggest that PathCAS can yield concurrent data structures that are relatively easy to build and prove correct, while offering surprisingly high performance.","lang":"eng"}],"publication_status":"published","language":[{"iso":"eng"}],"status":"public","has_accepted_license":"1","ddc":["000"],"file":[{"file_name":"2022_PPoPP_Brown.pdf","success":1,"access_level":"open_access","checksum":"8ceea411fa133795cd4903529498eb6b","relation":"main_file","date_updated":"2022-08-05T09:19:29Z","content_type":"application/pdf","file_size":1128343,"creator":"dernst","date_created":"2022-08-05T09:19:29Z","file_id":"11731"}],"type":"conference","citation":{"ama":"Brown TA, Sigouin W, Alistarh D-A. PathCAS: An efficient middle ground for concurrent search data structures. In: <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. Association for Computing Machinery; 2022:385-399. doi:<a href=\"https://doi.org/10.1145/3503221.3508410\">10.1145/3503221.3508410</a>","chicago":"Brown, Trevor A, William Sigouin, and Dan-Adrian Alistarh. “PathCAS: An Efficient Middle Ground for Concurrent Search Data Structures.” In <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, 385–99. Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3503221.3508410\">https://doi.org/10.1145/3503221.3508410</a>.","mla":"Brown, Trevor A., et al. “PathCAS: An Efficient Middle Ground for Concurrent Search Data Structures.” <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Association for Computing Machinery, 2022, pp. 385–99, doi:<a href=\"https://doi.org/10.1145/3503221.3508410\">10.1145/3503221.3508410</a>.","ista":"Brown TA, Sigouin W, Alistarh D-A. 2022. PathCAS: An efficient middle ground for concurrent search data structures. Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPoPP: Sympopsium on Principles and Practice of Parallel Programming, 385–399.","apa":"Brown, T. A., Sigouin, W., &#38; Alistarh, D.-A. (2022). PathCAS: An efficient middle ground for concurrent search data structures. In <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp. 385–399). Seoul, Republic of Korea: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3503221.3508410\">https://doi.org/10.1145/3503221.3508410</a>","short":"T.A. Brown, W. Sigouin, D.-A. Alistarh, in:, Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery, 2022, pp. 385–399.","ieee":"T. A. Brown, W. Sigouin, and D.-A. Alistarh, “PathCAS: An efficient middle ground for concurrent search data structures,” in <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Seoul, Republic of Korea, 2022, pp. 385–399."},"author":[{"full_name":"Brown, Trevor A","last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","first_name":"Trevor A"},{"first_name":"William","full_name":"Sigouin, William","last_name":"Sigouin"},{"last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"}],"isi":1,"year":"2022","conference":{"name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming","location":"Seoul, Republic of Korea","start_date":"2022-04-02","end_date":"2022-04-06"},"department":[{"_id":"DaAl"}],"publication_identifier":{"isbn":["9781450392044"]},"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publisher":"Association for Computing Machinery","day":"02","doi":"10.1145/3503221.3508410","oa_version":"Published Version","acknowledgement":"This work was supported by: the Natural Sciences and Engineering Research Council of Canada (NSERC) Collaborative Research and Development grant: CRDPJ 539431-19, the\r\nCanada Foundation for Innovation John R. Evans Leaders Fund with equal support from the Ontario Research Fund CFI Leaders Opportunity Fund: 38512, Waterloo Huawei Joint Innovation Lab project “Scalable Infrastructure for Next Generation Data Management Systems”, NSERC Discovery Launch Supplement: DGECR-2019-00048, NSERC Discovery\r\nProgram under the grants: RGPIN-2019-04227 and RGPIN04512-2018, and the University of Waterloo. We would also like to thank the reviewers for their insightful comments.","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa":1,"scopus_import":"1","date_published":"2022-04-02T00:00:00Z","article_processing_charge":"No","title":"PathCAS: An efficient middle ground for concurrent search data structures","date_updated":"2023-08-03T06:49:20Z","month":"04","_id":"11181","date_created":"2022-04-17T22:01:46Z","external_id":{"isi":["000883318200027"]},"file_date_updated":"2022-08-05T09:19:29Z","publication":"Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","page":"385-399"},{"file_date_updated":"2022-05-02T07:53:00Z","publication":"25th International Conference on Principles of Distributed Systems","_id":"11183","project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning"}],"date_created":"2022-04-17T22:01:47Z","date_updated":"2022-05-02T07:56:35Z","title":"Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters","month":"02","date_published":"2022-02-01T00:00:00Z","article_processing_charge":"No","ec_funded":1,"scopus_import":"1","alternative_title":["LIPIcs"],"volume":217,"article_number":"15","acknowledgement":"Amir Nikabadi: Supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). Janne H. Korhonen: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).\r\nWe thank François Le Gall and Masayuki Miyamoto for sharing their work on lower bounds for induced subgraph detection [36].","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"       217","oa":1,"doi":"10.4230/LIPIcs.OPODIS.2021.15","oa_version":"Published Version","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","day":"01","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772198"]},"department":[{"_id":"DaAl"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"author":[{"full_name":"Nikabadi, Amir","last_name":"Nikabadi","first_name":"Amir"},{"last_name":"Korhonen","full_name":"Korhonen, Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne"}],"year":"2022","conference":{"location":"Strasbourg, France","start_date":"2021-12-13","end_date":"2021-12-15","name":"OPODIS"},"editor":[{"first_name":"Quentin","full_name":"Bramas, Quentin","last_name":"Bramas"},{"full_name":"Gramoli, Vincent","last_name":"Gramoli","first_name":"Vincent"},{"full_name":"Milani, Alessia","last_name":"Milani","first_name":"Alessia"}],"file":[{"file_id":"11345","date_created":"2022-05-02T07:53:00Z","creator":"dernst","checksum":"626551c14de5d4091573200ed0535752","relation":"main_file","file_size":790396,"content_type":"application/pdf","date_updated":"2022-05-02T07:53:00Z","file_name":"2022_LIPICs_Nikabadi.pdf","access_level":"open_access","success":1}],"type":"conference","citation":{"mla":"Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters.” <i>25th International Conference on Principles of Distributed Systems</i>, edited by Quentin Bramas et al., vol. 217, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.15\">10.4230/LIPIcs.OPODIS.2021.15</a>.","ista":"Nikabadi A, Korhonen J. 2022. Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters. 25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 15.","chicago":"Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters.” In <i>25th International Conference on Principles of Distributed Systems</i>, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol. 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.15\">https://doi.org/10.4230/LIPIcs.OPODIS.2021.15</a>.","ama":"Nikabadi A, Korhonen J. Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters. In: Bramas Q, Gramoli V, Milani A, eds. <i>25th International Conference on Principles of Distributed Systems</i>. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.15\">10.4230/LIPIcs.OPODIS.2021.15</a>","ieee":"A. Nikabadi and J. Korhonen, “Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters,” in <i>25th International Conference on Principles of Distributed Systems</i>, Strasbourg, France, 2022, vol. 217.","short":"A. Nikabadi, J. Korhonen, in:, Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","apa":"Nikabadi, A., &#38; Korhonen, J. (2022). Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters. In Q. Bramas, V. Gramoli, &#38; A. Milani (Eds.), <i>25th International Conference on Principles of Distributed Systems</i> (Vol. 217). Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.15\">https://doi.org/10.4230/LIPIcs.OPODIS.2021.15</a>"},"ddc":["510"],"publication_status":"published","abstract":[{"lang":"eng","text":"Subgraph detection has recently been one of the most studied problems in the CONGEST model of distributed computing. In this work, we study the distributed complexity of problems closely related to subgraph detection, mainly focusing on induced subgraph detection. The main line of this work presents lower bounds and parameterized algorithms w.r.t structural parameters of the input graph:\r\n- On general graphs, we give unconditional lower bounds for induced detection of cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions from centralized parameterized complexity, we prove lower bounds in CONGEST for detecting patterns with a 4-clique, and for induced path detection conditional on the hardness of triangle detection in the congested clique.\r\n- On graphs of bounded degeneracy, we show that induced paths can be detected fast in CONGEST using techniques from parameterized algorithms, while detecting cycles and patterns of treewidth 2 is hard.\r\n- On graphs of bounded vertex cover number, we show that induced subgraph detection is easy in CONGEST for any pattern graph. More specifically, we adapt a centralized parameterized algorithm for a more general maximum common induced subgraph detection problem to the distributed setting. In addition to these induced subgraph detection results, we study various related problems in the CONGEST and congested clique models, including for multicolored versions of subgraph-detection-like problems."}],"language":[{"iso":"eng"}],"status":"public","has_accepted_license":"1","quality_controlled":"1"},{"publication":"25th International Conference on Principles of Distributed Systems","file_date_updated":"2022-05-02T08:06:33Z","project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"name":"Coordination in constrained and natural distributed systems","call_identifier":"H2020","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","grant_number":"840605"}],"_id":"11184","external_id":{"arxiv":["2102.08808"]},"date_created":"2022-04-17T22:01:47Z","title":"Fast graphical population protocols","date_updated":"2022-05-02T08:09:39Z","month":"02","article_processing_charge":"No","date_published":"2022-02-01T00:00:00Z","ec_funded":1,"scopus_import":"1","alternative_title":["LIPIcs"],"volume":217,"article_number":"14","intvolume":"       217","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"Dan Alistarh: This project has received funding from the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (grant agreement No.805223 ScaleML).\r\nJoel Rybicki: This project has received from the European Union’s Horizon 2020 research and\r\ninnovation programme under the Marie Skłodowska-Curie grant agreement No. 840605.\r\nAcknowledgements We grateful to Giorgi Nadiradze for pointing out a generalisation of the phase clock construction to non-regular graphs. We also thank anonymous reviewers for their useful comments on earlier versions of this manuscript.","doi":"10.4230/LIPIcs.OPODIS.2021.14","arxiv":1,"oa_version":"Published Version","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","day":"01","department":[{"_id":"DaAl"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772198"]},"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"conference":{"name":"OPODIS","location":"Strasbourg, France","start_date":"2021-12-13","end_date":"2021-12-15"},"year":"2022","author":[{"last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Gelashvili","full_name":"Gelashvili, Rati","first_name":"Rati"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","last_name":"Rybicki"}],"editor":[{"first_name":"Quentin","last_name":"Bramas","full_name":"Bramas, Quentin"},{"first_name":"Vincent","full_name":"Gramoli, Vincent","last_name":"Gramoli"},{"full_name":"Milani, Alessia","last_name":"Milani","first_name":"Alessia"}],"file":[{"date_created":"2022-05-02T08:06:33Z","creator":"dernst","file_id":"11346","file_name":"2022_LIPICs_Alistarh.pdf","success":1,"access_level":"open_access","checksum":"2c7c982174c6f98c4ca6e92539d15086","relation":"main_file","content_type":"application/pdf","date_updated":"2022-05-02T08:06:33Z","file_size":959406}],"type":"conference","citation":{"chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Fast Graphical Population Protocols.” In <i>25th International Conference on Principles of Distributed Systems</i>, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol. 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.14\">https://doi.org/10.4230/LIPIcs.OPODIS.2021.14</a>.","ama":"Alistarh D-A, Gelashvili R, Rybicki J. Fast graphical population protocols. In: Bramas Q, Gramoli V, Milani A, eds. <i>25th International Conference on Principles of Distributed Systems</i>. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.14\">10.4230/LIPIcs.OPODIS.2021.14</a>","ista":"Alistarh D-A, Gelashvili R, Rybicki J. 2022. Fast graphical population protocols. 25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 14.","mla":"Alistarh, Dan-Adrian, et al. “Fast Graphical Population Protocols.” <i>25th International Conference on Principles of Distributed Systems</i>, edited by Quentin Bramas et al., vol. 217, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.14\">10.4230/LIPIcs.OPODIS.2021.14</a>.","apa":"Alistarh, D.-A., Gelashvili, R., &#38; Rybicki, J. (2022). Fast graphical population protocols. In Q. Bramas, V. Gramoli, &#38; A. Milani (Eds.), <i>25th International Conference on Principles of Distributed Systems</i> (Vol. 217). Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.14\">https://doi.org/10.4230/LIPIcs.OPODIS.2021.14</a>","short":"D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ieee":"D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Fast graphical population protocols,” in <i>25th International Conference on Principles of Distributed Systems</i>, Strasbourg, France, 2022, vol. 217."},"ddc":["510"],"publication_status":"published","abstract":[{"text":"Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node.\r\nIn this work, we consider the more general setting where G is an arbitrary regular graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As a sample application, we show that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties. We believe our results will prove generally useful, as they allow efficient technology transfer between the well-mixed (clique) case, and the under-explored spatial setting.","lang":"eng"}],"has_accepted_license":"1","status":"public","language":[{"iso":"eng"}],"quality_controlled":"1"},{"date_created":"2022-05-29T22:01:54Z","external_id":{"arxiv":["2111.02278"]},"_id":"11420","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"page":"1-55","file_date_updated":"2022-05-30T08:22:55Z","publication":"Journal of Machine Learning Research","date_published":"2022-04-01T00:00:00Z","article_processing_charge":"No","month":"04","date_updated":"2024-09-10T13:03:17Z","title":"Mean-field analysis of piecewise linear solutions for wide ReLU networks","scopus_import":"1","acknowledgement":"We would like to thank Mert Pilanci for several exploratory discussions in the early stage\r\nof the project, Jan Maas for clarifications about Jordan et al. (1998), and Max Zimmer for\r\nsuggestive numerical experiments. A. Shevchenko and M. Mondelli are partially supported\r\nby the 2019 Lopez-Loreta Prize. V. Kungurtsev acknowledges support to the OP VVV\r\nproject CZ.02.1.01/0.0/0.0/16 019/0000765 Research Center for Informatics.\r\n","issue":"130","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","oa":1,"intvolume":"        23","volume":23,"related_material":{"link":[{"relation":"other","url":"https://www.jmlr.org/papers/v23/21-1365.html"}]},"day":"01","publisher":"Journal of Machine Learning Research","oa_version":"Published Version","arxiv":1,"author":[{"full_name":"Shevchenko, Aleksandr","last_name":"Shevchenko","first_name":"Aleksandr","id":"F2B06EC2-C99E-11E9-89F0-752EE6697425"},{"first_name":"Vyacheslav","full_name":"Kungurtsev, Vyacheslav","last_name":"Kungurtsev"},{"full_name":"Mondelli, Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"}],"year":"2022","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"department":[{"_id":"MaMo"},{"_id":"DaAl"}],"publication_identifier":{"issn":["1532-4435"],"eissn":["1533-7928"]},"article_type":"original","ddc":["000"],"type":"journal_article","citation":{"ieee":"A. Shevchenko, V. Kungurtsev, and M. Mondelli, “Mean-field analysis of piecewise linear solutions for wide ReLU networks,” <i>Journal of Machine Learning Research</i>, vol. 23, no. 130. Journal of Machine Learning Research, pp. 1–55, 2022.","apa":"Shevchenko, A., Kungurtsev, V., &#38; Mondelli, M. (2022). Mean-field analysis of piecewise linear solutions for wide ReLU networks. <i>Journal of Machine Learning Research</i>. Journal of Machine Learning Research.","short":"A. Shevchenko, V. Kungurtsev, M. Mondelli, Journal of Machine Learning Research 23 (2022) 1–55.","ista":"Shevchenko A, Kungurtsev V, Mondelli M. 2022. Mean-field analysis of piecewise linear solutions for wide ReLU networks. Journal of Machine Learning Research. 23(130), 1–55.","mla":"Shevchenko, Aleksandr, et al. “Mean-Field Analysis of Piecewise Linear Solutions for Wide ReLU Networks.” <i>Journal of Machine Learning Research</i>, vol. 23, no. 130, Journal of Machine Learning Research, 2022, pp. 1–55.","ama":"Shevchenko A, Kungurtsev V, Mondelli M. Mean-field analysis of piecewise linear solutions for wide ReLU networks. <i>Journal of Machine Learning Research</i>. 2022;23(130):1-55.","chicago":"Shevchenko, Aleksandr, Vyacheslav Kungurtsev, and Marco Mondelli. “Mean-Field Analysis of Piecewise Linear Solutions for Wide ReLU Networks.” <i>Journal of Machine Learning Research</i>. Journal of Machine Learning Research, 2022."},"file":[{"date_updated":"2022-05-30T08:22:55Z","content_type":"application/pdf","file_size":1521701,"checksum":"d4ff5d1affb34848b5c5e4002483fc62","relation":"main_file","success":1,"access_level":"open_access","file_name":"21-1365.pdf","file_id":"11422","creator":"cchlebak","date_created":"2022-05-30T08:22:55Z"}],"quality_controlled":"1","language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public","abstract":[{"lang":"eng","text":"Understanding the properties of neural networks trained via stochastic gradient descent (SGD) is at the heart of the theory of deep learning. In this work, we take a mean-field view, and consider a two-layer ReLU network trained via noisy-SGD for a univariate regularized regression problem. Our main result is that SGD with vanishingly small noise injected in the gradients is biased towards a simple solution: at convergence, the ReLU network implements a piecewise linear map of the inputs, and the number of “knot” points -- i.e., points where the tangent of the ReLU network estimator changes -- between two consecutive training inputs is at most three. In particular, as the number of neurons of the network grows, the SGD dynamics is captured by the solution of a gradient flow and, at convergence, the distribution of the weights approaches the unique minimizer of a related free energy, which has a Gibbs form. Our key technical contribution consists in the analysis of the estimator resulting from this minimizer: we show that its second derivative vanishes everywhere, except at some specific locations which represent the “knot” points. We also provide empirical evidence that knots at locations distinct from the data points might occur, as predicted by our theory."}],"publication_status":"published"},{"type":"conference","citation":{"chicago":"Balliu, Alkida, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, and Jukka Suomela. “Local Mending.” In <i>International Colloquium on Structural Information and Communication Complexity</i>, edited by Merav Parter, 13298:1–20. LNCS. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/978-3-031-09993-9_1\">https://doi.org/10.1007/978-3-031-09993-9_1</a>.","ama":"Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. Local mending. In: Parter M, ed. <i>International Colloquium on Structural Information and Communication Complexity</i>. Vol 13298. LNCS. Springer Nature; 2022:1-20. doi:<a href=\"https://doi.org/10.1007/978-3-031-09993-9_1\">10.1007/978-3-031-09993-9_1</a>","ista":"Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. 2022. Local mending. International Colloquium on Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication ComplexityLNCS vol. 13298, 1–20.","mla":"Balliu, Alkida, et al. “Local Mending.” <i>International Colloquium on Structural Information and Communication Complexity</i>, edited by Merav Parter, vol. 13298, Springer Nature, 2022, pp. 1–20, doi:<a href=\"https://doi.org/10.1007/978-3-031-09993-9_1\">10.1007/978-3-031-09993-9_1</a>.","short":"A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, J. Suomela, in:, M. Parter (Ed.), International Colloquium on Structural Information and Communication Complexity, Springer Nature, 2022, pp. 1–20.","apa":"Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J., &#38; Suomela, J. (2022). Local mending. In M. Parter (Ed.), <i>International Colloquium on Structural Information and Communication Complexity</i> (Vol. 13298, pp. 1–20). Paderborn, Germany: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-09993-9_1\">https://doi.org/10.1007/978-3-031-09993-9_1</a>","ieee":"A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, and J. Suomela, “Local mending,” in <i>International Colloquium on Structural Information and Communication Complexity</i>, Paderborn, Germany, 2022, vol. 13298, pp. 1–20."},"status":"public","language":[{"iso":"eng"}],"publication_status":"published","abstract":[{"lang":"eng","text":"In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to “patch a hole.” We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Π can be solved in O(log∗n), there is always a restriction Π′⊆Π that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Θ(logn), or Θ(n), while in general graphs the structure is much more diverse."}],"quality_controlled":"1","arxiv":1,"oa_version":"Preprint","doi":"10.1007/978-3-031-09993-9_1","day":"25","publisher":"Springer Nature","series_title":"LNCS","publication_identifier":{"isbn":["9783031099922"],"eissn":["1611-3349"],"issn":["0302-9743"]},"department":[{"_id":"DaAl"}],"editor":[{"last_name":"Parter","full_name":"Parter, Merav","first_name":"Merav"}],"year":"2022","conference":{"end_date":"2022-06-29","location":"Paderborn, Germany","start_date":"2022-06-27","name":"SIROCCO: Structural Information and Communication Complexity"},"isi":1,"author":[{"full_name":"Balliu, Alkida","last_name":"Balliu","first_name":"Alkida"},{"first_name":"Juho","full_name":"Hirvonen, Juho","last_name":"Hirvonen"},{"full_name":"Melnyk, Darya","last_name":"Melnyk","first_name":"Darya"},{"last_name":"Olivetti","full_name":"Olivetti, Dennis","first_name":"Dennis"},{"last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Suomela, Jukka","last_name":"Suomela","first_name":"Jukka"}],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2102.08703"}],"volume":13298,"intvolume":"     13298","oa":1,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 840605. This work was supported in part by the Academy of Finland, Grants 314888 and 333837. The authors would also like to thank David Harris, Neven Villani, and the anonymous reviewers for their very helpful comments and feedback on previous versions of this work.","page":"1-20","publication":"International Colloquium on Structural Information and Communication Complexity","external_id":{"arxiv":["2102.08703"],"isi":["000876977400001"]},"date_created":"2022-07-31T22:01:49Z","project":[{"name":"Coordination in constrained and natural distributed systems","grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"_id":"11707","month":"06","date_updated":"2023-08-03T12:16:29Z","title":"Local mending","ec_funded":1,"article_processing_charge":"No","date_published":"2022-06-25T00:00:00Z"},{"author":[{"last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Rybicki","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Sasha","last_name":"Voitovych","full_name":"Voitovych, Sasha"}],"year":"2022","conference":{"end_date":"2022-07-29","start_date":"2022-07-25","location":"Salerno, Italy","name":"PODC: Symposium on Principles of Distributed Computing"},"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_identifier":{"isbn":["9781450392624"]},"department":[{"_id":"DaAl"}],"day":"21","publisher":"Association for Computing Machinery","oa_version":"Published Version","arxiv":1,"doi":"10.1145/3519270.3538435","quality_controlled":"1","language":[{"iso":"eng"}],"status":"public","has_accepted_license":"1","publication_status":"published","abstract":[{"lang":"eng","text":"In the stochastic population protocol model, we are given a connected graph with n nodes, and in every time step, a scheduler samples an edge of the graph uniformly at random and the nodes connected by this edge interact. A fundamental task in this model is stable leader election, in which all nodes start in an identical state and the aim is to reach a configuration in which (1) exactly one node is elected as leader and (2) this node remains as the unique leader no matter what sequence of interactions follows. On cliques, the complexity of this problem has recently been settled: time-optimal protocols stabilize in Θ(n log n) expected steps using Θ(log log n) states, whereas protocols that use O(1) states require Θ(n2) expected steps.\r\n\r\nIn this work, we investigate the complexity of stable leader election on general graphs. We provide the first non-trivial time lower bounds for leader election on general graphs, showing that, when moving beyond cliques, the complexity landscape of leader election becomes very diverse: the time required to elect a leader can range from O(1) to Θ(n3) expected steps. On the upper bound side, we first observe that there exists a protocol that is time-optimal on many graph families, but uses polynomially-many states. In contrast, we give a near-time-optimal protocol that uses only O(log2n) states that is at most a factor log n slower. Finally, we show that the constant-state protocol of Beauquier et al. [OPODIS 2013] is at most a factor n log n slower than the fast polynomial-state protocol. Moreover, among constant-state protocols, this protocol has near-optimal average case complexity on dense random graphs."}],"ddc":["000"],"type":"conference","citation":{"chicago":"Alistarh, Dan-Adrian, Joel Rybicki, and Sasha Voitovych. “Near-Optimal Leader Election in Population Protocols on Graphs.” In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, 246–56. Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3519270.3538435\">https://doi.org/10.1145/3519270.3538435</a>.","ama":"Alistarh D-A, Rybicki J, Voitovych S. Near-optimal leader election in population protocols on graphs. In: <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2022:246-256. doi:<a href=\"https://doi.org/10.1145/3519270.3538435\">10.1145/3519270.3538435</a>","mla":"Alistarh, Dan-Adrian, et al. “Near-Optimal Leader Election in Population Protocols on Graphs.” <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2022, pp. 246–56, doi:<a href=\"https://doi.org/10.1145/3519270.3538435\">10.1145/3519270.3538435</a>.","ista":"Alistarh D-A, Rybicki J, Voitovych S. 2022. Near-optimal leader election in population protocols on graphs. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 246–256.","apa":"Alistarh, D.-A., Rybicki, J., &#38; Voitovych, S. (2022). Near-optimal leader election in population protocols on graphs. In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i> (pp. 246–256). Salerno, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3519270.3538435\">https://doi.org/10.1145/3519270.3538435</a>","short":"D.-A. Alistarh, J. Rybicki, S. Voitovych, in:, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2022, pp. 246–256.","ieee":"D.-A. Alistarh, J. Rybicki, and S. Voitovych, “Near-optimal leader election in population protocols on graphs,” in <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Salerno, Italy, 2022, pp. 246–256."},"file":[{"date_created":"2022-08-16T08:05:15Z","creator":"cchlebak","file_id":"11854","file_name":"2022_PODC_Alistarh.pdf","access_level":"open_access","success":1,"checksum":"4c6b29172b8e355b4fbc364a2e0827b2","relation":"main_file","file_size":1593474,"content_type":"application/pdf","date_updated":"2022-08-16T08:05:15Z"}],"ec_funded":1,"date_published":"2022-07-21T00:00:00Z","article_processing_charge":"Yes (via OA deal)","month":"07","date_updated":"2023-06-14T12:06:01Z","title":"Near-optimal leader election in population protocols on graphs","date_created":"2022-08-14T22:01:46Z","external_id":{"arxiv":["2205.12597"]},"project":[{"call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning"}],"_id":"11844","page":"246-256","file_date_updated":"2022-08-16T08:05:15Z","publication":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"We thank the anonymous reviewers for their helpful comments. We gratefully acknowledge funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).","oa":1,"scopus_import":"1"},{"day":"01","publisher":"ML Research Press","oa_version":"Published Version","arxiv":1,"conference":{"end_date":"2021-07-24","location":"Virtual","start_date":"2021-07-18","name":"International Conference on Machine Learning"},"year":"2021","author":[{"first_name":"Foivos","full_name":"Alimisis, Foivos","last_name":"Alimisis"},{"first_name":"Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","last_name":"Davies","full_name":"Davies, Peter","orcid":"0000-0002-5646-9524"},{"full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_identifier":{"eissn":["2640-3498"],"isbn":["9781713845065"]},"department":[{"_id":"DaAl"}],"ddc":["000"],"citation":{"ista":"Alimisis F, Davies P, Alistarh D-A. 2021. Communication-efficient distributed optimization with quantized preconditioners. Proceedings of the 38th International Conference on Machine Learning. International Conference on Machine Learning vol. 139, 196–206.","mla":"Alimisis, Foivos, et al. “Communication-Efficient Distributed Optimization with Quantized Preconditioners.” <i>Proceedings of the 38th International Conference on Machine Learning</i>, vol. 139, ML Research Press, 2021, pp. 196–206.","ama":"Alimisis F, Davies P, Alistarh D-A. Communication-efficient distributed optimization with quantized preconditioners. In: <i>Proceedings of the 38th International Conference on Machine Learning</i>. Vol 139. ML Research Press; 2021:196-206.","chicago":"Alimisis, Foivos, Peter Davies, and Dan-Adrian Alistarh. “Communication-Efficient Distributed Optimization with Quantized Preconditioners.” In <i>Proceedings of the 38th International Conference on Machine Learning</i>, 139:196–206. ML Research Press, 2021.","ieee":"F. Alimisis, P. Davies, and D.-A. Alistarh, “Communication-efficient distributed optimization with quantized preconditioners,” in <i>Proceedings of the 38th International Conference on Machine Learning</i>, Virtual, 2021, vol. 139, pp. 196–206.","apa":"Alimisis, F., Davies, P., &#38; Alistarh, D.-A. (2021). Communication-efficient distributed optimization with quantized preconditioners. In <i>Proceedings of the 38th International Conference on Machine Learning</i> (Vol. 139, pp. 196–206). Virtual: ML Research Press.","short":"F. Alimisis, P. Davies, D.-A. Alistarh, in:, Proceedings of the 38th International Conference on Machine Learning, ML Research Press, 2021, pp. 196–206."},"type":"conference","file":[{"access_level":"open_access","success":1,"file_name":"2021_PMLR_Alimisis.pdf","file_size":429087,"content_type":"application/pdf","date_updated":"2023-06-19T10:41:05Z","checksum":"7ec0d59bac268b49c76bf2e036dedd7a","relation":"main_file","creator":"dernst","date_created":"2023-06-19T10:41:05Z","file_id":"13154"}],"quality_controlled":"1","status":"public","has_accepted_license":"1","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We investigate fast and communication-efficient algorithms for the classic problem of minimizing a sum of strongly convex and smooth functions that are distributed among n\r\n different nodes, which can communicate using a limited number of bits. Most previous communication-efficient approaches for this problem are limited to first-order optimization, and therefore have \\emph{linear} dependence on the condition number in their communication complexity. We show that this dependence is not inherent: communication-efficient methods can in fact have sublinear dependence on the condition number. For this, we design and analyze the first communication-efficient distributed variants of preconditioned gradient descent for Generalized Linear Models, and for Newton’s method. Our results rely on a new technique for quantizing both the preconditioner and the descent direction at each step of the algorithms, while controlling their convergence rate. We also validate our findings experimentally, showing faster convergence and reduced communication relative to previous methods."}],"publication_status":"published","external_id":{"arxiv":["2102.07214"]},"date_created":"2023-06-18T22:00:48Z","_id":"13147","project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"page":"196-206","publication":"Proceedings of the 38th International Conference on Machine Learning","file_date_updated":"2023-06-19T10:41:05Z","ec_funded":1,"article_processing_charge":"No","date_published":"2021-07-01T00:00:00Z","month":"07","date_updated":"2023-06-19T10:44:38Z","title":"Communication-efficient distributed optimization with quantized preconditioners","scopus_import":"1","oa":1,"intvolume":"       139","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"The authors would like to thank Janne Korhonen, Aurelien Lucchi, Celestine MendlerDunner and Antonio Orvieto for helpful discussions. FA ¨and DA were supported during this work by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). PD was supported by the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No. 754411.","volume":139},{"related_material":{"link":[{"relation":"earlier_version","url":"https://doi.org/10.4230/LIPIcs.ICALP.2020.7"}],"record":[{"relation":"earlier_version","status":"public","id":"15077"}]},"acknowledgement":"The authors sincerely thank Thomas Sauerwald and George Giakkoupis for insightful discussions, and Mohsen Ghaffari, Yuval Peres, and Udi Wieder for feedback on earlier versions of this draft. We also thank the ICALP anonymous reviewers for their very useful comments. Open access funding provided by Institute of Science and Technology (IST Austria). Funding was provided by European Research Council (Grant No. PR1042ERC01).","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa":1,"scopus_import":"1","month":"12","title":"Dynamic averaging load balancing on cycles","date_updated":"2024-03-05T07:35:53Z","ec_funded":1,"date_published":"2021-12-24T00:00:00Z","article_processing_charge":"Yes (via OA deal)","file_date_updated":"2021-12-27T10:36:40Z","publication":"Algorithmica","date_created":"2020-08-24T06:24:04Z","external_id":{"isi":["000734004600001"],"arxiv":["2003.09297"]},"_id":"8286","project":[{"name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"},{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public","abstract":[{"lang":"eng","text":"We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step t≥ 0, one unit of load is created, and placed at a randomly chosen graph node. In the same step, the chosen node picks a random neighbor, and the two nodes balance their loads by averaging them. We are interested in the expected gap between the minimum and maximum loads at nodes as the process progresses, and its dependence on n and on the graph structure. Variants of the above graphical balanced allocation process have been studied previously by Peres, Talwar, and Wieder [Peres et al., 2015], and by Sauerwald and Sun [Sauerwald and Sun, 2015]. These authors left as open the question of characterizing the gap in the case of cycle graphs in the dynamic case, where weights are created during the algorithm’s execution. For this case, the only known upper bound is of 𝒪(n log n), following from a majorization argument due to [Peres et al., 2015], which analyzes a related graphical allocation process. In this paper, we provide an upper bound of 𝒪 (√n log n) on the expected gap of the above process for cycles of length n. We introduce a new potential analysis technique, which enables us to bound the difference in load between k-hop neighbors on the cycle, for any k ≤ n/2. We complement this with a \"gap covering\" argument, which bounds the maximum value of the gap by bounding its value across all possible subsets of a certain structure, and recursively bounding the gaps within each subset. We provide analytical and experimental evidence that our upper bound on the gap is tight up to a logarithmic factor. "}],"publication_status":"published","quality_controlled":"1","citation":{"short":"D.-A. Alistarh, G. Nadiradze, A. Sabour, Algorithmica (2021).","apa":"Alistarh, D.-A., Nadiradze, G., &#38; Sabour, A. (2021). Dynamic averaging load balancing on cycles. <i>Algorithmica</i>. Virtual, Online; Germany: Springer Nature. <a href=\"https://doi.org/10.1007/s00453-021-00905-9\">https://doi.org/10.1007/s00453-021-00905-9</a>","ieee":"D.-A. Alistarh, G. Nadiradze, and A. Sabour, “Dynamic averaging load balancing on cycles,” <i>Algorithmica</i>. Springer Nature, 2021.","chicago":"Alistarh, Dan-Adrian, Giorgi Nadiradze, and Amirmojtaba Sabour. “Dynamic Averaging Load Balancing on Cycles.” <i>Algorithmica</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s00453-021-00905-9\">https://doi.org/10.1007/s00453-021-00905-9</a>.","ama":"Alistarh D-A, Nadiradze G, Sabour A. Dynamic averaging load balancing on cycles. <i>Algorithmica</i>. 2021. doi:<a href=\"https://doi.org/10.1007/s00453-021-00905-9\">10.1007/s00453-021-00905-9</a>","mla":"Alistarh, Dan-Adrian, et al. “Dynamic Averaging Load Balancing on Cycles.” <i>Algorithmica</i>, Springer Nature, 2021, doi:<a href=\"https://doi.org/10.1007/s00453-021-00905-9\">10.1007/s00453-021-00905-9</a>.","ista":"Alistarh D-A, Nadiradze G, Sabour A. 2021. Dynamic averaging load balancing on cycles. Algorithmica."},"type":"journal_article","file":[{"file_name":"2021_Algorithmica_Alistarh.pdf","access_level":"open_access","success":1,"relation":"main_file","checksum":"21169b25b0c8e17b21e12af22bff9870","file_size":525950,"date_updated":"2021-12-27T10:36:40Z","content_type":"application/pdf","date_created":"2021-12-27T10:36:40Z","creator":"cchlebak","file_id":"10577"}],"article_type":"original","ddc":["000"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"department":[{"_id":"DaAl"}],"isi":1,"author":[{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"},{"id":"3279A00C-F248-11E8-B48F-1D18A9856A87","first_name":"Giorgi","last_name":"Nadiradze","full_name":"Nadiradze, Giorgi","orcid":"0000-0001-5634-0731"},{"first_name":"Amirmojtaba","id":"bcc145fd-e77f-11ea-ae8b-80d661dbff67","full_name":"Sabour, Amirmojtaba","last_name":"Sabour"}],"conference":{"name":"ICALP: International Colloquium on Automata, Languages, and Programming ","end_date":"2020-07-11","start_date":"2020-07-08","location":"Virtual, Online; Germany"},"year":"2021","arxiv":1,"oa_version":"Published Version","doi":"10.1007/s00453-021-00905-9","day":"24","publisher":"Springer Nature"},{"article_processing_charge":"No","date_published":"2021-07-01T00:00:00Z","ec_funded":1,"date_updated":"2023-08-04T11:08:52Z","title":"Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging","month":"07","project":[{"name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","call_identifier":"H2020"}],"_id":"8723","external_id":{"arxiv":["2005.00124"],"isi":["000621405200019"]},"date_created":"2020-11-05T15:25:43Z","publication":"IEEE Transactions on Parallel and Distributed Systems","article_number":"9271898","oa":1,"intvolume":"        32","issue":"7","acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’s Hori-\r\nzon 2020 programme under Grant DAPP, Grant 678880; EPi-GRAM-HS, Grant 801039; and ERC Starting Grant ScaleML, Grant 805223. The work of Tal Ben-Nun is supported by the Swiss National Science Foundation (Ambizione Project No. 185778). The work of Nikoli Dryden is supported by the ETH Postdoctoral Fellowship. The authors would like to thank the Swiss National Supercomputing Center for providing the computing resources and technical support.","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2005.00124"}],"volume":32,"scopus_import":"1","year":"2021","author":[{"last_name":"Li","full_name":"Li, Shigang","first_name":"Shigang"},{"full_name":"Tal Ben-Nun, Tal Ben-Nun","last_name":"Tal Ben-Nun","first_name":"Tal Ben-Nun"},{"first_name":"Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","last_name":"Nadiradze","full_name":"Nadiradze, Giorgi"},{"first_name":"Salvatore Di","last_name":"Girolamo","full_name":"Girolamo, Salvatore Di"},{"first_name":"Nikoli","last_name":"Dryden","full_name":"Dryden, Nikoli"},{"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":"Hoefler, Torsten","last_name":"Hoefler","first_name":"Torsten"}],"isi":1,"department":[{"_id":"DaAl"}],"publication_identifier":{"issn":["10459219"]},"publisher":"IEEE","day":"01","doi":"10.1109/TPDS.2020.3040606","oa_version":"Preprint","arxiv":1,"quality_controlled":"1","abstract":[{"text":"Deep learning at scale is dominated by communication time. Distributing samples across nodes usually yields the best performance, but poses scaling challenges due to global information dissemination and load imbalance across uneven sample lengths. State-of-the-art decentralized optimizers mitigate the problem, but require more iterations to achieve the same accuracy as their globally-communicating counterparts. We present Wait-Avoiding Group Model Averaging (WAGMA) SGD, a wait-avoiding stochastic optimizer that reduces global communication via subgroup weight exchange. The key insight is a combination of algorithmic changes to the averaging scheme and the use of a group allreduce operation. We prove the convergence of WAGMA-SGD, and empirically show that it retains convergence rates similar to Allreduce-SGD. For evaluation, we train ResNet-50 on ImageNet; Transformer for machine translation; and deep reinforcement learning for navigation at scale. Compared with state-of-the-art decentralized SGD variants, WAGMA-SGD significantly improves training throughput (e.g., 2.1× on 1,024 GPUs for reinforcement learning), and achieves the fastest time-to-solution (e.g., the highest score using the shortest training time for Transformer).","lang":"eng"}],"publication_status":"published","status":"public","language":[{"iso":"eng"}],"article_type":"original","type":"journal_article","citation":{"mla":"Li, Shigang, et al. “Breaking (Global) Barriers in Parallel Stochastic Optimization with Wait-Avoiding Group Averaging.” <i>IEEE Transactions on Parallel and Distributed Systems</i>, vol. 32, no. 7, 9271898, IEEE, 2021, doi:<a href=\"https://doi.org/10.1109/TPDS.2020.3040606\">10.1109/TPDS.2020.3040606</a>.","ista":"Li S, Tal Ben-Nun TB-N, Nadiradze G, Girolamo SD, Dryden N, Alistarh D-A, Hoefler T. 2021. Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging. IEEE Transactions on Parallel and Distributed Systems. 32(7), 9271898.","chicago":"Li, Shigang, Tal Ben-Nun Tal Ben-Nun, Giorgi Nadiradze, Salvatore Di Girolamo, Nikoli Dryden, Dan-Adrian Alistarh, and Torsten Hoefler. “Breaking (Global) Barriers in Parallel Stochastic Optimization with Wait-Avoiding Group Averaging.” <i>IEEE Transactions on Parallel and Distributed Systems</i>. IEEE, 2021. <a href=\"https://doi.org/10.1109/TPDS.2020.3040606\">https://doi.org/10.1109/TPDS.2020.3040606</a>.","ama":"Li S, Tal Ben-Nun TB-N, Nadiradze G, et al. Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging. <i>IEEE Transactions on Parallel and Distributed Systems</i>. 2021;32(7). doi:<a href=\"https://doi.org/10.1109/TPDS.2020.3040606\">10.1109/TPDS.2020.3040606</a>","ieee":"S. Li <i>et al.</i>, “Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging,” <i>IEEE Transactions on Parallel and Distributed Systems</i>, vol. 32, no. 7. IEEE, 2021.","apa":"Li, S., Tal Ben-Nun, T. B.-N., Nadiradze, G., Girolamo, S. D., Dryden, N., Alistarh, D.-A., &#38; Hoefler, T. (2021). Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging. <i>IEEE Transactions on Parallel and Distributed Systems</i>. IEEE. <a href=\"https://doi.org/10.1109/TPDS.2020.3040606\">https://doi.org/10.1109/TPDS.2020.3040606</a>","short":"S. Li, T.B.-N. Tal Ben-Nun, G. Nadiradze, S.D. Girolamo, N. Dryden, D.-A. Alistarh, T. Hoefler, IEEE Transactions on Parallel and Distributed Systems 32 (2021)."}},{"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00446-020-00380-5"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"6933"}]},"volume":34,"intvolume":"        34","oa":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). We thank Mohsen Ghaffari, Michael Elkin and Merav Parter for fruitful discussions. This project has received funding from the European Union’s Horizon 2020 Research And Innovation Program under Grant Agreement No. 755839.","publication":"Distributed Computing","page":"463-487","_id":"7939","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"external_id":{"arxiv":["1903.05956"],"isi":["000556444600001"]},"date_created":"2020-06-07T22:00:54Z","date_updated":"2024-03-07T14:43:39Z","title":"Fast approximate shortest paths in the congested clique","month":"12","article_processing_charge":"Yes (via OA deal)","date_published":"2021-12-01T00:00:00Z","citation":{"ieee":"K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate shortest paths in the congested clique,” <i>Distributed Computing</i>, vol. 34. Springer Nature, pp. 463–487, 2021.","short":"K. Censor-Hillel, M. Dory, J. Korhonen, D. Leitersdorf, Distributed Computing 34 (2021) 463–487.","apa":"Censor-Hillel, K., Dory, M., Korhonen, J., &#38; Leitersdorf, D. (2021). Fast approximate shortest paths in the congested clique. <i>Distributed Computing</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00446-020-00380-5\">https://doi.org/10.1007/s00446-020-00380-5</a>","ista":"Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2021. Fast approximate shortest paths in the congested clique. Distributed Computing. 34, 463–487.","mla":"Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested Clique.” <i>Distributed Computing</i>, vol. 34, Springer Nature, 2021, pp. 463–87, doi:<a href=\"https://doi.org/10.1007/s00446-020-00380-5\">10.1007/s00446-020-00380-5</a>.","chicago":"Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf. “Fast Approximate Shortest Paths in the Congested Clique.” <i>Distributed Computing</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s00446-020-00380-5\">https://doi.org/10.1007/s00446-020-00380-5</a>.","ama":"Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest paths in the congested clique. <i>Distributed Computing</i>. 2021;34:463-487. doi:<a href=\"https://doi.org/10.1007/s00446-020-00380-5\">10.1007/s00446-020-00380-5</a>"},"type":"journal_article","article_type":"original","publication_status":"published","abstract":[{"text":"We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include:\r\n    A (2+ϵ)-approximation for all-pairs shortest paths in O(log2n/ϵ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model.\r\n    A (1+ϵ)-approximation for multi-source shortest paths from O(n−−√) sources in O(log2n/ϵ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size.\r\n\r\nOur main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in O~(n1/6) rounds. ","lang":"eng"}],"status":"public","language":[{"iso":"eng"}],"quality_controlled":"1","doi":"10.1007/s00446-020-00380-5","arxiv":1,"oa_version":"Published Version","publisher":"Springer Nature","day":"01","department":[{"_id":"DaAl"}],"publication_identifier":{"issn":["0178-2770"],"eissn":["1432-0452"]},"year":"2021","isi":1,"author":[{"first_name":"Keren","last_name":"Censor-Hillel","full_name":"Censor-Hillel, Keren"},{"first_name":"Michal","full_name":"Dory, Michal","last_name":"Dory"},{"first_name":"Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","last_name":"Korhonen","full_name":"Korhonen, Janne"},{"first_name":"Dean","full_name":"Leitersdorf, Dean","last_name":"Leitersdorf"}]},{"quality_controlled":"1","abstract":[{"text":"While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open.","lang":"eng"}],"publication_status":"published","status":"public","language":[{"iso":"eng"}],"citation":{"apa":"Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M., Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In <i>2021 IEEE Symposium on Security and Privacy </i> (pp. 268–284). San Francisco, CA, United States: IEEE. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>","short":"K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M. Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–284.","ieee":"K. Klein <i>et al.</i>, “Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement,” in <i>2021 IEEE Symposium on Security and Privacy </i>, San Francisco, CA, United States, 2021, pp. 268–284.","chicago":"Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo, Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” In <i>2021 IEEE Symposium on Security and Privacy </i>, 268–84. IEEE, 2021. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>.","ama":"Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In: <i>2021 IEEE Symposium on Security and Privacy </i>. IEEE; 2021:268-284. doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>","mla":"Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” <i>2021 IEEE Symposium on Security and Privacy </i>, IEEE, 2021, pp. 268–84, doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>.","ista":"Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium on Security and Privacy . SP: Symposium on Security and Privacy, 268–284."},"type":"conference","conference":{"end_date":"2021-05-27","start_date":"2021-05-24","location":"San Francisco, CA, United States","name":"SP: Symposium on Security and Privacy"},"year":"2021","author":[{"first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","full_name":"Klein, Karen"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo","last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","orcid":"0000-0001-8630-415X"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael"},{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg"},{"first_name":"Margarita","full_name":"Capretto, Margarita","last_name":"Capretto"},{"first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval"},{"full_name":"Markov, Ilia","last_name":"Markov","id":"D0CF4148-C985-11E9-8066-0BDEE5697425","first_name":"Ilia"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X","full_name":"Yeo, Michelle X","last_name":"Yeo"},{"full_name":"Alwen, Joel F","last_name":"Alwen","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"department":[{"_id":"KrPi"},{"_id":"DaAl"}],"publisher":"IEEE","day":"26","doi":"10.1109/sp40001.2021.00035","oa_version":"Preprint","oa":1,"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","acknowledgement":"The first three authors contributed equally to this work. Funded by the European Research Council (ERC) under the European Union’s Horizon2020 research and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.665385.","main_file_link":[{"url":"https://eprint.iacr.org/2019/1489","open_access":"1"}],"related_material":{"record":[{"id":"10035","status":"public","relation":"dissertation_contains"}]},"article_processing_charge":"No","date_published":"2021-08-26T00:00:00Z","ec_funded":1,"title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","date_updated":"2023-09-07T13:32:11Z","month":"08","_id":"10049","project":[{"name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","call_identifier":"H2020"},{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"date_created":"2021-09-27T13:46:27Z","publication":"2021 IEEE Symposium on Security and Privacy ","page":"268-284"},{"volume":22,"main_file_link":[{"url":"https://www.jmlr.org/papers/v22/21-0366.html","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"241","acknowledgement":"We thank Doug Burger, Steve Scott, Marco Heddes, and the respective teams at Microsoft for inspiring discussions on the topic. We thank Angelika Steger for uplifting debates about the connections to biological brains, Sidak Pal Singh for his support regarding experimental results, and Utku Evci as well as Xin Wang for comments on previous versions of this\r\nwork. Special thanks go to Bernhard Schölkopf, our JMLR editor Samy Bengio, and the three anonymous reviewers who provided excellent comprehensive, pointed, and deep review comments that improved the quality of our manuscript significantly.","intvolume":"        22","oa":1,"scopus_import":"1","date_updated":"2022-05-13T09:36:08Z","title":"Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks","month":"09","date_published":"2021-09-01T00:00:00Z","article_processing_charge":"No","file_date_updated":"2021-10-27T15:34:18Z","publication":"Journal of Machine Learning Research","page":"1-124","_id":"10180","date_created":"2021-10-24T22:01:34Z","external_id":{"arxiv":["2102.00554"]},"publication_status":"published","abstract":[{"lang":"eng","text":"The growing energy and performance costs of deep learning have driven the community to reduce the size of neural networks by selectively pruning components. Similarly to their biological counterparts, sparse networks generalize just as well, sometimes even better than, the original dense networks. Sparsity promises to reduce the memory footprint of regular networks to fit mobile devices, as well as shorten training time for ever growing networks. In this paper, we survey prior work on sparsity in deep learning and provide an extensive tutorial of sparsification for both inference and training. We describe approaches to remove and add elements of neural networks, different training strategies to achieve model sparsity, and mechanisms to exploit sparsity in practice. Our work distills ideas from more than 300 research papers and provides guidance to practitioners who wish to utilize sparsity today, as well as to researchers whose goal is to push the frontier forward. We include the necessary background on mathematical methods in sparsification, describe phenomena such as early structure adaptation, the intricate relations between sparsity and the training process, and show techniques for achieving acceleration on real hardware. We also define a metric of pruned parameter efficiency that could serve as a baseline for comparison of different sparse networks. We close by speculating on how sparsity can improve future workloads and outline major open problems in the field."}],"language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public","quality_controlled":"1","file":[{"date_created":"2021-10-27T15:34:18Z","creator":"cziletti","file_id":"10192","success":1,"access_level":"open_access","file_name":"2021_JMachLearnRes_Hoefler.pdf","content_type":"application/pdf","date_updated":"2021-10-27T15:34:18Z","file_size":3527521,"relation":"main_file","checksum":"3389d9d01fc58f8fb4c1a53e14a8abbf"}],"type":"journal_article","citation":{"ista":"Hoefler T, Alistarh D-A, Ben-Nun T, Dryden N, Peste E-A. 2021. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. Journal of Machine Learning Research. 22(241), 1–124.","mla":"Hoefler, Torsten, et al. “Sparsity in Deep Learning: Pruning and Growth for Efficient Inference and Training in Neural Networks.” <i>Journal of Machine Learning Research</i>, vol. 22, no. 241, Journal of Machine Learning Research, 2021, pp. 1–124.","chicago":"Hoefler, Torsten, Dan-Adrian Alistarh, Tal Ben-Nun, Nikoli Dryden, and Elena-Alexandra Peste. “Sparsity in Deep Learning: Pruning and Growth for Efficient Inference and Training in Neural Networks.” <i>Journal of Machine Learning Research</i>. Journal of Machine Learning Research, 2021.","ama":"Hoefler T, Alistarh D-A, Ben-Nun T, Dryden N, Peste E-A. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. <i>Journal of Machine Learning Research</i>. 2021;22(241):1-124.","ieee":"T. Hoefler, D.-A. Alistarh, T. Ben-Nun, N. Dryden, and E.-A. Peste, “Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks,” <i>Journal of Machine Learning Research</i>, vol. 22, no. 241. Journal of Machine Learning Research, pp. 1–124, 2021.","apa":"Hoefler, T., Alistarh, D.-A., Ben-Nun, T., Dryden, N., &#38; Peste, E.-A. (2021). Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. <i>Journal of Machine Learning Research</i>. Journal of Machine Learning Research.","short":"T. Hoefler, D.-A. Alistarh, T. Ben-Nun, N. Dryden, E.-A. Peste, Journal of Machine Learning Research 22 (2021) 1–124."},"ddc":["000"],"article_type":"original","publication_identifier":{"issn":["1532-4435"],"eissn":["1533-7928"]},"department":[{"_id":"DaAl"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"author":[{"first_name":"Torsten","last_name":"Hoefler","full_name":"Hoefler, Torsten"},{"last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Tal","last_name":"Ben-Nun","full_name":"Ben-Nun, Tal"},{"full_name":"Dryden, Nikoli","last_name":"Dryden","first_name":"Nikoli"},{"last_name":"Peste","full_name":"Peste, Elena-Alexandra","first_name":"Elena-Alexandra","id":"32D78294-F248-11E8-B48F-1D18A9856A87"}],"year":"2021","arxiv":1,"oa_version":"Published Version","publisher":"Journal of Machine Learning Research","day":"01"},{"doi":"10.4230/LIPIcs.DISC.2021.52","oa_version":"Published Version","arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","day":"04","publication_identifier":{"issn":["1868-8969"],"isbn":["9-783-9597-7210-5"]},"department":[{"_id":"DaAl"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2021","conference":{"location":"Freiburg, Germany","start_date":"2021-10-04","end_date":"2021-10-08","name":"DISC: Distributed Computing"},"author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Bapi","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","first_name":"Bapi"},{"full_name":"Peri, Sathya","last_name":"Peri","first_name":"Sathya"},{"first_name":"Muktikanta","last_name":"Sa","full_name":"Sa, Muktikanta"}],"file":[{"access_level":"open_access","success":1,"file_name":"2021_LIPIcsDISC_BChatterjee.pdf","file_size":795860,"content_type":"application/pdf","date_updated":"2021-11-12T09:23:22Z","relation":"main_file","checksum":"76546df112a0ba1166c864d33d7834e2","date_created":"2021-11-12T09:23:22Z","creator":"cchlebak","file_id":"10276"}],"citation":{"chicago":"Chatterjee, Bapi, Sathya Peri, and Muktikanta Sa. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">https://doi.org/10.4230/LIPIcs.DISC.2021.52</a>.","ama":"Chatterjee B, Peri S, Sa M. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">10.4230/LIPIcs.DISC.2021.52</a>","mla":"Chatterjee, Bapi, et al. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 52, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">10.4230/LIPIcs.DISC.2021.52</a>.","ista":"Chatterjee B, Peri S, Sa M. 2021. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 52.","short":"B. Chatterjee, S. Peri, M. Sa, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","apa":"Chatterjee, B., Peri, S., &#38; Sa, M. (2021). Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">https://doi.org/10.4230/LIPIcs.DISC.2021.52</a>","ieee":"B. Chatterjee, S. Peri, and M. Sa, “Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209."},"type":"conference","ddc":["000"],"abstract":[{"text":"This paper reports a new concurrent graph data structure that supports updates of both edges and vertices and queries: Breadth-first search, Single-source shortest-path, and Betweenness centrality. The operations are provably linearizable and non-blocking.","lang":"eng"}],"publication_status":"published","has_accepted_license":"1","status":"public","language":[{"iso":"eng"}],"quality_controlled":"1","publication":"35th International Symposium on Distributed Computing","file_date_updated":"2021-11-12T09:23:22Z","_id":"10216","external_id":{"arxiv":["2003.01697"]},"date_created":"2021-11-07T23:01:23Z","date_updated":"2021-11-12T09:42:55Z","title":"Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds","month":"10","article_processing_charge":"No","date_published":"2021-10-04T00:00:00Z","scopus_import":"1","volume":209,"alternative_title":["LIPIcs"],"article_number":"52","oa":1,"intvolume":"       209","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","acknowledgement":"This work was partially funded by National Supercomputing Mission, Govt. of India under the project “Concurrent and Distributed Programming primitives and algorithms for Temporal Graphs”(DST/NSM/R&D_Exascale/2021/16).\r\n"},{"publication_identifier":{"issn":["1868-8969"],"isbn":["9-783-9597-7210-5"]},"department":[{"_id":"DaAl"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"author":[{"last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Rati","last_name":"Gelashvili","full_name":"Gelashvili, Rati"},{"first_name":"Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","last_name":"Nadiradze","full_name":"Nadiradze, Giorgi"}],"year":"2021","conference":{"end_date":"2021-10-08","location":"Freiburg, Germany","start_date":"2021-10-04","name":"DISC: Distributed Computing"},"doi":"10.4230/LIPIcs.DISC.2021.4","oa_version":"Published Version","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","day":"04","publication_status":"published","abstract":[{"text":"This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registers, for both deterministic and randomized obstruction-free algorithms. The approach extends to lower bounds for deterministic and randomized obstruction-free algorithms using multi-writer registers under bounded write concurrency, showing a trade-off between the solo step complexity of a leader election algorithm, and the worst-case number of stalls incurred by a processor in an execution.","lang":"eng"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public","quality_controlled":"1","file":[{"access_level":"open_access","success":1,"file_name":"2021_LIPIcsDISC_Alistarh.pdf","file_size":706791,"content_type":"application/pdf","date_updated":"2021-11-12T09:33:26Z","relation":"main_file","checksum":"b4cdc6668c899a601c5e6a96b8ca54d9","date_created":"2021-11-12T09:33:26Z","creator":"cchlebak","file_id":"10277"}],"type":"conference","citation":{"ieee":"D.-A. Alistarh, R. Gelashvili, and G. Nadiradze, “Lower bounds for shared-memory leader election under bounded write contention,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","short":"D.-A. Alistarh, R. Gelashvili, G. Nadiradze, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","apa":"Alistarh, D.-A., Gelashvili, R., &#38; Nadiradze, G. (2021). Lower bounds for shared-memory leader election under bounded write contention. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">https://doi.org/10.4230/LIPIcs.DISC.2021.4</a>","ista":"Alistarh D-A, Gelashvili R, Nadiradze G. 2021. Lower bounds for shared-memory leader election under bounded write contention. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 4.","mla":"Alistarh, Dan-Adrian, et al. “Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 4, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">10.4230/LIPIcs.DISC.2021.4</a>.","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Giorgi Nadiradze. “Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">https://doi.org/10.4230/LIPIcs.DISC.2021.4</a>.","ama":"Alistarh D-A, Gelashvili R, Nadiradze G. Lower bounds for shared-memory leader election under bounded write contention. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">10.4230/LIPIcs.DISC.2021.4</a>"},"ddc":["000"],"title":"Lower bounds for shared-memory leader election under bounded write contention","date_updated":"2022-08-19T07:23:28Z","month":"10","date_published":"2021-10-04T00:00:00Z","article_processing_charge":"No","ec_funded":1,"file_date_updated":"2021-11-12T09:33:26Z","publication":"35th International Symposium on Distributed Computing","_id":"10217","project":[{"name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"}],"date_created":"2021-11-07T23:01:23Z","volume":209,"alternative_title":["LIPIcs"],"article_number":"4","acknowledgement":"Dan Alistarh: Supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Giorgi Nadiradze: Supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). The authors would like to thank the DISC anonymous reviewers for their useful\r\nfeedback and comments.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"intvolume":"       209","scopus_import":"1"},{"scopus_import":"1","oa":1,"intvolume":"       209","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 840605.","article_number":"43","alternative_title":["LIPIcs"],"volume":209,"external_id":{"arxiv":["2102.08808"]},"date_created":"2021-11-07T23:01:24Z","project":[{"name":"Coordination in constrained and natural distributed systems","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","grant_number":"840605","call_identifier":"H2020"}],"_id":"10218","publication":"35th International Symposium on Distributed Computing","file_date_updated":"2021-11-12T08:16:44Z","ec_funded":1,"article_processing_charge":"No","date_published":"2021-10-04T00:00:00Z","month":"10","date_updated":"2023-02-21T09:24:08Z","title":"Brief announcement: Fast graphical population protocols","ddc":["000"],"type":"conference","citation":{"short":"D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","apa":"Alistarh, D.-A., Gelashvili, R., &#38; Rybicki, J. (2021). Brief announcement: Fast graphical population protocols. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">https://doi.org/10.4230/LIPIcs.DISC.2021.43</a>","ieee":"D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Brief announcement: Fast graphical population protocols,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Brief Announcement: Fast Graphical Population Protocols.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">https://doi.org/10.4230/LIPIcs.DISC.2021.43</a>.","ama":"Alistarh D-A, Gelashvili R, Rybicki J. Brief announcement: Fast graphical population protocols. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">10.4230/LIPIcs.DISC.2021.43</a>","ista":"Alistarh D-A, Gelashvili R, Rybicki J. 2021. Brief announcement: Fast graphical population protocols. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 43.","mla":"Alistarh, Dan-Adrian, et al. “Brief Announcement: Fast Graphical Population Protocols.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">10.4230/LIPIcs.DISC.2021.43</a>."},"file":[{"file_name":"2021_LIPIcsDISC_Alistarh.pdf","access_level":"open_access","success":1,"relation":"main_file","checksum":"fd2a690f6856d21247e9aa952b0e2885","file_size":534219,"content_type":"application/pdf","date_updated":"2021-11-12T08:16:44Z","creator":"cchlebak","date_created":"2021-11-12T08:16:44Z","file_id":"10274"}],"quality_controlled":"1","status":"public","has_accepted_license":"1","language":[{"iso":"eng"}],"publication_status":"published","abstract":[{"text":"Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node. In this work, we consider the more general setting where G is an arbitrary graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As an example, this implies that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties.","lang":"eng"}],"day":"04","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"oa_version":"Published Version","doi":"10.4230/LIPIcs.DISC.2021.43","conference":{"location":"Freiburg, Germany","start_date":"2021-10-04","end_date":"2021-10-08","name":"DISC: Distributed Computing "},"year":"2021","author":[{"last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"},{"full_name":"Gelashvili, Rati","last_name":"Gelashvili","first_name":"Rati"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel","last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_identifier":{"isbn":["9-783-9597-7210-5"],"issn":["1868-8969"]},"department":[{"_id":"DaAl"}]},{"date_published":"2021-10-04T00:00:00Z","article_processing_charge":"No","ec_funded":1,"date_updated":"2021-11-12T09:37:18Z","title":"Brief announcement: Sinkless orientation is hard also in the supported LOCAL model","month":"10","_id":"10219","project":[{"grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning"}],"date_created":"2021-11-07T23:01:24Z","external_id":{"arxiv":["2108.02655"]},"file_date_updated":"2021-11-12T08:27:42Z","publication":"35th International Symposium on Distributed Computing","article_number":"58","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","acknowledgement":"Janne H. Korhonen: Project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Ami Paz: We acknowledge the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Stefan Schmid: Research supported by the Austrian Science Fund (FWF) project ADVISE, I 4800-N, 2020-2023.\r\n","oa":1,"intvolume":"       209","alternative_title":["LIPIcs"],"volume":209,"scopus_import":"1","author":[{"last_name":"Korhonen","full_name":"Korhonen, Janne","first_name":"Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425"},{"first_name":"Ami","full_name":"Paz, Ami","last_name":"Paz"},{"last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"first_name":"Jukka","full_name":"Suomela, Jukka","last_name":"Suomela"}],"conference":{"start_date":"2021-10-04","location":"Freiburg, Germany","end_date":"2021-10-08","name":"DISC: Distributed Computing "},"year":"2021","department":[{"_id":"DaAl"}],"publication_identifier":{"isbn":["9-783-9597-7210-5"],"issn":["1868-8969"]},"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","day":"04","doi":"10.4230/LIPIcs.DISC.2021.58","oa_version":"Published Version","arxiv":1,"quality_controlled":"1","abstract":[{"lang":"eng","text":"We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n)."}],"publication_status":"published","language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public","ddc":["000"],"file":[{"creator":"cchlebak","date_created":"2021-11-12T08:27:42Z","file_id":"10275","file_name":"2021_LIPIcsDISC_Korhonen.pdf","access_level":"open_access","success":1,"relation":"main_file","checksum":"c43188dc2070bbd2bf5fd6fdaf9ce36d","file_size":474242,"content_type":"application/pdf","date_updated":"2021-11-12T08:27:42Z"}],"citation":{"ieee":"J. Korhonen, A. Paz, J. Rybicki, S. Schmid, and J. Suomela, “Brief announcement: Sinkless orientation is hard also in the supported LOCAL model,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","short":"J. Korhonen, A. Paz, J. Rybicki, S. Schmid, J. Suomela, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","apa":"Korhonen, J., Paz, A., Rybicki, J., Schmid, S., &#38; Suomela, J. (2021). Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">https://doi.org/10.4230/LIPIcs.DISC.2021.58</a>","mla":"Korhonen, Janne, et al. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 58, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">10.4230/LIPIcs.DISC.2021.58</a>.","ista":"Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. 2021. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 58.","chicago":"Korhonen, Janne, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">https://doi.org/10.4230/LIPIcs.DISC.2021.58</a>.","ama":"Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">10.4230/LIPIcs.DISC.2021.58</a>"},"type":"conference"},{"language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public","publication_status":"published","abstract":[{"text":"The scalability of concurrent data structures and distributed algorithms strongly depends on\r\nreducing the contention for shared resources and the costs of synchronization and communication. We show how such cost reductions can be attained by relaxing the strict consistency conditions required by sequential implementations. In the first part of the thesis, we consider relaxation in the context of concurrent data structures. Specifically, in data structures \r\nsuch as priority queues, imposing strong semantics renders scalability impossible, since a correct implementation of the remove operation should return only the element with highest priority. Intuitively, attempting to invoke remove operations concurrently  creates a race condition. This bottleneck  can be circumvented by relaxing semantics of the affected data structure, thus allowing removal of the elements which are no longer required to have the highest priority. We prove that the randomized implementations of relaxed data structures provide provable guarantees on the priority of the removed elements even under concurrency. Additionally, we show that in some cases the relaxed data structures can be used to scale the classical algorithms which are usually implemented with the exact ones. In the second part, we study parallel variants of the  stochastic gradient descent (SGD) algorithm, which distribute computation  among the multiple processors, thus reducing the running time. Unfortunately, in order for standard parallel SGD to succeed, each processor has to maintain a local copy of the necessary model parameter, which is identical to the local copies of other processors; the overheads from this perfect consistency in terms of communication and synchronization can negate the speedup gained by distributing the computation. We show that the consistency conditions required by SGD can be  relaxed, allowing the algorithm to be more flexible in terms of tolerating quantized communication, asynchrony, or even crash faults, while its convergence remains asymptotically the same.","lang":"eng"}],"ddc":["000"],"citation":{"ama":"Nadiradze G. On achieving scalability through relaxation. 2021. doi:<a href=\"https://doi.org/10.15479/at:ista:10429\">10.15479/at:ista:10429</a>","chicago":"Nadiradze, Giorgi. “On Achieving Scalability through Relaxation.” Institute of Science and Technology Austria, 2021. <a href=\"https://doi.org/10.15479/at:ista:10429\">https://doi.org/10.15479/at:ista:10429</a>.","ista":"Nadiradze G. 2021. On achieving scalability through relaxation. Institute of Science and Technology Austria.","mla":"Nadiradze, Giorgi. <i>On Achieving Scalability through Relaxation</i>. Institute of Science and Technology Austria, 2021, doi:<a href=\"https://doi.org/10.15479/at:ista:10429\">10.15479/at:ista:10429</a>.","apa":"Nadiradze, G. (2021). <i>On achieving scalability through relaxation</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:10429\">https://doi.org/10.15479/at:ista:10429</a>","short":"G. Nadiradze, On Achieving Scalability through Relaxation, Institute of Science and Technology Austria, 2021.","ieee":"G. Nadiradze, “On achieving scalability through relaxation,” Institute of Science and Technology Austria, 2021."},"type":"dissertation","file":[{"file_size":2370859,"content_type":"application/pdf","date_updated":"2021-12-09T17:47:49Z","checksum":"6bf14e9a523387328f016c0689f5e10e","relation":"main_file","access_level":"open_access","success":1,"file_name":"Thesis_Final_09_12_2021.pdf","file_id":"10436","date_created":"2021-12-09T17:47:49Z","creator":"gnadirad"},{"file_name":"Thesis_Final_09_12_2021.zip","access_level":"closed","relation":"source_file","checksum":"914d6c5ca86bd0add471971a8f4c4341","content_type":"application/zip","date_updated":"2022-03-28T12:55:12Z","file_size":2596924,"date_created":"2021-12-09T17:47:49Z","creator":"gnadirad","file_id":"10437"}],"author":[{"orcid":"0000-0001-5634-0731","full_name":"Nadiradze, Giorgi","last_name":"Nadiradze","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","first_name":"Giorgi"}],"year":"2021","degree_awarded":"PhD","department":[{"_id":"GradSch"},{"_id":"DaAl"}],"publication_identifier":{"issn":["2663-337X"]},"day":"09","publisher":"Institute of Science and Technology Austria","oa_version":"Published Version","doi":"10.15479/at:ista:10429","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa":1,"alternative_title":["ISTA Thesis"],"related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"10432"},{"id":"6673","relation":"part_of_dissertation","status":"public"},{"id":"5965","status":"public","relation":"part_of_dissertation"},{"status":"public","relation":"part_of_dissertation","id":"10435"}]},"ec_funded":1,"date_published":"2021-12-09T00:00:00Z","article_processing_charge":"No","month":"12","title":"On achieving scalability through relaxation","date_updated":"2023-10-17T11:48:55Z","date_created":"2021-12-08T21:52:28Z","_id":"10429","project":[{"call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning"}],"page":"132","file_date_updated":"2022-03-28T12:55:12Z","supervisor":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"}]}]