[{"oa_version":"Published Version","quality_controlled":"1","_id":"6972","doi":"10.1145/3339471","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"},"citation":{"apa":"Lenzen, C., &#38; Rybicki, J. (2019). Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/3339471\">https://doi.org/10.1145/3339471</a>","ista":"Lenzen C, Rybicki J. 2019. Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. Journal of the ACM. 66(5), 32.","ama":"Lenzen C, Rybicki J. Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. <i>Journal of the ACM</i>. 2019;66(5). doi:<a href=\"https://doi.org/10.1145/3339471\">10.1145/3339471</a>","mla":"Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus.” <i>Journal of the ACM</i>, vol. 66, no. 5, 32, ACM, 2019, doi:<a href=\"https://doi.org/10.1145/3339471\">10.1145/3339471</a>.","ieee":"C. Lenzen and J. Rybicki, “Self-stabilising Byzantine clock synchronisation is almost as easy as consensus,” <i>Journal of the ACM</i>, vol. 66, no. 5. ACM, 2019.","short":"C. Lenzen, J. Rybicki, Journal of the ACM 66 (2019).","chicago":"Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus.” <i>Journal of the ACM</i>. ACM, 2019. <a href=\"https://doi.org/10.1145/3339471\">https://doi.org/10.1145/3339471</a>."},"project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"volume":66,"scopus_import":"1","department":[{"_id":"DaAl"}],"date_updated":"2025-04-14T07:44:06Z","title":"Self-stabilising Byzantine clock synchronisation is almost as easy as consensus","author":[{"last_name":"Lenzen","first_name":"Christoph","full_name":"Lenzen, Christoph"},{"last_name":"Rybicki","orcid":"0000-0002-6432-6646","first_name":"Joel","full_name":"Rybicki, Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"isi":["000496514100001"],"arxiv":["1705.06173"]},"license":"https://creativecommons.org/licenses/by/4.0/","arxiv":1,"article_type":"original","file_date_updated":"2020-07-14T12:47:46Z","publication_identifier":{"issn":["0004-5411"]},"day":"01","month":"09","publication":"Journal of the ACM","corr_author":"1","ddc":["000"],"status":"public","issue":"5","intvolume":"        66","language":[{"iso":"eng"}],"publisher":"ACM","date_created":"2019-10-24T17:12:48Z","abstract":[{"lang":"eng","text":"We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of thennodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e.,the initial state of the system may be arbitrary, and there can be up to f<n/3 ongoing Byzantine faults, i.e.,nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks ofthe nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model,we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodesgenerate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner.Compared to prior work, we achieveexponentialimprovements in stabilisation time and the number ofcommunicated bits, and give the first sublinear-time algorithm for the problem:•In the deterministic setting, the state-of-the-art solutions stabilise in timeΘ(f)and have each nodebroadcastΘ(flogf)bits per time unit. We exponentially reduce the number of bits broadcasted pertime unit toΘ(logf)while retaining the same stabilisation time.•In the randomised setting, the state-of-the-art solutions stabilise in timeΘ(f)and have each nodebroadcastO(1)bits per time unit. We exponentially reduce the stabilisation time to polylogfwhileeach node broadcasts polylogfbits per time unit.These results are obtained by means of a recursive approach reducing the above task ofself-stabilisingpulse synchronisation in thebounded-delaymodel tonon-self-stabilisingbinary consensus in thesynchro-nousmodel. In general, our approach introduces at most logarithmic overheads in terms of stabilisation timeand broadcasted bits over the underlying consensus routine."}],"has_accepted_license":"1","date_published":"2019-09-01T00:00:00Z","article_number":"32","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","file":[{"file_id":"6975","date_updated":"2020-07-14T12:47:46Z","date_created":"2019-10-25T12:58:38Z","relation":"main_file","checksum":"7e5d95c478e0e393f4927fcf7e48194e","file_name":"2019_JACM_Lenzen.pdf","creator":"dernst","file_size":2183085,"access_level":"open_access","content_type":"application/pdf"}],"year":"2019","article_processing_charge":"Yes","publication_status":"published","oa":1,"ec_funded":1,"type":"journal_article","isi":1},{"publication_status":"published","year":"2019","article_processing_charge":"No","author":[{"full_name":"Khirirat, Sarit","last_name":"Khirirat","first_name":"Sarit"},{"full_name":"Johansson, Mikael","first_name":"Mikael","last_name":"Johansson"},{"last_name":"Alistarh","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"Gradient compression for communication-limited convex optimization","date_published":"2019-01-21T00:00:00Z","date_updated":"2023-09-06T11:14:55Z","article_number":"8619625","day":"21","publication_identifier":{"isbn":["9781538613955"],"issn":["0743-1546"]},"conference":{"end_date":"2018-12-19","location":"Miami Beach, FL, United States","name":"CDC: Conference on Decision and Control","start_date":"2018-12-17"},"isi":1,"type":"conference","external_id":{"isi":["000458114800023"]},"_id":"7122","publication":"2018 IEEE Conference on Decision and Control","month":"01","status":"public","oa_version":"None","quality_controlled":"1","department":[{"_id":"DaAl"}],"date_created":"2019-11-26T15:07:49Z","scopus_import":"1","abstract":[{"text":"Data-rich applications in machine-learning and control have motivated an intense research on large-scale optimization. Novel algorithms have been proposed and shown to have optimal convergence rates in terms of iteration counts. However, their practical performance is severely degraded by the cost of exchanging high-dimensional gradient vectors between computing nodes. Several gradient compression heuristics have recently been proposed to reduce communications, but few theoretical results exist that quantify how they impact algorithm convergence. This paper establishes and strengthens the convergence guarantees for gradient descent under a family of gradient compression techniques. For convex optimization problems, we derive admissible step sizes and quantify both the number of iterations and the number of bits that need to be exchanged to reach a target accuracy. Finally, we validate the performance of different gradient compression techniques in simulations. The numerical results highlight the properties of different gradient compression algorithms and confirm that fast convergence with limited information exchange is possible.","lang":"eng"}],"publisher":"IEEE","language":[{"iso":"eng"}],"citation":{"chicago":"Khirirat, Sarit, Mikael Johansson, and Dan-Adrian Alistarh. “Gradient Compression for Communication-Limited Convex Optimization.” In <i>2018 IEEE Conference on Decision and Control</i>. IEEE, 2019. <a href=\"https://doi.org/10.1109/cdc.2018.8619625\">https://doi.org/10.1109/cdc.2018.8619625</a>.","short":"S. Khirirat, M. Johansson, D.-A. Alistarh, in:, 2018 IEEE Conference on Decision and Control, IEEE, 2019.","ieee":"S. Khirirat, M. Johansson, and D.-A. Alistarh, “Gradient compression for communication-limited convex optimization,” in <i>2018 IEEE Conference on Decision and Control</i>, Miami Beach, FL, United States, 2019.","mla":"Khirirat, Sarit, et al. “Gradient Compression for Communication-Limited Convex Optimization.” <i>2018 IEEE Conference on Decision and Control</i>, 8619625, IEEE, 2019, doi:<a href=\"https://doi.org/10.1109/cdc.2018.8619625\">10.1109/cdc.2018.8619625</a>.","apa":"Khirirat, S., Johansson, M., &#38; Alistarh, D.-A. (2019). Gradient compression for communication-limited convex optimization. In <i>2018 IEEE Conference on Decision and Control</i>. Miami Beach, FL, United States: IEEE. <a href=\"https://doi.org/10.1109/cdc.2018.8619625\">https://doi.org/10.1109/cdc.2018.8619625</a>","ista":"Khirirat S, Johansson M, Alistarh D-A. 2019. Gradient compression for communication-limited convex optimization. 2018 IEEE Conference on Decision and Control. CDC: Conference on Decision and Control, 8619625.","ama":"Khirirat S, Johansson M, Alistarh D-A. Gradient compression for communication-limited convex optimization. In: <i>2018 IEEE Conference on Decision and Control</i>. IEEE; 2019. doi:<a href=\"https://doi.org/10.1109/cdc.2018.8619625\">10.1109/cdc.2018.8619625</a>"},"doi":"10.1109/cdc.2018.8619625"},{"language":[{"iso":"eng"}],"publisher":"ACM","abstract":[{"lang":"eng","text":"Applying machine learning techniques to the quickly growing data in science and industry requires highly-scalable algorithms. Large datasets are most commonly processed \"data parallel\" distributed across many nodes. Each node's contribution to the overall gradient is summed using a global allreduce. This allreduce is the single communication and thus scalability bottleneck for most machine learning workloads. We observe that frequently, many gradient values are (close to) zero, leading to sparse of sparsifyable communications. To exploit this insight, we analyze, design, and implement a set of communication-efficient protocols for sparse input data, in conjunction with efficient machine learning algorithms which can leverage these primitives. Our communication protocols generalize standard collective operations, by allowing processes to contribute arbitrary sparse input data vectors. Our generic communication library, SparCML1, extends MPI to support additional features, such as non-blocking (asynchronous) operations and low-precision data representations. As such, SparCML and its techniques will form the basis of future highly-scalable machine learning frameworks."}],"date_created":"2019-12-22T23:00:42Z","status":"public","publication":"International Conference for High Performance Computing, Networking, Storage and Analysis, SC","month":"11","oa":1,"ec_funded":1,"isi":1,"type":"conference","date_published":"2019-11-17T00:00:00Z","article_number":"a11","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","article_processing_charge":"No","year":"2019","doi":"10.1145/3295500.3356222","citation":{"ista":"Renggli C, Ashkboos S, Aghagolzadeh M, Alistarh D-A, Hoefler T. 2019. SparCML: High-performance sparse communication for machine learning. International Conference for High Performance Computing, Networking, Storage and Analysis, SC. SC: Conference for High Performance Computing, Networking, Storage and Analysis, a11.","ama":"Renggli C, Ashkboos S, Aghagolzadeh M, Alistarh D-A, Hoefler T. SparCML: High-performance sparse communication for machine learning. In: <i>International Conference for High Performance Computing, Networking, Storage and Analysis, SC</i>. ACM; 2019. doi:<a href=\"https://doi.org/10.1145/3295500.3356222\">10.1145/3295500.3356222</a>","apa":"Renggli, C., Ashkboos, S., Aghagolzadeh, M., Alistarh, D.-A., &#38; Hoefler, T. (2019). SparCML: High-performance sparse communication for machine learning. In <i>International Conference for High Performance Computing, Networking, Storage and Analysis, SC</i>. Denver, CO, Unites States: ACM. <a href=\"https://doi.org/10.1145/3295500.3356222\">https://doi.org/10.1145/3295500.3356222</a>","mla":"Renggli, Cedric, et al. “SparCML: High-Performance Sparse Communication for Machine Learning.” <i>International Conference for High Performance Computing, Networking, Storage and Analysis, SC</i>, a11, ACM, 2019, doi:<a href=\"https://doi.org/10.1145/3295500.3356222\">10.1145/3295500.3356222</a>.","ieee":"C. Renggli, S. Ashkboos, M. Aghagolzadeh, D.-A. Alistarh, and T. Hoefler, “SparCML: High-performance sparse communication for machine learning,” in <i>International Conference for High Performance Computing, Networking, Storage and Analysis, SC</i>, Denver, CO, Unites States, 2019.","short":"C. Renggli, S. Ashkboos, M. Aghagolzadeh, D.-A. Alistarh, T. Hoefler, in:, International Conference for High Performance Computing, Networking, Storage and Analysis, SC, ACM, 2019.","chicago":"Renggli, Cedric, Saleh Ashkboos, Mehdi Aghagolzadeh, Dan-Adrian Alistarh, and Torsten Hoefler. “SparCML: High-Performance Sparse Communication for Machine Learning.” In <i>International Conference for High Performance Computing, Networking, Storage and Analysis, SC</i>. ACM, 2019. <a href=\"https://doi.org/10.1145/3295500.3356222\">https://doi.org/10.1145/3295500.3356222</a>."},"project":[{"grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"scopus_import":"1","department":[{"_id":"DaAl"}],"oa_version":"Preprint","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1802.08021"}],"_id":"7201","external_id":{"arxiv":["1802.08021"],"isi":["000545976800011"]},"conference":{"name":"SC: Conference for High Performance Computing, Networking, Storage and Analysis","location":"Denver, CO, Unites States","start_date":"2019-11-17","end_date":"2019-11-19"},"arxiv":1,"day":"17","publication_identifier":{"eissn":["2167-4337"],"isbn":["9781450362290"],"issn":["2167-4329"]},"title":"SparCML: High-performance sparse communication for machine learning","date_updated":"2025-07-10T11:54:21Z","author":[{"first_name":"Cedric","last_name":"Renggli","full_name":"Renggli, Cedric"},{"full_name":"Ashkboos, Saleh","id":"0D0A9058-257B-11EA-A937-9341C3D8BC8A","last_name":"Ashkboos","first_name":"Saleh"},{"last_name":"Aghagolzadeh","first_name":"Mehdi","full_name":"Aghagolzadeh, Mehdi"},{"last_name":"Alistarh","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Hoefler, Torsten","first_name":"Torsten","last_name":"Hoefler"}]},{"date_updated":"2026-04-16T08:35:00Z","title":"Recovering rearranged cancer chromosomes from karyotype graphs","author":[{"last_name":"Aganezov","first_name":"Sergey","full_name":"Aganezov, Sergey"},{"last_name":"Zban","first_name":"Ilya","full_name":"Zban, Ilya"},{"full_name":"Aksenov, Vitalii","id":"2980135A-F248-11E8-B48F-1D18A9856A87","first_name":"Vitalii","last_name":"Aksenov"},{"first_name":"Nikita","last_name":"Alexeev","full_name":"Alexeev, Nikita"},{"last_name":"Schatz","first_name":"Michael C.","full_name":"Schatz, Michael C."}],"external_id":{"isi":["000511618800007"]},"publication_identifier":{"eissn":["1471-2105"]},"file_date_updated":"2020-07-14T12:47:54Z","article_type":"original","day":"17","_id":"7214","oa_version":"Published Version","quality_controlled":"1","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"},"doi":"10.1186/s12859-019-3208-4","citation":{"ama":"Aganezov S, Zban I, Aksenov V, Alexeev N, Schatz MC. Recovering rearranged cancer chromosomes from karyotype graphs. <i>BMC Bioinformatics</i>. 2019;20. doi:<a href=\"https://doi.org/10.1186/s12859-019-3208-4\">10.1186/s12859-019-3208-4</a>","apa":"Aganezov, S., Zban, I., Aksenov, V., Alexeev, N., &#38; Schatz, M. C. (2019). Recovering rearranged cancer chromosomes from karyotype graphs. <i>BMC Bioinformatics</i>. BMC. <a href=\"https://doi.org/10.1186/s12859-019-3208-4\">https://doi.org/10.1186/s12859-019-3208-4</a>","ista":"Aganezov S, Zban I, Aksenov V, Alexeev N, Schatz MC. 2019. Recovering rearranged cancer chromosomes from karyotype graphs. BMC Bioinformatics. 20, 641.","mla":"Aganezov, Sergey, et al. “Recovering Rearranged Cancer Chromosomes from Karyotype Graphs.” <i>BMC Bioinformatics</i>, vol. 20, 641, BMC, 2019, doi:<a href=\"https://doi.org/10.1186/s12859-019-3208-4\">10.1186/s12859-019-3208-4</a>.","ieee":"S. Aganezov, I. Zban, V. Aksenov, N. Alexeev, and M. C. Schatz, “Recovering rearranged cancer chromosomes from karyotype graphs,” <i>BMC Bioinformatics</i>, vol. 20. BMC, 2019.","short":"S. Aganezov, I. Zban, V. Aksenov, N. Alexeev, M.C. Schatz, BMC Bioinformatics 20 (2019).","chicago":"Aganezov, Sergey, Ilya Zban, Vitalii Aksenov, Nikita Alexeev, and Michael C. Schatz. “Recovering Rearranged Cancer Chromosomes from Karyotype Graphs.” <i>BMC Bioinformatics</i>. BMC, 2019. <a href=\"https://doi.org/10.1186/s12859-019-3208-4\">https://doi.org/10.1186/s12859-019-3208-4</a>."},"department":[{"_id":"DaAl"}],"scopus_import":"1","volume":20,"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","date_published":"2019-12-17T00:00:00Z","article_number":"641","article_processing_charge":"No","year":"2019","publication_status":"published","file":[{"date_updated":"2020-07-14T12:47:54Z","file_id":"7221","content_type":"application/pdf","access_level":"open_access","file_size":1917374,"file_name":"2019_BMCBioinfo_Aganezov.pdf","creator":"dernst","checksum":"7a30357efdcf8f66587ed495c0927724","relation":"main_file","date_created":"2020-01-02T16:10:58Z"}],"type":"journal_article","isi":1,"oa":1,"month":"12","publication":"BMC Bioinformatics","status":"public","ddc":["570"],"language":[{"iso":"eng"}],"intvolume":"        20","abstract":[{"lang":"eng","text":"Background: Many cancer genomes are extensively rearranged with highly aberrant chromosomal karyotypes. Structural and copy number variations in cancer genomes can be determined via abnormal mapping of sequenced reads to the reference genome. Recently it became possible to reconcile both of these types of large-scale variations into a karyotype graph representation of the rearranged cancer genomes. Such a representation, however, does not directly describe the linear and/or circular structure of the underlying rearranged cancer chromosomes, thus limiting possible analysis of cancer genomes somatic evolutionary process as well as functional genomic changes brought by the large-scale genome rearrangements.\r\n\r\nResults: Here we address the aforementioned limitation by introducing a novel methodological framework for recovering rearranged cancer chromosomes from karyotype graphs. For a cancer karyotype graph we formulate an Eulerian Decomposition Problem (EDP) of finding a collection of linear and/or circular rearranged cancer chromosomes that are determined by the graph. We derive and prove computational complexities for several variations of the EDP. We then demonstrate that Eulerian decomposition of the cancer karyotype graphs is not always unique and present the Consistent Contig Covering Problem (CCCP) of recovering unambiguous cancer contigs from the cancer karyotype graph, and describe a novel algorithm CCR capable of solving CCCP in polynomial time. We apply CCR on a prostate cancer dataset and demonstrate that it is capable of consistently recovering large cancer contigs even when underlying cancer genomes are highly rearranged.\r\n\r\nConclusions: CCR can recover rearranged cancer contigs from karyotype graphs thereby addressing existing limitation in inferring chromosomal structures of rearranged cancer genomes and advancing our understanding of both patient/cancer-specific as well as the overall genetic instability in cancer."}],"date_created":"2019-12-29T23:00:46Z","has_accepted_license":"1","publisher":"BMC"},{"day":"13","publication_identifier":{"isbn":["978-3-0302-9399-4"],"issn":["0302-9743"],"eissn":["1611-3349"]},"conference":{"start_date":"2019-08-26","name":"Euro-Par: European Conference on Parallel Processing","location":"Göttingen, Germany","end_date":"2019-08-30"},"external_id":{"isi":["000851061400023"]},"author":[{"first_name":"Nikita","last_name":"Koval","full_name":"Koval, Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"first_name":"Roman","last_name":"Elizarov","full_name":"Elizarov, Roman"}],"title":"Scalable FIFO channels for programming via communicating sequential processes","date_updated":"2023-09-06T14:53:59Z","scopus_import":"1","department":[{"_id":"DaAl"}],"volume":11725,"citation":{"chicago":"Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. “Scalable FIFO Channels for Programming via Communicating Sequential Processes.” In <i>25th Anniversary of Euro-Par</i>, 11725:317–33. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-29400-7_23\">https://doi.org/10.1007/978-3-030-29400-7_23</a>.","short":"N. Koval, D.-A. Alistarh, R. Elizarov, in:, 25th Anniversary of Euro-Par, Springer Nature, 2019, pp. 317–333.","mla":"Koval, Nikita, et al. “Scalable FIFO Channels for Programming via Communicating Sequential Processes.” <i>25th Anniversary of Euro-Par</i>, vol. 11725, Springer Nature, 2019, pp. 317–33, doi:<a href=\"https://doi.org/10.1007/978-3-030-29400-7_23\">10.1007/978-3-030-29400-7_23</a>.","ieee":"N. Koval, D.-A. Alistarh, and R. Elizarov, “Scalable FIFO channels for programming via communicating sequential processes,” in <i>25th Anniversary of Euro-Par</i>, Göttingen, Germany, 2019, vol. 11725, pp. 317–333.","ista":"Koval N, Alistarh D-A, Elizarov R. 2019. Scalable FIFO channels for programming via communicating sequential processes. 25th Anniversary of Euro-Par. Euro-Par: European Conference on Parallel Processing, LNCS, vol. 11725, 317–333.","ama":"Koval N, Alistarh D-A, Elizarov R. Scalable FIFO channels for programming via communicating sequential processes. In: <i>25th Anniversary of Euro-Par</i>. Vol 11725. Springer Nature; 2019:317-333. doi:<a href=\"https://doi.org/10.1007/978-3-030-29400-7_23\">10.1007/978-3-030-29400-7_23</a>","apa":"Koval, N., Alistarh, D.-A., &#38; Elizarov, R. (2019). Scalable FIFO channels for programming via communicating sequential processes. In <i>25th Anniversary of Euro-Par</i> (Vol. 11725, pp. 317–333). Göttingen, Germany: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-29400-7_23\">https://doi.org/10.1007/978-3-030-29400-7_23</a>"},"doi":"10.1007/978-3-030-29400-7_23","_id":"7228","quality_controlled":"1","oa_version":"None","page":"317-333","isi":1,"type":"conference","publication_status":"published","article_processing_charge":"No","year":"2019","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_published":"2019-08-13T00:00:00Z","date_created":"2020-01-05T23:00:46Z","abstract":[{"lang":"eng","text":"Traditional concurrent programming involves manipulating shared mutable state. Alternatives to this programming style are communicating sequential processes (CSP) and actor models, which share data via explicit communication. These models have been known for almost half a century, and have recently had started to gain significant traction among modern programming languages. The common abstraction for communication between several processes is the channel. Although channels are similar to producer-consumer data structures, they have different semantics and support additional operations, such as the select expression. Despite their growing popularity, most known implementations of channels use lock-based data structures and can be rather inefficient.\r\n\r\nIn this paper, we present the first efficient lock-free algorithm for implementing a communication channel for CSP programming. We provide implementations and experimental results in the Kotlin and Go programming languages. Our new algorithm outperforms existing implementations on many workloads, while providing non-blocking progress guarantee. Our design can serve as an example of how to construct general communication data structures for CSP and actor models. "}],"alternative_title":["LNCS"],"publisher":"Springer Nature","language":[{"iso":"eng"}],"intvolume":"     11725","month":"08","status":"public","publication":"25th Anniversary of Euro-Par"},{"main_file_link":[{"url":"http://papers.nips.cc/paper/8379-powerset-convolutional-neural-networks","open_access":"1"}],"quality_controlled":"1","oa_version":"Published Version","_id":"7542","citation":{"short":"C. Wendler, D.-A. Alistarh, M. Püschel, in:, Neural Information Processing Systems Foundation, 2019, pp. 927–938.","chicago":"Wendler, Chris, Dan-Adrian Alistarh, and Markus Püschel. “Powerset Convolutional Neural Networks,” 32:927–38. Neural Information Processing Systems Foundation, 2019.","ama":"Wendler C, Alistarh D-A, Püschel M. Powerset convolutional neural networks. In: Vol 32. Neural Information Processing Systems Foundation; 2019:927-938.","apa":"Wendler, C., Alistarh, D.-A., &#38; Püschel, M. (2019). Powerset convolutional neural networks (Vol. 32, pp. 927–938). Presented at the NIPS: Conference on Neural Information Processing Systems, Vancouver, Canada: Neural Information Processing Systems Foundation.","ista":"Wendler C, Alistarh D-A, Püschel M. 2019. Powerset convolutional neural networks. NIPS: Conference on Neural Information Processing Systems vol. 32, 927–938.","ieee":"C. Wendler, D.-A. Alistarh, and M. Püschel, “Powerset convolutional neural networks,” presented at the NIPS: Conference on Neural Information Processing Systems, Vancouver, Canada, 2019, vol. 32, pp. 927–938.","mla":"Wendler, Chris, et al. <i>Powerset Convolutional Neural Networks</i>. Vol. 32, Neural Information Processing Systems Foundation, 2019, pp. 927–38."},"project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"volume":32,"department":[{"_id":"DaAl"}],"date_updated":"2026-06-18T19:23:08Z","title":"Powerset convolutional neural networks","author":[{"full_name":"Wendler, Chris","last_name":"Wendler","first_name":"Chris"},{"full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian"},{"last_name":"Püschel","first_name":"Markus","full_name":"Püschel, Markus"}],"external_id":{"arxiv":["1909.02253"],"isi":["000534424300084"]},"conference":{"name":"NIPS: Conference on Neural Information Processing Systems","location":"Vancouver, Canada","start_date":"2019-12-08","end_date":"2019-12-14"},"arxiv":1,"publication_identifier":{"issn":["1049-5258"]},"day":"01","status":"public","ddc":["000"],"month":"12","intvolume":"        32","language":[{"iso":"eng"}],"publisher":"Neural Information Processing Systems Foundation","date_created":"2020-02-28T10:03:24Z","abstract":[{"text":"We present a novel class of convolutional neural networks (CNNs) for set functions,i.e., data indexed with the powerset of a finite set. The convolutions are derivedas linear, shift-equivariant functions for various notions of shifts on set functions.The framework is fundamentally different from graph convolutions based on theLaplacian, as it provides not one but several basic shifts, one for each element inthe ground set. Prototypical experiments with several set function classificationtasks on synthetic datasets and on datasets derived from real-world hypergraphsdemonstrate the potential of our new powerset CNNs.","lang":"eng"}],"date_published":"2019-12-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2019","article_processing_charge":"No","publication_status":"published","oa":1,"type":"conference","isi":1,"ec_funded":1,"page":"927-938"},{"volume":"2019-June","scopus_import":"1","department":[{"_id":"DaAl"}],"citation":{"chicago":"Yu, Chen, Hanlin Tang, Cedric Renggli, Simon Kassing, Ankit Singla, Dan-Adrian Alistarh, Ce Zhang, and Ji Liu. “Distributed Learning over Unreliable Networks.” In <i>36th International Conference on Machine Learning</i>, 2019–June:12481–512. IMLS, 2019.","short":"C. Yu, H. Tang, C. Renggli, S. Kassing, A. Singla, D.-A. Alistarh, C. Zhang, J. Liu, in:, 36th International Conference on Machine Learning, IMLS, 2019, pp. 12481–12512.","mla":"Yu, Chen, et al. “Distributed Learning over Unreliable Networks.” <i>36th International Conference on Machine Learning</i>, vol. 2019–June, IMLS, 2019, pp. 12481–512.","ieee":"C. Yu <i>et al.</i>, “Distributed learning over unreliable networks,” in <i>36th International Conference on Machine Learning</i>, Long Beach, CA, United States, 2019, vol. 2019–June, pp. 12481–12512.","ama":"Yu C, Tang H, Renggli C, et al. Distributed learning over unreliable networks. In: <i>36th International Conference on Machine Learning</i>. Vol 2019-June. IMLS; 2019:12481-12512.","apa":"Yu, C., Tang, H., Renggli, C., Kassing, S., Singla, A., Alistarh, D.-A., … Liu, J. (2019). Distributed learning over unreliable networks. In <i>36th International Conference on Machine Learning</i> (Vol. 2019–June, pp. 12481–12512). Long Beach, CA, United States: IMLS.","ista":"Yu C, Tang H, Renggli C, Kassing S, Singla A, Alistarh D-A, Zhang C, Liu J. 2019. Distributed learning over unreliable networks. 36th International Conference on Machine Learning. ICML: International Conference on Machine Learning vol. 2019–June, 12481–12512."},"quality_controlled":"1","oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1810.07766","open_access":"1"}],"_id":"7437","arxiv":1,"day":"01","publication_identifier":{"isbn":["9781510886988"]},"external_id":{"isi":["000684034307036"],"arxiv":["1810.07766"]},"conference":{"start_date":"2019-06-10","location":"Long Beach, CA, United States","name":"ICML: International Conference on Machine Learning","end_date":"2019-06-15"},"author":[{"full_name":"Yu, Chen","first_name":"Chen","last_name":"Yu"},{"full_name":"Tang, Hanlin","last_name":"Tang","first_name":"Hanlin"},{"first_name":"Cedric","last_name":"Renggli","full_name":"Renggli, Cedric"},{"full_name":"Kassing, Simon","first_name":"Simon","last_name":"Kassing"},{"full_name":"Singla, Ankit","first_name":"Ankit","last_name":"Singla"},{"last_name":"Alistarh","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Zhang, Ce","last_name":"Zhang","first_name":"Ce"},{"first_name":"Ji","last_name":"Liu","full_name":"Liu, Ji"}],"title":"Distributed learning over unreliable networks","date_updated":"2026-07-07T13:41:57Z","publisher":"IMLS","date_created":"2020-02-02T23:01:06Z","abstract":[{"lang":"eng","text":"Most of today's distributed machine learning systems assume reliable networks: whenever two machines exchange information (e.g., gradients or models), the network should guarantee the delivery of the message. At the same time, recent work exhibits the impressive tolerance of machine learning algorithms to errors or noise arising from relaxed communication or synchronization. In this paper, we connect these two trends, and consider the following question: Can we design machine learning systems that are tolerant to network unreliability during training? With this motivation, we focus on a theoretical problem of independent interest-given a standard distributed parameter server architecture, if every communication between the worker and the server has a non-zero probability p of being dropped, does there exist an algorithm that still converges, and at what speed? The technical contribution of this paper is a novel theoretical analysis proving that distributed learning over unreliable network can achieve comparable convergence rate to centralized or distributed learning over reliable networks. Further, we prove that the influence of the packet drop rate diminishes with the growth of the number of parameter servers. We map this theoretical result onto a real-world scenario, training deep neural networks over an unreliable network layer, and conduct network simulation to validate the system improvement by allowing the networks to be unreliable."}],"language":[{"iso":"eng"}],"publication":"36th International Conference on Machine Learning","status":"public","month":"06","das_tickbox":"1","page":"12481-12512","oa":1,"type":"conference","isi":1,"publication_status":"published","article_processing_charge":"No","year":"2019","date_published":"2019-06-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"_id":"5947","oa_version":"Published Version","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1145/3288599.3288617"}],"citation":{"short":"B. Chatterjee, S. Peri, M. Sa, N. Singhal, in:, ACM International Conference Proceeding Series, ACM, 2019, pp. 168–177.","chicago":"Chatterjee, Bapi, Sathya Peri, Muktikanta Sa, and Nandini Singhal. “A Simple and Practical Concurrent Non-Blocking Unbounded Graph with Linearizable Reachability Queries.” In <i>ACM International Conference Proceeding Series</i>, 168–77. ACM, 2019. <a href=\"https://doi.org/10.1145/3288599.3288617\">https://doi.org/10.1145/3288599.3288617</a>.","ista":"Chatterjee B, Peri S, Sa M, Singhal N. 2019. A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries. ACM International Conference Proceeding Series. ICDCN: Conference on Distributed Computing and Networking, 168–177.","apa":"Chatterjee, B., Peri, S., Sa, M., &#38; Singhal, N. (2019). A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries. In <i>ACM International Conference Proceeding Series</i> (pp. 168–177). Bangalore, India: ACM. <a href=\"https://doi.org/10.1145/3288599.3288617\">https://doi.org/10.1145/3288599.3288617</a>","ama":"Chatterjee B, Peri S, Sa M, Singhal N. A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries. In: <i>ACM International Conference Proceeding Series</i>. ACM; 2019:168-177. doi:<a href=\"https://doi.org/10.1145/3288599.3288617\">10.1145/3288599.3288617</a>","ieee":"B. Chatterjee, S. Peri, M. Sa, and N. Singhal, “A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries,” in <i>ACM International Conference Proceeding Series</i>, Bangalore, India, 2019, pp. 168–177.","mla":"Chatterjee, Bapi, et al. “A Simple and Practical Concurrent Non-Blocking Unbounded Graph with Linearizable Reachability Queries.” <i>ACM International Conference Proceeding Series</i>, ACM, 2019, pp. 168–77, doi:<a href=\"https://doi.org/10.1145/3288599.3288617\">10.1145/3288599.3288617</a>."},"doi":"10.1145/3288599.3288617","scopus_import":"1","department":[{"_id":"DaAl"}],"title":"A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries","date_updated":"2026-07-28T13:34:36Z","author":[{"last_name":"Chatterjee","orcid":"0000-0002-2742-4028","first_name":"Bapi","full_name":"Chatterjee, Bapi","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Sathya","last_name":"Peri","full_name":"Peri, Sathya"},{"full_name":"Sa, Muktikanta","last_name":"Sa","first_name":"Muktikanta"},{"last_name":"Singhal","first_name":"Nandini","full_name":"Singhal, Nandini"}],"conference":{"end_date":"2019-01-07","start_date":"2019-01-04","location":"Bangalore, India","name":"ICDCN: Conference on Distributed Computing and Networking"},"OA_place":"publisher","external_id":{"isi":["000484491600019"],"arxiv":["1809.00896"]},"day":"04","publication_identifier":{"isbn":["978-1-4503-6094-4 "]},"arxiv":1,"status":"public","month":"01","publication":"ACM International Conference Proceeding Series","corr_author":"1","OA_type":"free access","language":[{"iso":"eng"}],"date_created":"2019-02-10T22:59:17Z","abstract":[{"lang":"eng","text":"Graph algorithms applied in many applications, including social networks, communication networks, VLSI design, graphics, and several others, require dynamic modifications - addition and removal of vertices and/or edges - in the graph. This paper presents a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. Most significant component of the presented algorithm is the reachability query in a concurrent graph. The reachability queries in our algorithm are obstruction-free and thus impose minimal additional synchronization cost over other operations. We prove that each of the data structure operations are linearizable. We extensively evaluate a sample C/C++ implementation of the algorithm through a number of micro-benchmarks. The experimental results show that the proposed algorithm scales well with the number of threads and on an average provides 5 to 7x performance improvement over a concurrent graph implementation using coarse-grained locking."}],"publisher":"ACM","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2019-01-04T00:00:00Z","publication_status":"published","year":"2019","article_processing_charge":"No","isi":1,"type":"conference","oa":1,"page":"168-177"},{"issue":"6","status":"public","month":"11","corr_author":"1","ddc":["000"],"publication":"Distributed Computing","publisher":"Springer","date_created":"2018-12-11T11:47:01Z","has_accepted_license":"1","abstract":[{"text":"We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary. We describe a new randomized consensus protocol with expected message complexity O(n2log2n) when fewer than n / 2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known Ω(n2) message lower bound. The protocol further ensures that no process sends more than O(nlog3n) messages in expectation, which is again within logarithmic factors of optimal. We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected O(nt+t2log2t) total messages. Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model.","lang":"eng"}],"intvolume":"        31","language":[{"iso":"eng"}],"file":[{"file_size":595707,"access_level":"open_access","content_type":"application/pdf","date_created":"2019-01-22T07:25:51Z","relation":"main_file","file_name":"2017_DistribComp_Alistarh.pdf","creator":"dernst","checksum":"69b46e537acdcac745237ddb853fcbb5","date_updated":"2020-07-14T12:46:38Z","file_id":"5867"}],"year":"2018","article_processing_charge":"Yes (via OA deal)","publication_status":"published","date_published":"2018-11-01T00:00:00Z","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","page":"489-501","oa":1,"type":"journal_article","isi":1,"oa_version":"Published Version","quality_controlled":"1","publist_id":"7281","_id":"536","volume":31,"scopus_import":"1","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"},"citation":{"short":"D.-A. Alistarh, J. Aspnes, V. King, J. Saia, Distributed Computing 31 (2018) 489–501.","chicago":"Alistarh, Dan-Adrian, James Aspnes, Valerie King, and Jared Saia. “Communication-Efficient Randomized Consensus.” <i>Distributed Computing</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s00446-017-0315-1\">https://doi.org/10.1007/s00446-017-0315-1</a>.","ama":"Alistarh D-A, Aspnes J, King V, Saia J. Communication-efficient randomized consensus. <i>Distributed Computing</i>. 2018;31(6):489-501. doi:<a href=\"https://doi.org/10.1007/s00446-017-0315-1\">10.1007/s00446-017-0315-1</a>","apa":"Alistarh, D.-A., Aspnes, J., King, V., &#38; Saia, J. (2018). Communication-efficient randomized consensus. <i>Distributed Computing</i>. Springer. <a href=\"https://doi.org/10.1007/s00446-017-0315-1\">https://doi.org/10.1007/s00446-017-0315-1</a>","ista":"Alistarh D-A, Aspnes J, King V, Saia J. 2018. Communication-efficient randomized consensus. Distributed Computing. 31(6), 489–501.","mla":"Alistarh, Dan-Adrian, et al. “Communication-Efficient Randomized Consensus.” <i>Distributed Computing</i>, vol. 31, no. 6, Springer, 2018, pp. 489–501, doi:<a href=\"https://doi.org/10.1007/s00446-017-0315-1\">10.1007/s00446-017-0315-1</a>.","ieee":"D.-A. Alistarh, J. Aspnes, V. King, and J. Saia, “Communication-efficient randomized consensus,” <i>Distributed Computing</i>, vol. 31, no. 6. Springer, pp. 489–501, 2018."},"doi":"10.1007/s00446-017-0315-1","project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"author":[{"first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"James","last_name":"Aspnes","full_name":"Aspnes, James"},{"full_name":"King, Valerie","first_name":"Valerie","last_name":"King"},{"full_name":"Saia, Jared","last_name":"Saia","first_name":"Jared"}],"date_updated":"2026-04-16T09:53:54Z","title":"Communication-efficient randomized consensus","publication_identifier":{"issn":["0178-2770"]},"file_date_updated":"2020-07-14T12:46:38Z","day":"01","external_id":{"isi":["000443832300005"]}},{"type":"conference","isi":1,"conference":{"start_date":"2018-07-23","name":"PODC: Principles of Distributed Computing","location":"Egham, United Kingdom","end_date":"2018-07-27"},"external_id":{"isi":["000458186900063"]},"publication_identifier":{"isbn":["9781450357951"]},"day":"27","page":"487-488","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2018-07-27T00:00:00Z","date_updated":"2025-06-03T11:56:33Z","title":"A brief tutorial on distributed and concurrent machine learning","year":"2018","article_processing_charge":"No","publication_status":"published","author":[{"full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X"}],"language":[{"iso":"eng"}],"doi":"10.1145/3212734.3212798","citation":{"mla":"Alistarh, Dan-Adrian. “A Brief Tutorial on Distributed and Concurrent Machine Learning.” <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, ACM, 2018, pp. 487–88, doi:<a href=\"https://doi.org/10.1145/3212734.3212798\">10.1145/3212734.3212798</a>.","ieee":"D.-A. Alistarh, “A brief tutorial on distributed and concurrent machine learning,” in <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, Egham, United Kingdom, 2018, pp. 487–488.","ista":"Alistarh D-A. 2018. A brief tutorial on distributed and concurrent machine learning. Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18. PODC: Principles of Distributed Computing, 487–488.","ama":"Alistarh D-A. A brief tutorial on distributed and concurrent machine learning. In: <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>. ACM; 2018:487-488. doi:<a href=\"https://doi.org/10.1145/3212734.3212798\">10.1145/3212734.3212798</a>","apa":"Alistarh, D.-A. (2018). A brief tutorial on distributed and concurrent machine learning. In <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i> (pp. 487–488). Egham, United Kingdom: ACM. <a href=\"https://doi.org/10.1145/3212734.3212798\">https://doi.org/10.1145/3212734.3212798</a>","chicago":"Alistarh, Dan-Adrian. “A Brief Tutorial on Distributed and Concurrent Machine Learning.” In <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, 487–88. ACM, 2018. <a href=\"https://doi.org/10.1145/3212734.3212798\">https://doi.org/10.1145/3212734.3212798</a>.","short":"D.-A. Alistarh, in:, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, ACM, 2018, pp. 487–488."},"date_created":"2019-02-13T09:48:55Z","scopus_import":"1","department":[{"_id":"DaAl"}],"abstract":[{"text":"The area of machine learning has made considerable progress over the past decade, enabled by the widespread availability of large datasets, as well as by improved algorithms and models. Given the large computational demands of machine learning workloads, parallelism, implemented either through single-node concurrency or through multi-node distribution, has been a third key ingredient to advances in machine learning.\r\nThe goal of this tutorial is to provide the audience with an overview of standard distribution techniques in machine learning, with an eye towards the intriguing trade-offs between synchronization and communication costs of distributed machine learning algorithms, on the one hand, and their convergence, on the other.The tutorial will focus on parallelization strategies for the fundamental stochastic gradient descent (SGD) algorithm, which is a key tool when training machine learning models, from classical instances such as linear regression, to state-of-the-art neural network architectures.\r\nThe tutorial will describe the guarantees provided by this algorithm in the sequential case, and then move on to cover both shared-memory and message-passing parallelization strategies, together with the guarantees they provide, and corresponding trade-offs. The presentation will conclude with a broad overview of ongoing research in distributed and concurrent machine learning. The tutorial will assume no prior knowledge beyond familiarity with basic concepts in algebra and analysis.\r\n","lang":"eng"}],"publisher":"ACM","_id":"5961","oa_version":"None","publication":"Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC '18","month":"07","status":"public","quality_controlled":"1"},{"publication":"Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC '18","status":"public","month":"07","language":[{"iso":"eng"}],"publisher":"ACM","date_created":"2019-02-13T09:58:58Z","abstract":[{"text":"Stochastic Gradient Descent (SGD) is a fundamental algorithm in machine learning, representing the optimization backbone for training several classic models, from regression to neural networks. Given the recent practical focus on distributed machine learning, significant work has been dedicated to the convergence properties of this algorithm under the inconsistent and noisy updates arising from execution in a distributed environment. However, surprisingly, the convergence properties of this classic algorithm in the standard shared-memory model are still not well-understood. In this work, we address this gap, and provide new convergence bounds for lock-free concurrent stochastic gradient descent, executing in the classic asynchronous shared memory model, against a strong adaptive adversary. Our results give improved upper and lower bounds on the \"price of asynchrony'' when executing the fundamental SGD algorithm in a concurrent setting. They show that this classic optimization tool can converge faster and with a wider range of parameters than previously known under asynchronous iterations. At the same time, we exhibit a fundamental trade-off between the maximum delay in the system and the rate at which SGD can converge, which governs the set of parameters under which this algorithm can still work efficiently.","lang":"eng"}],"date_published":"2018-07-23T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","article_processing_charge":"No","year":"2018","oa":1,"isi":1,"type":"conference","page":"169-178","oa_version":"Preprint","quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1803.08841","open_access":"1"}],"_id":"5962","doi":"10.1145/3212734.3212763","citation":{"chicago":"Alistarh, Dan-Adrian, Christopher De Sa, and Nikola H Konstantinov. “The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory.” In <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, 169–78. ACM, 2018. <a href=\"https://doi.org/10.1145/3212734.3212763\">https://doi.org/10.1145/3212734.3212763</a>.","short":"D.-A. Alistarh, C. De Sa, N.H. Konstantinov, in:, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, ACM, 2018, pp. 169–178.","ieee":"D.-A. Alistarh, C. De Sa, and N. H. Konstantinov, “The convergence of stochastic gradient descent in asynchronous shared memory,” in <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, Egham, United Kingdom, 2018, pp. 169–178.","mla":"Alistarh, Dan-Adrian, et al. “The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory.” <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, ACM, 2018, pp. 169–78, doi:<a href=\"https://doi.org/10.1145/3212734.3212763\">10.1145/3212734.3212763</a>.","ista":"Alistarh D-A, De Sa C, Konstantinov NH. 2018. The convergence of stochastic gradient descent in asynchronous shared memory. Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18. PODC: Principles of Distributed Computing, 169–178.","ama":"Alistarh D-A, De Sa C, Konstantinov NH. The convergence of stochastic gradient descent in asynchronous shared memory. In: <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>. ACM; 2018:169-178. doi:<a href=\"https://doi.org/10.1145/3212734.3212763\">10.1145/3212734.3212763</a>","apa":"Alistarh, D.-A., De Sa, C., &#38; Konstantinov, N. H. (2018). The convergence of stochastic gradient descent in asynchronous shared memory. In <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i> (pp. 169–178). Egham, United Kingdom: ACM. <a href=\"https://doi.org/10.1145/3212734.3212763\">https://doi.org/10.1145/3212734.3212763</a>"},"scopus_import":"1","department":[{"_id":"DaAl"}],"title":"The convergence of stochastic gradient descent in asynchronous shared memory","date_updated":"2025-06-03T11:56:41Z","author":[{"last_name":"Alistarh","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Christopher","last_name":"De Sa","full_name":"De Sa, Christopher"},{"last_name":"Konstantinov","first_name":"Nikola H","id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87","full_name":"Konstantinov, Nikola H"}],"external_id":{"arxiv":["1803.08841"],"isi":["000458186900022"]},"conference":{"end_date":"2018-07-27","start_date":"2018-07-23","name":"PODC: Principles of Distributed Computing","location":"Egham, United Kingdom"},"arxiv":1,"day":"23","publication_identifier":{"isbn":["9781450357951"]}},{"publication":"Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC '18","month":"07","status":"public","language":[{"iso":"eng"}],"publisher":"ACM","date_created":"2019-02-13T10:03:25Z","abstract":[{"text":"There has been significant progress in understanding the parallelism inherent to iterative sequential algorithms: for many classic algorithms, the depth of the dependence structure is now well understood, and scheduling techniques have been developed to exploit this shallow dependence structure for efficient parallel implementations. A related, applied research strand has studied methods by which certain iterative task-based algorithms can be efficiently parallelized via relaxed concurrent priority schedulers. These allow for high concurrency when inserting and removing tasks, at the cost of executing superfluous work due to the relaxed semantics of the scheduler. In this work, we take a step towards unifying these two research directions, by showing that there exists a family of relaxed priority schedulers that can efficiently and deterministically execute classic iterative algorithms such as greedy maximal independent set (MIS) and matching. Our primary result shows that, given a randomized scheduler with an expected relaxation factor of k in terms of the maximum allowed priority inversions on a task, and any graph on n vertices, the scheduler is able to execute greedy MIS with only an additive factor of \\poly(k) expected additional iterations compared to an exact (but not scalable) scheduler. This counter-intuitive result demonstrates that the overhead of relaxation when computing MIS is not dependent on the input size or structure of the input graph. Experimental results show that this overhead can be clearly offset by the gain in performance due to the highly scalable scheduler. In sum, we present an efficient method to deterministically parallelize iterative sequential algorithms, with provable runtime guarantees in terms of the number of executed tasks to completion.","lang":"eng"}],"date_published":"2018-07-23T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2018","article_processing_charge":"No","publication_status":"published","oa":1,"type":"conference","isi":1,"page":"377-386","main_file_link":[{"url":"https://arxiv.org/abs/1808.04155","open_access":"1"}],"quality_controlled":"1","oa_version":"Preprint","_id":"5963","citation":{"chicago":"Alistarh, Dan-Adrian, Trevor A Brown, Justin Kopinsky, and Giorgi Nadiradze. “Relaxed Schedulers Can Efficiently Parallelize Iterative Algorithms.” In <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, 377–86. ACM, 2018. <a href=\"https://doi.org/10.1145/3212734.3212756\">https://doi.org/10.1145/3212734.3212756</a>.","short":"D.-A. Alistarh, T.A. Brown, J. Kopinsky, G. Nadiradze, in:, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, ACM, 2018, pp. 377–386.","ieee":"D.-A. Alistarh, T. A. Brown, J. Kopinsky, and G. Nadiradze, “Relaxed schedulers can efficiently parallelize iterative algorithms,” in <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, Egham, United Kingdom, 2018, pp. 377–386.","mla":"Alistarh, Dan-Adrian, et al. “Relaxed Schedulers Can Efficiently Parallelize Iterative Algorithms.” <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, ACM, 2018, pp. 377–86, doi:<a href=\"https://doi.org/10.1145/3212734.3212756\">10.1145/3212734.3212756</a>.","apa":"Alistarh, D.-A., Brown, T. A., Kopinsky, J., &#38; Nadiradze, G. (2018). Relaxed schedulers can efficiently parallelize iterative algorithms. In <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i> (pp. 377–386). Egham, United Kingdom: ACM. <a href=\"https://doi.org/10.1145/3212734.3212756\">https://doi.org/10.1145/3212734.3212756</a>","ama":"Alistarh D-A, Brown TA, Kopinsky J, Nadiradze G. Relaxed schedulers can efficiently parallelize iterative algorithms. In: <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>. ACM; 2018:377-386. doi:<a href=\"https://doi.org/10.1145/3212734.3212756\">10.1145/3212734.3212756</a>","ista":"Alistarh D-A, Brown TA, Kopinsky J, Nadiradze G. 2018. Relaxed schedulers can efficiently parallelize iterative algorithms. Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18. PODC: Principles of Distributed Computing, 377–386."},"doi":"10.1145/3212734.3212756","department":[{"_id":"DaAl"}],"scopus_import":"1","date_updated":"2025-06-03T11:56:49Z","title":"Relaxed schedulers can efficiently parallelize iterative algorithms","author":[{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"first_name":"Trevor A","last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","full_name":"Brown, Trevor A"},{"full_name":"Kopinsky, Justin","last_name":"Kopinsky","first_name":"Justin"},{"full_name":"Nadiradze, Giorgi","first_name":"Giorgi","last_name":"Nadiradze"}],"external_id":{"arxiv":["1808.04155"],"isi":["000458186900048"]},"conference":{"location":"Egham, United Kingdom","name":"PODC: Principles of Distributed Computing","start_date":"2018-07-23","end_date":"2018-07-27"},"arxiv":1,"publication_identifier":{"isbn":["9781450357951"]},"day":"23"},{"publication_status":"published","article_processing_charge":"No","year":"2018","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2018-07-23T00:00:00Z","page":"411-413","type":"conference","isi":1,"oa":1,"status":"public","publication":"Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC '18","month":"07","abstract":[{"lang":"eng","text":"A standard design pattern found in many concurrent data structures, such as hash tables or ordered containers, is an alternation of parallelizable sections that incur no data conflicts and critical sections that must run sequentially and are protected with locks. A lock can be viewed as a queue that arbitrates the order in which the critical sections are executed, and a natural question is whether we can use stochastic analysis to predict the resulting throughput. As a preliminary evidence to the affirmative, we describe a simple model that can be used to predict the throughput of coarse-grained lock-based algorithms. We show that our model works well for CLH lock, and we expect it to work for other popular lock designs such as TTAS, MCS, etc."}],"date_created":"2019-02-13T10:08:19Z","publisher":"ACM","language":[{"iso":"eng"}],"author":[{"last_name":"Aksenov","first_name":"Vitaly","full_name":"Aksenov, Vitaly"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"},{"full_name":"Kuznetsov, Petr","last_name":"Kuznetsov","first_name":"Petr"}],"title":"Brief Announcement: Performance prediction for coarse-grained locking","date_updated":"2025-06-03T11:58:00Z","day":"23","publication_identifier":{"isbn":["9781450357951"]},"conference":{"location":"Egham, United Kingdom","name":"PODC: Principles of Distributed Computing","start_date":"2018-07-23","end_date":"2018-07-27"},"external_id":{"isi":["000458186900052"]},"_id":"5964","oa_version":"Submitted Version","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://hal-univ-lyon3.archives-ouvertes.fr/INRIA/hal-01887733v1"}],"scopus_import":"1","department":[{"_id":"DaAl"}],"citation":{"ista":"Aksenov V, Alistarh D-A, Kuznetsov P. 2018. Brief Announcement: Performance prediction for coarse-grained locking. Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18. PODC: Principles of Distributed Computing, 411–413.","ama":"Aksenov V, Alistarh D-A, Kuznetsov P. Brief Announcement: Performance prediction for coarse-grained locking. In: <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>. ACM; 2018:411-413. doi:<a href=\"https://doi.org/10.1145/3212734.3212785\">10.1145/3212734.3212785</a>","apa":"Aksenov, V., Alistarh, D.-A., &#38; Kuznetsov, P. (2018). Brief Announcement: Performance prediction for coarse-grained locking. In <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i> (pp. 411–413). Egham, United Kingdom: ACM. <a href=\"https://doi.org/10.1145/3212734.3212785\">https://doi.org/10.1145/3212734.3212785</a>","mla":"Aksenov, Vitaly, et al. “Brief Announcement: Performance Prediction for Coarse-Grained Locking.” <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, ACM, 2018, pp. 411–13, doi:<a href=\"https://doi.org/10.1145/3212734.3212785\">10.1145/3212734.3212785</a>.","ieee":"V. Aksenov, D.-A. Alistarh, and P. Kuznetsov, “Brief Announcement: Performance prediction for coarse-grained locking,” in <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, Egham, United Kingdom, 2018, pp. 411–413.","short":"V. Aksenov, D.-A. Alistarh, P. Kuznetsov, in:, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, ACM, 2018, pp. 411–413.","chicago":"Aksenov, Vitaly, Dan-Adrian Alistarh, and Petr Kuznetsov. “Brief Announcement: Performance Prediction for Coarse-Grained Locking.” In <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, 411–13. ACM, 2018. <a href=\"https://doi.org/10.1145/3212734.3212785\">https://doi.org/10.1145/3212734.3212785</a>."},"doi":"10.1145/3212734.3212785"},{"author":[{"first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Brown","first_name":"Trevor A","full_name":"Brown, Trevor A","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kopinsky","first_name":"Justin","full_name":"Kopinsky, Justin"},{"first_name":"Jerry Z.","last_name":"Li","full_name":"Li, Jerry Z."},{"full_name":"Nadiradze, Giorgi","first_name":"Giorgi","last_name":"Nadiradze"}],"title":"Distributionally linearizable data structures","date_updated":"2026-04-08T07:00:45Z","day":"16","related_material":{"record":[{"relation":"dissertation_contains","id":"10429","status":"public"}]},"publication_identifier":{"isbn":["9781450357999"]},"arxiv":1,"conference":{"end_date":"2018-07-18","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures","location":"Vienna, Austria","start_date":"2018-07-16"},"external_id":{"arxiv":["1804.01018"],"isi":["000545269600016"]},"_id":"5965","quality_controlled":"1","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1804.01018"}],"department":[{"_id":"DaAl"}],"scopus_import":"1","doi":"10.1145/3210377.3210411","citation":{"ieee":"D.-A. Alistarh, T. A. Brown, J. Kopinsky, J. Z. Li, and G. Nadiradze, “Distributionally linearizable data structures,” in <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, Vienna, Austria, 2018, pp. 133–142.","mla":"Alistarh, Dan-Adrian, et al. “Distributionally Linearizable Data Structures.” <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, ACM, 2018, pp. 133–42, doi:<a href=\"https://doi.org/10.1145/3210377.3210411\">10.1145/3210377.3210411</a>.","ista":"Alistarh D-A, Brown TA, Kopinsky J, Li JZ, Nadiradze G. 2018. Distributionally linearizable data structures. Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18. SPAA: Symposium on Parallelism in Algorithms and Architectures, 133–142.","ama":"Alistarh D-A, Brown TA, Kopinsky J, Li JZ, Nadiradze G. Distributionally linearizable data structures. In: <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>. ACM; 2018:133-142. doi:<a href=\"https://doi.org/10.1145/3210377.3210411\">10.1145/3210377.3210411</a>","apa":"Alistarh, D.-A., Brown, T. A., Kopinsky, J., Li, J. Z., &#38; Nadiradze, G. (2018). Distributionally linearizable data structures. In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i> (pp. 133–142). Vienna, Austria: ACM. <a href=\"https://doi.org/10.1145/3210377.3210411\">https://doi.org/10.1145/3210377.3210411</a>","chicago":"Alistarh, Dan-Adrian, Trevor A Brown, Justin Kopinsky, Jerry Z. Li, and Giorgi Nadiradze. “Distributionally Linearizable Data Structures.” In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, 133–42. ACM, 2018. <a href=\"https://doi.org/10.1145/3210377.3210411\">https://doi.org/10.1145/3210377.3210411</a>.","short":"D.-A. Alistarh, T.A. Brown, J. Kopinsky, J.Z. Li, G. Nadiradze, in:, Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18, ACM, 2018, pp. 133–142."},"publication_status":"published","article_processing_charge":"No","year":"2018","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2018-07-16T00:00:00Z","page":"133-142","isi":1,"type":"conference","oa":1,"month":"07","publication":"Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA '18","status":"public","date_created":"2019-02-13T10:17:19Z","abstract":[{"lang":"eng","text":"Relaxed concurrent data structures have become increasingly popular, due to their scalability in graph processing and machine learning applications (\\citeNguyen13, gonzalez2012powergraph ). Despite considerable interest, there exist families of natural, high performing randomized relaxed concurrent data structures, such as the popular MultiQueue~\\citeMQ pattern for implementing relaxed priority queue data structures, for which no guarantees are known in the concurrent setting~\\citeAKLN17. Our main contribution is in showing for the first time that, under a set of analytic assumptions, a family of relaxed concurrent data structures, including variants of MultiQueues, but also a new approximate counting algorithm we call the MultiCounter, provides strong probabilistic guarantees on the degree of relaxation with respect to the sequential specification, in arbitrary concurrent executions. We formalize these guarantees via a new correctness condition called distributional linearizability, tailored to concurrent implementations with randomized relaxations. Our result is based on a new analysis of an asynchronous variant of the classic power-of-two-choices load balancing algorithm, in which placement choices can be based on inconsistent, outdated information (this result may be of independent interest). We validate our results empirically, showing that the MultiCounter algorithm can implement scalable relaxed timestamps."}],"publisher":"ACM","language":[{"iso":"eng"}]},{"date_created":"2019-02-13T10:26:07Z","abstract":[{"text":"The transactional conflict problem arises in transactional systems whenever two or more concurrent transactions clash on a data item. While the standard solution to such conflicts is to immediately abort one of the transactions, some practical systems consider the alternative of delaying conflict resolution for a short interval, which may allow one of the transactions to commit. The challenge in the transactional conflict problem is to choose the optimal length of this delay interval so as to minimize the overall running time penalty for the conflicting transactions. In this paper, we propose a family of optimal online algorithms for the transactional conflict problem. Specifically, we consider variants of this problem which arise in different implementations of transactional systems, namely \"requestor wins'' and \"requestor aborts'' implementations: in the former, the recipient of a coherence request is aborted, whereas in the latter, it is the requestor which has to abort. Both strategies are implemented by real systems. We show that the requestor aborts case can be reduced to a classic instance of the ski rental problem, while the requestor wins case leads to a new version of this classical problem, for which we derive optimal deterministic and randomized algorithms. Moreover, we prove that, under a simplified adversarial model, our algorithms are constant-competitive with the offline optimum in terms of throughput. We validate our algorithmic results empirically through a hardware simulation of hardware transactional memory (HTM), showing that our algorithms can lead to non-trivial performance improvements for classic concurrent data structures.","lang":"eng"}],"publisher":"ACM","language":[{"iso":"eng"}],"month":"07","publication":"Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA '18","status":"public","page":"383-392","isi":1,"type":"conference","oa":1,"article_processing_charge":"No","year":"2018","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2018-07-16T00:00:00Z","department":[{"_id":"DaAl"}],"scopus_import":"1","citation":{"chicago":"Alistarh, Dan-Adrian, Syed Kamran Haider, Raphael Kübler, and Giorgi Nadiradze. “The Transactional Conflict Problem.” In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, 383–92. ACM, 2018. <a href=\"https://doi.org/10.1145/3210377.3210406\">https://doi.org/10.1145/3210377.3210406</a>.","short":"D.-A. Alistarh, S.K. Haider, R. Kübler, G. Nadiradze, in:, Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18, ACM, 2018, pp. 383–392.","ieee":"D.-A. Alistarh, S. K. Haider, R. Kübler, and G. Nadiradze, “The transactional conflict problem,” in <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, Vienna, Austria, 2018, pp. 383–392.","mla":"Alistarh, Dan-Adrian, et al. “The Transactional Conflict Problem.” <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, ACM, 2018, pp. 383–92, doi:<a href=\"https://doi.org/10.1145/3210377.3210406\">10.1145/3210377.3210406</a>.","ama":"Alistarh D-A, Haider SK, Kübler R, Nadiradze G. The transactional conflict problem. In: <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>. ACM; 2018:383-392. doi:<a href=\"https://doi.org/10.1145/3210377.3210406\">10.1145/3210377.3210406</a>","ista":"Alistarh D-A, Haider SK, Kübler R, Nadiradze G. 2018. The transactional conflict problem. Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18. SPAA: Symposium on Parallelism in Algorithms and Architectures, 383–392.","apa":"Alistarh, D.-A., Haider, S. K., Kübler, R., &#38; Nadiradze, G. (2018). The transactional conflict problem. In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i> (pp. 383–392). Vienna, Austria: ACM. <a href=\"https://doi.org/10.1145/3210377.3210406\">https://doi.org/10.1145/3210377.3210406</a>"},"doi":"10.1145/3210377.3210406","_id":"5966","main_file_link":[{"url":"https://arxiv.org/abs/1804.00947","open_access":"1"}],"oa_version":"Preprint","quality_controlled":"1","publication_identifier":{"isbn":["9781450357999"]},"day":"16","arxiv":1,"conference":{"end_date":"2018-07-18","location":"Vienna, Austria","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures","start_date":"2018-07-16"},"external_id":{"isi":["000545269600046"],"arxiv":["1804.00947"]},"author":[{"last_name":"Alistarh","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Syed Kamran","last_name":"Haider","full_name":"Haider, Syed Kamran"},{"last_name":"Kübler","first_name":"Raphael","full_name":"Kübler, Raphael"},{"full_name":"Nadiradze, Giorgi","first_name":"Giorgi","last_name":"Nadiradze"}],"date_updated":"2025-06-03T11:58:22Z","title":"The transactional conflict problem"},{"scopus_import":1,"abstract":[{"text":"The concurrent memory reclamation problem is that of devising a way for a deallocating thread to verify that no other concurrent threads hold references to a memory block being deallocated. To date, in the absence of automatic garbage collection, there is no satisfactory solution to this problem; existing tracking methods like hazard pointers, reference counters, or epoch-based techniques like RCU are either prohibitively expensive or require significant programming expertise to the extent that implementing them efficiently can be worthy of a publication. None of the existing techniques are automatic or even semi-automated.\r\nIn this article, we take a new approach to concurrent memory reclamation. Instead of manually tracking access to memory locations as done in techniques like hazard pointers, or restricting shared accesses to specific epoch boundaries as in RCU, our algorithm, called ThreadScan, leverages operating system signaling to automatically detect which memory locations are being accessed by concurrent threads.\r\nInitial empirical evidence shows that ThreadScan scales surprisingly well and requires negligible programming effort beyond the standard use of Malloc and Free.","lang":"eng"}],"date_created":"2019-02-14T13:24:11Z","department":[{"_id":"DaAl"}],"publisher":"Association for Computing Machinery","volume":4,"language":[{"iso":"eng"}],"intvolume":"         4","citation":{"ista":"Alistarh D-A, Leiserson W, Matveev A, Shavit N. 2018. ThreadScan: Automatic and scalable memory reclamation. ACM Transactions on Parallel Computing. 4(4), 18.","ama":"Alistarh D-A, Leiserson W, Matveev A, Shavit N. ThreadScan: Automatic and scalable memory reclamation. <i>ACM Transactions on Parallel Computing</i>. 2018;4(4). doi:<a href=\"https://doi.org/10.1145/3201897\">10.1145/3201897</a>","apa":"Alistarh, D.-A., Leiserson, W., Matveev, A., &#38; Shavit, N. (2018). ThreadScan: Automatic and scalable memory reclamation. <i>ACM Transactions on Parallel Computing</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3201897\">https://doi.org/10.1145/3201897</a>","ieee":"D.-A. Alistarh, W. Leiserson, A. Matveev, and N. Shavit, “ThreadScan: Automatic and scalable memory reclamation,” <i>ACM Transactions on Parallel Computing</i>, vol. 4, no. 4. Association for Computing Machinery, 2018.","mla":"Alistarh, Dan-Adrian, et al. “ThreadScan: Automatic and Scalable Memory Reclamation.” <i>ACM Transactions on Parallel Computing</i>, vol. 4, no. 4, 18, Association for Computing Machinery, 2018, doi:<a href=\"https://doi.org/10.1145/3201897\">10.1145/3201897</a>.","short":"D.-A. Alistarh, W. Leiserson, A. Matveev, N. Shavit, ACM Transactions on Parallel Computing 4 (2018).","chicago":"Alistarh, Dan-Adrian, William Leiserson, Alexander Matveev, and Nir Shavit. “ThreadScan: Automatic and Scalable Memory Reclamation.” <i>ACM Transactions on Parallel Computing</i>. Association for Computing Machinery, 2018. <a href=\"https://doi.org/10.1145/3201897\">https://doi.org/10.1145/3201897</a>."},"doi":"10.1145/3201897","issue":"4","_id":"6001","quality_controlled":"1","status":"public","publication":"ACM Transactions on Parallel Computing","month":"09","oa_version":"None","day":"01","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"779"}]},"publication_identifier":{"issn":["2329-4949"]},"type":"journal_article","publication_status":"published","year":"2018","author":[{"orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"full_name":"Leiserson, William","last_name":"Leiserson","first_name":"William"},{"first_name":"Alexander","last_name":"Matveev","full_name":"Matveev, Alexander"},{"last_name":"Shavit","first_name":"Nir","full_name":"Shavit, Nir"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","title":"ThreadScan: Automatic and scalable memory reclamation","date_published":"2018-09-01T00:00:00Z","article_number":"18","date_updated":"2023-02-23T13:17:54Z"},{"_id":"6031","status":"public","quality_controlled":"1","oa_version":"None","publication":"2018 IEEE International Workshop on Signal Processing Systems","month":"12","language":[{"iso":"eng"}],"doi":"10.1109/SiPS.2018.8598402","citation":{"apa":"Stojanov, A., Smith, T. M., Alistarh, D.-A., &#38; Puschel, M. (2018). Fast quantized arithmetic on x86: Trading compute for data movement. In <i>2018 IEEE International Workshop on Signal Processing Systems</i> (Vol. 2018–October). Cape Town, South Africa: IEEE. <a href=\"https://doi.org/10.1109/SiPS.2018.8598402\">https://doi.org/10.1109/SiPS.2018.8598402</a>","ista":"Stojanov A, Smith TM, Alistarh D-A, Puschel M. 2018. Fast quantized arithmetic on x86: Trading compute for data movement. 2018 IEEE International Workshop on Signal Processing Systems. SiPS: Workshop on Signal Processing Systems vol. 2018–October, 8598402.","ama":"Stojanov A, Smith TM, Alistarh D-A, Puschel M. Fast quantized arithmetic on x86: Trading compute for data movement. In: <i>2018 IEEE International Workshop on Signal Processing Systems</i>. Vol 2018-October. IEEE; 2018. doi:<a href=\"https://doi.org/10.1109/SiPS.2018.8598402\">10.1109/SiPS.2018.8598402</a>","mla":"Stojanov, Alen, et al. “Fast Quantized Arithmetic on X86: Trading Compute for Data Movement.” <i>2018 IEEE International Workshop on Signal Processing Systems</i>, vol. 2018–October, 8598402, IEEE, 2018, doi:<a href=\"https://doi.org/10.1109/SiPS.2018.8598402\">10.1109/SiPS.2018.8598402</a>.","ieee":"A. Stojanov, T. M. Smith, D.-A. Alistarh, and M. Puschel, “Fast quantized arithmetic on x86: Trading compute for data movement,” in <i>2018 IEEE International Workshop on Signal Processing Systems</i>, Cape Town, South Africa, 2018, vol. 2018–October.","short":"A. Stojanov, T.M. Smith, D.-A. Alistarh, M. Puschel, in:, 2018 IEEE International Workshop on Signal Processing Systems, IEEE, 2018.","chicago":"Stojanov, Alen, Tyler Michael Smith, Dan-Adrian Alistarh, and Markus Puschel. “Fast Quantized Arithmetic on X86: Trading Compute for Data Movement.” In <i>2018 IEEE International Workshop on Signal Processing Systems</i>, Vol. 2018–October. IEEE, 2018. <a href=\"https://doi.org/10.1109/SiPS.2018.8598402\">https://doi.org/10.1109/SiPS.2018.8598402</a>."},"date_created":"2019-02-17T22:59:25Z","abstract":[{"text":"We introduce Clover, a new library for efficient computation using low-precision data, providing mathematical routines required by fundamental methods in optimization and sparse recovery. Our library faithfully implements variants of stochastic quantization that guarantee convergence at low precision, and supports data formats from 4-bit quantized to 32-bit IEEE-754 on current Intel processors. In particular, we show that 4-bit can be implemented efficiently using Intel AVX despite the lack of native support for this data format. Experimental results with dot product, matrix-vector multiplication (MVM), gradient descent (GD), and iterative hard thresholding (IHT) demonstrate that the attainable speedups are in many cases close to linear with respect to the reduction of precision due to reduced data movement. Finally, for GD and IHT, we show examples of absolute speedup achieved by 4-bit versus 32-bit, by iterating until a given target error is achieved.","lang":"eng"}],"scopus_import":"1","department":[{"_id":"DaAl"}],"publisher":"IEEE","volume":"2018-October","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"Fast quantized arithmetic on x86: Trading compute for data movement","article_number":"8598402","date_updated":"2023-09-19T14:41:51Z","date_published":"2018-12-31T00:00:00Z","publication_status":"published","year":"2018","article_processing_charge":"No","author":[{"full_name":"Stojanov, Alen","first_name":"Alen","last_name":"Stojanov"},{"full_name":"Smith, Tyler Michael","first_name":"Tyler Michael","last_name":"Smith"},{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"first_name":"Markus","last_name":"Puschel","full_name":"Puschel, Markus"}],"conference":{"end_date":"2018-10-24","start_date":"2018-10-21","location":"Cape Town, South Africa","name":"SiPS: Workshop on Signal Processing Systems"},"type":"conference","isi":1,"external_id":{"isi":["000465106800060"]},"day":"31"},{"external_id":{"isi":["000475627800005"]},"day":"12","file_date_updated":"2020-07-14T12:48:01Z","title":"Near-optimal self-stabilising counting and firing squads","date_updated":"2025-04-15T06:53:15Z","author":[{"full_name":"Lenzen, Christoph","first_name":"Christoph","last_name":"Lenzen"},{"orcid":"0000-0002-6432-6646","last_name":"Rybicki","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","full_name":"Rybicki, Joel"}],"project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"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"},"citation":{"short":"C. Lenzen, J. Rybicki, Distributed Computing (2018).","chicago":"Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting and Firing Squads.” <i>Distributed Computing</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s00446-018-0342-6\">https://doi.org/10.1007/s00446-018-0342-6</a>.","ama":"Lenzen C, Rybicki J. Near-optimal self-stabilising counting and firing squads. <i>Distributed Computing</i>. 2018. doi:<a href=\"https://doi.org/10.1007/s00446-018-0342-6\">10.1007/s00446-018-0342-6</a>","ista":"Lenzen C, Rybicki J. 2018. Near-optimal self-stabilising counting and firing squads. Distributed Computing.","apa":"Lenzen, C., &#38; Rybicki, J. (2018). Near-optimal self-stabilising counting and firing squads. <i>Distributed Computing</i>. Springer. <a href=\"https://doi.org/10.1007/s00446-018-0342-6\">https://doi.org/10.1007/s00446-018-0342-6</a>","ieee":"C. Lenzen and J. Rybicki, “Near-optimal self-stabilising counting and firing squads,” <i>Distributed Computing</i>. Springer, 2018.","mla":"Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting and Firing Squads.” <i>Distributed Computing</i>, Springer, 2018, doi:<a href=\"https://doi.org/10.1007/s00446-018-0342-6\">10.1007/s00446-018-0342-6</a>."},"doi":"10.1007/s00446-018-0342-6","department":[{"_id":"DaAl"}],"scopus_import":"1","_id":"76","publist_id":"7978","quality_controlled":"1","oa_version":"Published Version","type":"journal_article","isi":1,"oa":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_published":"2018-09-12T00:00:00Z","publication_status":"published","article_processing_charge":"Yes (via OA deal)","year":"2018","file":[{"file_size":799337,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2018-12-17T14:21:22Z","checksum":"872db70bba9b401500abe3c6ae2f1a61","creator":"dernst","file_name":"2018_DistributedComputing_Lenzen.pdf","date_updated":"2020-07-14T12:48:01Z","file_id":"5711"}],"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Consider a fully-connected synchronous distributed system consisting of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous C-counting problem, all nodes need to eventually agree on a counter that is increased by one modulo C in each round for given C&gt;1. In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience f&lt;n/3, asymptotically optimal stabilisation and response time O(f), and message size O(log f). As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions."}],"date_created":"2018-12-11T11:44:30Z","has_accepted_license":"1","publisher":"Springer","publication":"Distributed Computing","ddc":["000"],"corr_author":"1","month":"09","status":"public"},{"publication":"6th International Conference on Learning Representations","status":"public","month":"05","ddc":["000"],"language":[{"iso":"eng"}],"abstract":[{"text":"Deep neural networks (DNNs) continue to make significant advances, solving tasks from image classification to translation or reinforcement learning. One aspect of the field receiving considerable attention is efficiently executing deep models in resource-constrained environments, such as mobile or embedded devices. This paper focuses on this problem, and proposes two new compression methods, which jointly leverage weight quantization and distillation of larger teacher networks into smaller student networks. The first method we propose is called quantized distillation and leverages distillation during the training process, by incorporating distillation loss, expressed with respect to the teacher, into the training of a student network whose weights are quantized to a limited set of levels. The second method,  differentiable quantization, optimizes the location of quantization points through stochastic gradient descent, to better fit the behavior of the teacher model.  We validate both methods through experiments on convolutional and recurrent architectures. We show that quantized shallow students can reach similar accuracy levels to full-precision teacher models, while providing order of magnitude compression, and inference speedup that is linear in the depth reduction. In sum, our results enable DNNs for resource-constrained environments to leverage architecture and accuracy advances developed on more powerful devices.","lang":"eng"}],"date_created":"2020-05-10T22:00:51Z","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2018-05-01T00:00:00Z","publication_status":"published","article_processing_charge":"No","year":"2018","file":[{"file_size":308339,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2020-05-26T13:02:00Z","checksum":"a4336c167978e81891970e4e4517a8c3","file_name":"2018_ICLR_Polino.pdf","creator":"dernst","date_updated":"2020-07-14T12:48:03Z","file_id":"7894"}],"type":"conference","oa":1,"_id":"7812","oa_version":"Published Version","quality_controlled":"1","citation":{"ista":"Polino A, Pascanu R, Alistarh D-A. 2018. Model compression via distillation and quantization. 6th International Conference on Learning Representations. ICLR: International Conference on Learning Representations.","apa":"Polino, A., Pascanu, R., &#38; Alistarh, D.-A. (2018). Model compression via distillation and quantization. In <i>6th International Conference on Learning Representations</i>. Vancouver, Canada.","ama":"Polino A, Pascanu R, Alistarh D-A. Model compression via distillation and quantization. In: <i>6th International Conference on Learning Representations</i>. ; 2018.","mla":"Polino, Antonio, et al. “Model Compression via Distillation and Quantization.” <i>6th International Conference on Learning Representations</i>, 2018.","ieee":"A. Polino, R. Pascanu, and D.-A. Alistarh, “Model compression via distillation and quantization,” in <i>6th International Conference on Learning Representations</i>, Vancouver, Canada, 2018.","short":"A. Polino, R. Pascanu, D.-A. Alistarh, in:, 6th International Conference on Learning Representations, 2018.","chicago":"Polino, Antonio, Razvan Pascanu, and Dan-Adrian Alistarh. “Model Compression via Distillation and Quantization.” In <i>6th International Conference on Learning Representations</i>, 2018."},"scopus_import":"1","department":[{"_id":"DaAl"}],"title":"Model compression via distillation and quantization","date_updated":"2025-06-30T10:04:44Z","author":[{"first_name":"Antonio","last_name":"Polino","full_name":"Polino, Antonio"},{"last_name":"Pascanu","first_name":"Razvan","full_name":"Pascanu, Razvan"},{"first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"conference":{"start_date":"2018-04-30","location":"Vancouver, Canada","name":"ICLR: International Conference on Learning Representations","end_date":"2018-05-03"},"external_id":{"arxiv":["1802.05668"]},"day":"01","file_date_updated":"2020-07-14T12:48:03Z","acknowledgement":"We would like to thank Ce Zhang (ETH Zurich), Hantian Zhang (ETH Zurich) and Martin Jaggi ´\r\n(EPFL) for their support with experiments and valuable feedback.\r\n","arxiv":1},{"quality_controlled":"1","oa_version":"Preprint","_id":"85","publist_id":"7969","doi":"10.1007/978-3-319-96983-1_33","citation":{"ista":"Gilad E, Brown TA, Oskin M, Etsion Y. 2018. Snapshot based synchronization: A fast replacement for Hand-over-Hand locking. Euro-Par: European Conference on Parallel Processing, LNCS, vol. 11014, 465–479.","apa":"Gilad, E., Brown, T. A., Oskin, M., &#38; Etsion, Y. (2018). Snapshot based synchronization: A fast replacement for Hand-over-Hand locking (Vol. 11014, pp. 465–479). Presented at the Euro-Par: European Conference on Parallel Processing, Turin, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">https://doi.org/10.1007/978-3-319-96983-1_33</a>","ama":"Gilad E, Brown TA, Oskin M, Etsion Y. Snapshot based synchronization: A fast replacement for Hand-over-Hand locking. In: Vol 11014. Springer; 2018:465-479. doi:<a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">10.1007/978-3-319-96983-1_33</a>","mla":"Gilad, Eran, et al. <i>Snapshot Based Synchronization: A Fast Replacement for Hand-over-Hand Locking</i>. Vol. 11014, Springer, 2018, pp. 465–79, doi:<a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">10.1007/978-3-319-96983-1_33</a>.","ieee":"E. Gilad, T. A. Brown, M. Oskin, and Y. Etsion, “Snapshot based synchronization: A fast replacement for Hand-over-Hand locking,” presented at the Euro-Par: European Conference on Parallel Processing, Turin, Italy, 2018, vol. 11014, pp. 465–479.","short":"E. Gilad, T.A. Brown, M. Oskin, Y. Etsion, in:, Springer, 2018, pp. 465–479.","chicago":"Gilad, Eran, Trevor A Brown, Mark Oskin, and Yoav Etsion. “Snapshot Based Synchronization: A Fast Replacement for Hand-over-Hand Locking,” 11014:465–79. Springer, 2018. <a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">https://doi.org/10.1007/978-3-319-96983-1_33</a>."},"project":[{"_id":"26450934-B435-11E9-9278-68D0E5697425","name":"NSERC Postdoctoral fellowship"}],"volume":11014,"scopus_import":"1","department":[{"_id":"DaAl"}],"title":"Snapshot based synchronization: A fast replacement for Hand-over-Hand locking","date_updated":"2026-04-16T09:53:41Z","author":[{"full_name":"Gilad, Eran","first_name":"Eran","last_name":"Gilad"},{"full_name":"Brown, Trevor A","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","first_name":"Trevor A","last_name":"Brown"},{"last_name":"Oskin","first_name":"Mark","full_name":"Oskin, Mark"},{"full_name":"Etsion, Yoav","first_name":"Yoav","last_name":"Etsion"}],"external_id":{"isi":["000851042300031"]},"conference":{"end_date":"2018-08-31","start_date":"2018-08-27","name":"Euro-Par: European Conference on Parallel Processing","location":"Turin, Italy"},"day":"01","file_date_updated":"2020-07-14T12:48:14Z","acknowledgement":"Trevor Brown was supported in part by the ISF (grants 2005/17 & 1749/14) and by a NSERC post-doctoral fellowship.","publication_identifier":{"issn":["0302-9743"]},"status":"public","month":"08","ddc":["000"],"intvolume":"     11014","language":[{"iso":"eng"}],"publisher":"Springer","date_created":"2018-12-11T11:44:33Z","abstract":[{"lang":"eng","text":"Concurrent accesses to shared data structures must be synchronized to avoid data races. Coarse-grained synchronization, which locks the entire data structure, is easy to implement but does not scale. Fine-grained synchronization can scale well, but can be hard to reason about. Hand-over-hand locking, in which operations are pipelined as they traverse the data structure, combines fine-grained synchronization with ease of use. However, the traditional implementation suffers from inherent overheads. This paper introduces snapshot-based synchronization (SBS), a novel hand-over-hand locking mechanism. SBS decouples the synchronization state from the data, significantly improving cache utilization. Further, it relies on guarantees provided by pipelining to minimize synchronization that requires cross-thread communication. Snapshot-based synchronization thus scales much better than traditional hand-over-hand locking, while maintaining the same ease of use."}],"has_accepted_license":"1","alternative_title":["LNCS"],"date_published":"2018-08-01T00:00:00Z","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","file":[{"date_updated":"2020-07-14T12:48:14Z","file_id":"5954","file_size":665372,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2019-02-12T07:40:40Z","checksum":"13a3f250be8878405e791b53c19722ad","creator":"dernst","file_name":"2018_Brown.pdf"}],"publication_status":"published","year":"2018","article_processing_charge":"No","oa":1,"isi":1,"type":"conference","page":"465 - 479"}]