--- _id: '7455' abstract: - lang: eng text: 'The reaction between NiO and (0001)- and ([1\bar102])-oriented Al2O3 single crystals has been investigated on model experimental systems by using the ReflEXAFS technique. Depth-sensitive information is obtained by collecting data above and below the critical angle for total reflection. A systematic protocol for data analysis, based on the recently developed CARD code, was implemented, and a detailed description of the reactive systems was obtained. In particular, for ([1\bar102])-oriented Al2O3, the reaction with NiO is almost complete after heating for 6 h at 1273 K, and an almost uniform layer of spinel is found below a mixed (NiO + spinel) layer at the very upmost part of the sample. In the case of the (0001)-oriented Al2O3, for the same temperature and heating time, the reaction shows a lower advancement degree and a residual fraction of at least 30% NiO is detected in the ReflEXAFS spectra. ' article_processing_charge: No article_type: original author: - first_name: Tommaso full_name: Costanzo, Tommaso id: D93824F4-D9BA-11E9-BB12-F207E6697425 last_name: Costanzo orcid: 0000-0001-9732-3815 - first_name: Federico full_name: Benzi, Federico last_name: Benzi - first_name: Paolo full_name: Ghigna, Paolo last_name: Ghigna - first_name: Sonia full_name: Pin, Sonia last_name: Pin - first_name: Giorgio full_name: Spinolo, Giorgio last_name: Spinolo - first_name: Francesco full_name: d'Acapito, Francesco last_name: d'Acapito citation: ama: Costanzo T, Benzi F, Ghigna P, Pin S, Spinolo G, d’Acapito F. Studying the surface reaction between NiO and Al2O3viatotal reflection EXAFS (ReflEXAFS). Journal of Synchrotron Radiation. 2014;21(2):395-400. doi:10.1107/s1600577513031299 apa: Costanzo, T., Benzi, F., Ghigna, P., Pin, S., Spinolo, G., & d’Acapito, F. (2014). Studying the surface reaction between NiO and Al2O3viatotal reflection EXAFS (ReflEXAFS). Journal of Synchrotron Radiation. International Union of Crystallography. https://doi.org/10.1107/s1600577513031299 chicago: Costanzo, Tommaso, Federico Benzi, Paolo Ghigna, Sonia Pin, Giorgio Spinolo, and Francesco d’Acapito. “Studying the Surface Reaction between NiO and Al2O3viatotal Reflection EXAFS (ReflEXAFS).” Journal of Synchrotron Radiation. International Union of Crystallography, 2014. https://doi.org/10.1107/s1600577513031299. ieee: T. Costanzo, F. Benzi, P. Ghigna, S. Pin, G. Spinolo, and F. d’Acapito, “Studying the surface reaction between NiO and Al2O3viatotal reflection EXAFS (ReflEXAFS),” Journal of Synchrotron Radiation, vol. 21, no. 2. International Union of Crystallography, pp. 395–400, 2014. ista: Costanzo T, Benzi F, Ghigna P, Pin S, Spinolo G, d’Acapito F. 2014. Studying the surface reaction between NiO and Al2O3viatotal reflection EXAFS (ReflEXAFS). Journal of Synchrotron Radiation. 21(2), 395–400. mla: Costanzo, Tommaso, et al. “Studying the Surface Reaction between NiO and Al2O3viatotal Reflection EXAFS (ReflEXAFS).” Journal of Synchrotron Radiation, vol. 21, no. 2, International Union of Crystallography, 2014, pp. 395–400, doi:10.1107/s1600577513031299. short: T. Costanzo, F. Benzi, P. Ghigna, S. Pin, G. Spinolo, F. d’Acapito, Journal of Synchrotron Radiation 21 (2014) 395–400. date_created: 2020-02-05T14:14:48Z date_published: 2014-01-10T00:00:00Z date_updated: 2023-02-23T13:08:22Z day: '10' doi: 10.1107/s1600577513031299 extern: '1' intvolume: ' 21' issue: '2' language: - iso: eng month: '01' oa_version: None page: 395-400 publication: Journal of Synchrotron Radiation publication_identifier: issn: - 1600-5775 publication_status: published publisher: International Union of Crystallography quality_controlled: '1' status: public title: Studying the surface reaction between NiO and Al2O3viatotal reflection EXAFS (ReflEXAFS) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 21 year: '2014' ... --- _id: '7598' article_processing_charge: No article_type: original author: - first_name: Shutang full_name: Tan, Shutang id: 2DE75584-F248-11E8-B48F-1D18A9856A87 last_name: Tan orcid: 0000-0002-0471-8285 - first_name: Hong-Wei full_name: Xue, Hong-Wei last_name: Xue citation: ama: Tan S, Xue H-W. Casein kinase 1 regulates ethylene synthesis by phosphorylating and promoting the turnover of ACS5. Cell Reports. 2014;9(5):1692-1702. doi:10.1016/j.celrep.2014.10.047 apa: Tan, S., & Xue, H.-W. (2014). Casein kinase 1 regulates ethylene synthesis by phosphorylating and promoting the turnover of ACS5. Cell Reports. Elsevier. https://doi.org/10.1016/j.celrep.2014.10.047 chicago: Tan, Shutang, and Hong-Wei Xue. “Casein Kinase 1 Regulates Ethylene Synthesis by Phosphorylating and Promoting the Turnover of ACS5.” Cell Reports. Elsevier, 2014. https://doi.org/10.1016/j.celrep.2014.10.047. ieee: S. Tan and H.-W. Xue, “Casein kinase 1 regulates ethylene synthesis by phosphorylating and promoting the turnover of ACS5,” Cell Reports, vol. 9, no. 5. Elsevier, pp. 1692–1702, 2014. ista: Tan S, Xue H-W. 2014. Casein kinase 1 regulates ethylene synthesis by phosphorylating and promoting the turnover of ACS5. Cell Reports. 9(5), 1692–1702. mla: Tan, Shutang, and Hong-Wei Xue. “Casein Kinase 1 Regulates Ethylene Synthesis by Phosphorylating and Promoting the Turnover of ACS5.” Cell Reports, vol. 9, no. 5, Elsevier, 2014, pp. 1692–702, doi:10.1016/j.celrep.2014.10.047. short: S. Tan, H.-W. Xue, Cell Reports 9 (2014) 1692–1702. date_created: 2020-03-21T16:08:18Z date_published: 2014-12-11T00:00:00Z date_updated: 2021-01-12T08:14:24Z day: '11' ddc: - '580' doi: 10.1016/j.celrep.2014.10.047 extern: '1' file: - access_level: open_access checksum: 23c30de4ac98ce9879fc054121517626 content_type: application/pdf creator: dernst date_created: 2020-03-23T12:23:40Z date_updated: 2020-07-14T12:48:01Z file_id: '7613' file_name: 2014_CellPress_Tan.pdf file_size: 2755808 relation: main_file file_date_updated: 2020-07-14T12:48:01Z has_accepted_license: '1' intvolume: ' 9' issue: '5' language: - iso: eng license: https://creativecommons.org/licenses/by-nc-nd/4.0/ month: '12' oa: 1 oa_version: Published Version page: 1692-1702 publication: Cell Reports publication_identifier: issn: - 2211-1247 publication_status: published publisher: Elsevier quality_controlled: '1' status: public title: Casein kinase 1 regulates ethylene synthesis by phosphorylating and promoting the turnover of ACS5 tmp: image: /images/cc_by_nc_nd.png legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) short: CC BY-NC-ND (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9 year: '2014' ... --- _id: '768' abstract: - lang: eng text: 'Task allocation is a classic distributed problem in which a set of p potentially faulty processes must cooperate to perform a set of tasks. This paper considers a new dynamic version of the problem, in which tasks are injected adversarially during an asynchronous execution. We give the first asynchronous shared-memory algorithm for dynamic task allocation, and we prove that our solution is optimal within logarithmic factors. The main algorithmic idea is a randomized concurrent data structure called a dynamic to-do tree, which allows processes to pick new tasks to perform at random from the set of available tasks, and to insert tasks at random empty locations in the data structure. Our analysis shows that these properties avoid duplicating work unnecessarily. On the other hand, since the adversary controls the input as well the scheduling, it can induce executions where lots of processes contend for a few available tasks, which is inefficient. However, we prove that every algorithm has the same problem: given an arbitrary input, if OPT is the worst-case complexity of the optimal algorithm on that input, then the expected work complexity of our algorithm on the same input is O(OPT log3 m), where m is an upper bound on the number of tasks that are present in the system at any given time.' acknowledgement: "Dan Alistarh - This author was supported by the SNF Postdoctoral Fellows Program, NSF grant CCF-1217921, DoE ASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations.\r\nJames Aspnes - Supported in part by NSF grant CCF-0916389.\r\nMichael A. Bender - This research was supported in part by NSF grants CCF 1114809, CCF 1217708, IIS 1247726, and IIS 1251137.\r\nRati Gelashvili - This work was supported in part by NSF grants CCF-1217921, CCF-1301926, DoE ASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations.\r\nSeth Gilbert - Supported by Singapore AcRF-2 MOE2011-T2-2-042.\r\n" article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: James full_name: Aspnes, James last_name: Aspnes - first_name: Michael full_name: Bender, Michael last_name: Bender - first_name: Rati full_name: Gelashvili, Rati last_name: Gelashvili - first_name: Seth full_name: Gilbert, Seth last_name: Gilbert citation: ama: 'Alistarh D-A, Aspnes J, Bender M, Gelashvili R, Gilbert S. Dynamic task allocation in asynchronous shared memory. In: SIAM; 2014:416-435. doi:10.1137/1.9781611973402.31' apa: 'Alistarh, D.-A., Aspnes, J., Bender, M., Gelashvili, R., & Gilbert, S. (2014). Dynamic task allocation in asynchronous shared memory (pp. 416–435). Presented at the SODA: Symposium on Discrete Algorithms, SIAM. https://doi.org/10.1137/1.9781611973402.31' chicago: Alistarh, Dan-Adrian, James Aspnes, Michael Bender, Rati Gelashvili, and Seth Gilbert. “Dynamic Task Allocation in Asynchronous Shared Memory,” 416–35. SIAM, 2014. https://doi.org/10.1137/1.9781611973402.31. ieee: 'D.-A. Alistarh, J. Aspnes, M. Bender, R. Gelashvili, and S. Gilbert, “Dynamic task allocation in asynchronous shared memory,” presented at the SODA: Symposium on Discrete Algorithms, 2014, pp. 416–435.' ista: 'Alistarh D-A, Aspnes J, Bender M, Gelashvili R, Gilbert S. 2014. Dynamic task allocation in asynchronous shared memory. SODA: Symposium on Discrete Algorithms, 416–435.' mla: Alistarh, Dan-Adrian, et al. Dynamic Task Allocation in Asynchronous Shared Memory. SIAM, 2014, pp. 416–35, doi:10.1137/1.9781611973402.31. short: D.-A. Alistarh, J. Aspnes, M. Bender, R. Gelashvili, S. Gilbert, in:, SIAM, 2014, pp. 416–435. conference: name: 'SODA: Symposium on Discrete Algorithms' date_created: 2018-12-11T11:48:24Z date_published: 2014-01-01T00:00:00Z date_updated: 2023-02-23T13:13:52Z day: '01' doi: 10.1137/1.9781611973402.31 extern: '1' language: - iso: eng month: '01' oa_version: None page: 416 - 435 publication_status: published publisher: SIAM publist_id: '6886' status: public title: Dynamic task allocation in asynchronous shared memory type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '769' abstract: - lang: eng text: 'This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual lower bound of ω(k) process steps for deterministic renaming into any namespace of size subexponential in k, where k is the number of participants. The bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic concurrent fetch-and-increment counters, queues, and stacks. The proof is based on a new reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement this individual bound with a global lower bound of ω(klog(k/c)) on the total step complexity of renaming into a namespace of size ck, for any c = 1. This result applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter implementations, that are tight within logarithmic factors. On the algorithmic side, we give a protocol that transforms any sorting network into a randomized strong adaptive renaming algorithm, with expected cost equal to the depth of the sorting network. This gives a tight adaptive renaming algorithm with expected step complexity O(log k), where k is the contention in the current execution. This algorithm is the first to achieve sublinear time, and it is time-optimal as per our randomized lower bound. Finally, we use this renaming protocol to build monotone-consistent counters with logarithmic step complexity and linearizable fetch-and-increment registers with polylogarithmic cost.' acknowledgement: "The work of J. Aspnes was supported in part by NSF grant CCF-0916389. The work of S. Gilbert was\r\nsupported by Singapore AcRF-2 MOE 2011-T2-2-042.\r\nK. Censor-Hillel is a Shalon Fellow. Part of this work was performed while K. Censor-Hillel was a postdoc at\r\nMIT, supported by the Simons Postdoctoral Fellowship." article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: James full_name: Aspnes, James last_name: Aspnes - first_name: Keren full_name: Censor Hillel, Keren last_name: Censor Hillel - first_name: Seth full_name: Gilbert, Seth last_name: Gilbert - first_name: Rachid full_name: Guerraoui, Rachid last_name: Guerraoui citation: ama: Alistarh D-A, Aspnes J, Censor Hillel K, Gilbert S, Guerraoui R. Tight bounds for asynchronous renaming. Journal of the ACM. 2014;61(3). doi:10.1145/2597630 apa: Alistarh, D.-A., Aspnes, J., Censor Hillel, K., Gilbert, S., & Guerraoui, R. (2014). Tight bounds for asynchronous renaming. Journal of the ACM. ACM. https://doi.org/10.1145/2597630 chicago: Alistarh, Dan-Adrian, James Aspnes, Keren Censor Hillel, Seth Gilbert, and Rachid Guerraoui. “Tight Bounds for Asynchronous Renaming.” Journal of the ACM. ACM, 2014. https://doi.org/10.1145/2597630. ieee: D.-A. Alistarh, J. Aspnes, K. Censor Hillel, S. Gilbert, and R. Guerraoui, “Tight bounds for asynchronous renaming,” Journal of the ACM, vol. 61, no. 3. ACM, 2014. ista: Alistarh D-A, Aspnes J, Censor Hillel K, Gilbert S, Guerraoui R. 2014. Tight bounds for asynchronous renaming. Journal of the ACM. 61(3). mla: Alistarh, Dan-Adrian, et al. “Tight Bounds for Asynchronous Renaming.” Journal of the ACM, vol. 61, no. 3, ACM, 2014, doi:10.1145/2597630. short: D.-A. Alistarh, J. Aspnes, K. Censor Hillel, S. Gilbert, R. Guerraoui, Journal of the ACM 61 (2014). date_created: 2018-12-11T11:48:24Z date_published: 2014-05-01T00:00:00Z date_updated: 2023-02-23T13:14:09Z day: '01' doi: 10.1145/2597630 extern: '1' intvolume: ' 61' issue: '3' language: - iso: eng month: '05' oa_version: None publication: Journal of the ACM publication_status: published publisher: ACM publist_id: '6887' status: public title: Tight bounds for asynchronous renaming type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 61 year: '2014' ... --- _id: '770' abstract: - lang: eng text: 'Dynamic memory reclamation is arguably the biggest open problem in concurrent data structure design: All known solutions induce high overhead, or must be customized to the specific data structure by the programmer, or both. This paper presents StackTrack, the first concurrent memory reclamation scheme that can be applied automatically by a compiler, while maintaining efficiency. StackTrack eliminates most of the expensive bookkeeping required for memory reclamation by leveraging the power of hardware transactional memory (HTM) in a new way: it tracks thread variables dynamically, and in an atomic fashion. This effectively makes all memory references visible without having threads pay the overhead of writing out this information. Our empirical results show that this new approach matches or outperforms prior, non-automated, techniques.' acknowledgement: "Dan Alistarh - Part of this work was performed while the \ author was a Postdoctoral\r\nAssociate a MIT CSAIL, supported in part by NSF grant CCF-1217921,\r\nDoE ASCR grant ER26116/DE-SC0008923, and by grants from the Oracle\r\nand Intel corporations.\r\nPatrick Eugester - Supported in part by DARPA grant N11AP20014 and NSF grant CNS-\r\n1117065.\r\nMaurice Herlihy - Supported by NSF grant 1301924.\r\nNir Shavit - Supported in part by NSF grants CCF-1217921 and CCF-1301926, DoE\r\nASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and\r\nIntel corporations." article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Patrick full_name: Eugster, Patrick last_name: Eugster - first_name: Maurice full_name: Herlihy, Maurice last_name: Herlihy - first_name: Alexander full_name: Matveev, Alexander last_name: Matveev - first_name: Nir full_name: Shavit, Nir last_name: Shavit citation: ama: 'Alistarh D-A, Eugster P, Herlihy M, Matveev A, Shavit N. StackTrack: An automated transactional approach to concurrent memory reclamation. In: ACM; 2014. doi:10.1145/2592798.2592808' apa: 'Alistarh, D.-A., Eugster, P., Herlihy, M., Matveev, A., & Shavit, N. (2014). StackTrack: An automated transactional approach to concurrent memory reclamation. Presented at the EuroSys: European Conference on Computer Systems, ACM. https://doi.org/10.1145/2592798.2592808' chicago: 'Alistarh, Dan-Adrian, Patrick Eugster, Maurice Herlihy, Alexander Matveev, and Nir Shavit. “StackTrack: An Automated Transactional Approach to Concurrent Memory Reclamation.” ACM, 2014. https://doi.org/10.1145/2592798.2592808.' ieee: 'D.-A. Alistarh, P. Eugster, M. Herlihy, A. Matveev, and N. Shavit, “StackTrack: An automated transactional approach to concurrent memory reclamation,” presented at the EuroSys: European Conference on Computer Systems, 2014.' ista: 'Alistarh D-A, Eugster P, Herlihy M, Matveev A, Shavit N. 2014. StackTrack: An automated transactional approach to concurrent memory reclamation. EuroSys: European Conference on Computer Systems.' mla: 'Alistarh, Dan-Adrian, et al. StackTrack: An Automated Transactional Approach to Concurrent Memory Reclamation. ACM, 2014, doi:10.1145/2592798.2592808.' short: D.-A. Alistarh, P. Eugster, M. Herlihy, A. Matveev, N. Shavit, in:, ACM, 2014. conference: name: 'EuroSys: European Conference on Computer Systems' date_created: 2018-12-11T11:48:24Z date_published: 2014-01-01T00:00:00Z date_updated: 2023-02-23T13:14:25Z day: '01' doi: 10.1145/2592798.2592808 extern: '1' language: - iso: eng month: '01' oa_version: None publication_status: published publisher: ACM publist_id: '6888' status: public title: 'StackTrack: An automated transactional approach to concurrent memory reclamation' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '771' abstract: - lang: eng text: 'We consider the following natural problem: n failure-prone servers, communicating synchronously through message passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in synchronous message-passing systems; for deterministic solutions, a tight bound of ©(logn) communication rounds is known. Second, model the scenario as an instance of randomized load-balancing, for which elegant sub-logarithmic solutions exist. However, careful examination reveals that known load-balancing schemes do not apply to our scenario, because they either do not tolerate faults or do not ensure one-to-one allocation. It is thus natural to ask if sublogarithmic solutions exist for this apparently simple but intriguing problem. In this paper, we combine the two approaches to provide a new randomized solution for tight renaming, which terminates in O (log log n) communication rounds with high probability, against a strong adaptive adversary. Our solution, called Balls-into-Leaves, combines the deterministic approach with a new randomized scheme to obtain perfectly balanced allocations. The algorithm arranges the items as leaves of a tree, and participants repeatedly perform random choices among the leaves. The algorithm exchanges information in each round to split the participants into progressively smaller groups whose random choices do not conflict. We then extend the algorithm to terminate early in O(log log) rounds w.h.p., where is the actual number of failures. These results imply an exponential separation between deterministic and randomized algorithms for the tight renaming problem in message-passing systems.' acknowledgement: "Dan Alistarh was partially supported by the SNF Post-\r\ndoctoral Fellows Program, NSF grant CCF-1217921, DoE\r\nASCR grant ER26116/DE-SC0008923, and by grants from\r\nthe Oracle and Intel corporations.\r\nOksana Denysyuk and Lu ́ıs Rodrigues were partially supported by Funda ̧c ̃ao para a Ciˆencia e Tecnologia (FCT) via\r\nthe project PEPITA (PTDC/EEI-SCR/2776/2012) and via\r\nthe INESC-ID multi-annual funding through the PIDDAC\r\nProgram fund grant, under project PEst-OE/EEI/LA0021/\r\n2013.\r\nNir Shavit was supported in part by NSF grants CCF-1217921 and CCF-1301926, DoE ASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations." article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Oksana full_name: Denysyuk, Oksana last_name: Denysyuk - first_name: Luís full_name: Rodrígues, Luís last_name: Rodrígues - first_name: Nir full_name: Shavit, Nir last_name: Shavit citation: ama: 'Alistarh D-A, Denysyuk O, Rodrígues L, Shavit N. Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems. In: ACM; 2014:232-241. doi:10.1145/2611462.2611499' apa: 'Alistarh, D.-A., Denysyuk, O., Rodrígues, L., & Shavit, N. (2014). Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems (pp. 232–241). Presented at the PODC: Principles of Distributed Computing, ACM. https://doi.org/10.1145/2611462.2611499' chicago: 'Alistarh, Dan-Adrian, Oksana Denysyuk, Luís Rodrígues, and Nir Shavit. “Balls-into-Leaves: Sub-Logarithmic Renaming in Synchronous Message-Passing Systems,” 232–41. ACM, 2014. https://doi.org/10.1145/2611462.2611499.' ieee: 'D.-A. Alistarh, O. Denysyuk, L. Rodrígues, and N. Shavit, “Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems,” presented at the PODC: Principles of Distributed Computing, 2014, pp. 232–241.' ista: 'Alistarh D-A, Denysyuk O, Rodrígues L, Shavit N. 2014. Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems. PODC: Principles of Distributed Computing, 232–241.' mla: 'Alistarh, Dan-Adrian, et al. Balls-into-Leaves: Sub-Logarithmic Renaming in Synchronous Message-Passing Systems. ACM, 2014, pp. 232–41, doi:10.1145/2611462.2611499.' short: D.-A. Alistarh, O. Denysyuk, L. Rodrígues, N. Shavit, in:, ACM, 2014, pp. 232–241. conference: name: 'PODC: Principles of Distributed Computing' date_created: 2018-12-11T11:48:25Z date_published: 2014-01-01T00:00:00Z date_updated: 2023-02-23T13:14:49Z day: '01' doi: 10.1145/2611462.2611499 extern: '1' language: - iso: eng month: '01' oa_version: None page: 232 - 241 publication_status: published publisher: ACM publist_id: '6884' status: public title: 'Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '772' abstract: - lang: eng text: Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior. acknowledgement: "Dan Alistarh - Part of this work was performed while the author was a Postdoctoral Associate at MIT CSAIL, where he was supported by SNF\r\nPostdoctoral Fellows Program, NSF grant CCF-1217921, DoE\r\nASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations.\r\nKeron Censor-Hillel - Shalon Fellow\r\nNir Shavit - This work was supported in part by NSF grants CCF-1217921 and\r\nCCF-1301926, DoE ASCR grant ER26116/DE-SC0008923, and\r\nby grants from the Oracle and Intel corporations." article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Keren full_name: Censor Hillel, Keren last_name: Censor Hillel - first_name: Nir full_name: Shavit, Nir last_name: Shavit citation: ama: 'Alistarh D-A, Censor Hillel K, Shavit N. Are lock-free concurrent algorithms practically wait-free? In: ACM; 2014:714-723. doi:10.1145/2591796.2591836' apa: 'Alistarh, D.-A., Censor Hillel, K., & Shavit, N. (2014). Are lock-free concurrent algorithms practically wait-free? (pp. 714–723). Presented at the STOC: Symposium on Theory of Computing, ACM. https://doi.org/10.1145/2591796.2591836' chicago: Alistarh, Dan-Adrian, Keren Censor Hillel, and Nir Shavit. “Are Lock-Free Concurrent Algorithms Practically Wait-Free?,” 714–23. ACM, 2014. https://doi.org/10.1145/2591796.2591836. ieee: 'D.-A. Alistarh, K. Censor Hillel, and N. Shavit, “Are lock-free concurrent algorithms practically wait-free?,” presented at the STOC: Symposium on Theory of Computing, 2014, pp. 714–723.' ista: 'Alistarh D-A, Censor Hillel K, Shavit N. 2014. Are lock-free concurrent algorithms practically wait-free? STOC: Symposium on Theory of Computing, 714–723.' mla: Alistarh, Dan-Adrian, et al. Are Lock-Free Concurrent Algorithms Practically Wait-Free? ACM, 2014, pp. 714–23, doi:10.1145/2591796.2591836. short: D.-A. Alistarh, K. Censor Hillel, N. Shavit, in:, ACM, 2014, pp. 714–723. conference: name: 'STOC: Symposium on Theory of Computing' date_created: 2018-12-11T11:48:25Z date_published: 2014-01-01T00:00:00Z date_updated: 2023-02-23T13:15:13Z day: '01' doi: 10.1145/2591796.2591836 extern: '1' external_id: arxiv: - '1311.3200' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1311.3200 month: '01' oa: 1 oa_version: Preprint page: 714 - 723 publication_status: published publisher: ACM publist_id: '6885' status: public title: Are lock-free concurrent algorithms practically wait-free? type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '773' abstract: - lang: eng text: "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(n log3n) 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 protocol uses messages of size O(log n), and can therefore scale to large networks.\r\n\r\nWe 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.\r\n\r\nOur 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." alternative_title: - LNCS article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: James full_name: Aspnes, James last_name: Aspnes - first_name: Valerie full_name: King, Valerie last_name: King - first_name: Jared full_name: Saia, Jared last_name: Saia citation: ama: 'Alistarh D-A, Aspnes J, King V, Saia J. Communication-efficient randomized consensus. In: Kuhn F, ed. Vol 8784. Springer; 2014:61-75. doi:10.1007/978-3-662-45174-8_5' apa: 'Alistarh, D.-A., Aspnes, J., King, V., & Saia, J. (2014). Communication-efficient randomized consensus. In F. Kuhn (Ed.) (Vol. 8784, pp. 61–75). Presented at the DISC: Distributed Computing, Austin, USA: Springer. https://doi.org/10.1007/978-3-662-45174-8_5' chicago: Alistarh, Dan-Adrian, James Aspnes, Valerie King, and Jared Saia. “Communication-Efficient Randomized Consensus.” edited by Fabian Kuhn, 8784:61–75. Springer, 2014. https://doi.org/10.1007/978-3-662-45174-8_5. ieee: 'D.-A. Alistarh, J. Aspnes, V. King, and J. Saia, “Communication-efficient randomized consensus,” presented at the DISC: Distributed Computing, Austin, USA, 2014, vol. 8784, pp. 61–75.' ista: 'Alistarh D-A, Aspnes J, King V, Saia J. 2014. Communication-efficient randomized consensus. DISC: Distributed Computing, LNCS, vol. 8784, 61–75.' mla: Alistarh, Dan-Adrian, et al. Communication-Efficient Randomized Consensus. Edited by Fabian Kuhn, vol. 8784, Springer, 2014, pp. 61–75, doi:10.1007/978-3-662-45174-8_5. short: D.-A. Alistarh, J. Aspnes, V. King, J. Saia, in:, F. Kuhn (Ed.), Springer, 2014, pp. 61–75. conference: end_date: 2014-10-15 location: Austin, USA name: 'DISC: Distributed Computing' start_date: 2014-10-12 date_created: 2018-12-11T11:48:25Z date_published: 2014-01-01T00:00:00Z date_updated: 2023-02-23T13:15:36Z day: '01' doi: 10.1007/978-3-662-45174-8_5 editor: - first_name: Fabian full_name: Kuhn, Fabian last_name: Kuhn extern: '1' intvolume: ' 8784' language: - iso: eng month: '01' oa_version: None page: 61 - 75 publication_status: published publisher: Springer publist_id: '6881' status: public title: Communication-efficient randomized consensus type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8784 year: '2014' ... --- _id: '774' abstract: - lang: eng text: Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers would prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is in general a complex undertaking, and the resulting algorithms are not always efficient, so most non-blocking commercial code is only lock-free, and the design of efficient wait-free algorithms has been left to the academic community. In [2], we suggest a solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a broad subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. acknowledgement: "Dan Alistarh - Part of this work was performed while the \ author was a\r\nPostdoctoral Associate at MIT CSAIL, where he was supported \ by SNF Postdoctoral Fellows Program, NSF grant\r\nCCF-1217921, DoE ASCR grant ER26116/DE-SC0008923,\r\nand by grants from the Oracle and Intel corporations.\r\nKeren Censor-Hille - Shalon Fellow\r\nNir Shavit - This work was supported in part \ by NSF grants CCF-1217921 and CCF-1301926, DoE ASCR grant ER26116/DE-\r\nSC0008923, and by grants from the Oracle and Intel corporations." article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Keren full_name: Censor Hille, Keren last_name: Censor Hille - first_name: Nir full_name: Shavit, Nir last_name: Shavit citation: ama: 'Alistarh D-A, Censor Hille K, Shavit N. Brief announcement: Are lock-free concurrent algorithms practically wait-free? In: ACM; 2014:50-52. doi:10.1145/2611462.2611502' apa: 'Alistarh, D.-A., Censor Hille, K., & Shavit, N. (2014). Brief announcement: Are lock-free concurrent algorithms practically wait-free? (pp. 50–52). Presented at the PODC: Principles of Distributed Computing, ACM. https://doi.org/10.1145/2611462.2611502' chicago: 'Alistarh, Dan-Adrian, Keren Censor Hille, and Nir Shavit. “Brief Announcement: Are Lock-Free Concurrent Algorithms Practically Wait-Free?,” 50–52. ACM, 2014. https://doi.org/10.1145/2611462.2611502.' ieee: 'D.-A. Alistarh, K. Censor Hille, and N. Shavit, “Brief announcement: Are lock-free concurrent algorithms practically wait-free?,” presented at the PODC: Principles of Distributed Computing, 2014, pp. 50–52.' ista: 'Alistarh D-A, Censor Hille K, Shavit N. 2014. Brief announcement: Are lock-free concurrent algorithms practically wait-free? PODC: Principles of Distributed Computing, 50–52.' mla: 'Alistarh, Dan-Adrian, et al. Brief Announcement: Are Lock-Free Concurrent Algorithms Practically Wait-Free? ACM, 2014, pp. 50–52, doi:10.1145/2611462.2611502.' short: D.-A. Alistarh, K. Censor Hille, N. Shavit, in:, ACM, 2014, pp. 50–52. conference: name: 'PODC: Principles of Distributed Computing' date_created: 2018-12-11T11:48:26Z date_published: 2014-01-01T00:00:00Z date_updated: 2023-02-23T13:15:54Z day: '01' doi: 10.1145/2611462.2611502 extern: '1' language: - iso: eng month: '01' oa_version: None page: 50 - 52 publication_status: published publisher: ACM publist_id: '6882' status: public title: 'Brief announcement: Are lock-free concurrent algorithms practically wait-free?' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '775' abstract: - lang: eng text: 'The long-lived renaming problem appears in shared-memory systems where a set of threads need to register and deregister frequently from the computation, while concurrent operations scan the set of currently registered threads. Instances of this problem show up in concurrent implementations of transactional memory, flat combining, thread barriers, and memory reclamation schemes for lock-free data structures. In this paper, we analyze a randomized solution for long-lived renaming. The algorithmic technique we consider, called the Level Array, has previously been used for hashing and one-shot (single-use) renaming. Our main contribution is to prove that, in long-lived executions, where processes may register and deregister polynomially many times, the technique guarantees constant steps on average and O (log log n) steps with high probability for registering, unit cost for deregistering, and O (n) steps for collect queries, where n is an upper bound on the number of processes that may be active at any point in time. We also show that the algorithm has the surprising property that it is self-healing: under reasonable assumptions on the schedule, operations running while the data structure is in a degraded state implicitly help the data structure re-balance itself. This subtle mechanism obviates the need for expensive periodic rebuilding procedures. Our benchmarks validate this approach, showing that, for typical use parameters, the average number of steps a process takes to register is less than two and the worst-case number of steps is bounded by six, even in executions with billions of operations. We contrast this with other randomized implementations, whose worst-case behavior we show to be unreliable, and with deterministic implementations, whose cost is linear in n.' article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Justin full_name: Kopinsky, Justin last_name: Kopinsky - first_name: Alexander full_name: Matveev, Alexander last_name: Matveev - first_name: Nir full_name: Shavit, Nir last_name: Shavit citation: ama: 'Alistarh D-A, Kopinsky J, Matveev A, Shavit N. The levelarray: A fast, practical long-lived renaming algorithm. In: IEEE; 2014:348-357. doi:10.1109/ICDCS.2014.43' apa: 'Alistarh, D.-A., Kopinsky, J., Matveev, A., & Shavit, N. (2014). The levelarray: A fast, practical long-lived renaming algorithm (pp. 348–357). Presented at the ICDCS: International Conference on Distributed Computing Systems, IEEE. https://doi.org/10.1109/ICDCS.2014.43' chicago: 'Alistarh, Dan-Adrian, Justin Kopinsky, Alexander Matveev, and Nir Shavit. “The Levelarray: A Fast, Practical Long-Lived Renaming Algorithm,” 348–57. IEEE, 2014. https://doi.org/10.1109/ICDCS.2014.43.' ieee: 'D.-A. Alistarh, J. Kopinsky, A. Matveev, and N. Shavit, “The levelarray: A fast, practical long-lived renaming algorithm,” presented at the ICDCS: International Conference on Distributed Computing Systems, 2014, pp. 348–357.' ista: 'Alistarh D-A, Kopinsky J, Matveev A, Shavit N. 2014. The levelarray: A fast, practical long-lived renaming algorithm. ICDCS: International Conference on Distributed Computing Systems, 348–357.' mla: 'Alistarh, Dan-Adrian, et al. The Levelarray: A Fast, Practical Long-Lived Renaming Algorithm. IEEE, 2014, pp. 348–57, doi:10.1109/ICDCS.2014.43.' short: D.-A. Alistarh, J. Kopinsky, A. Matveev, N. Shavit, in:, IEEE, 2014, pp. 348–357. conference: name: 'ICDCS: International Conference on Distributed Computing Systems' date_created: 2018-12-11T11:48:26Z date_published: 2014-08-29T00:00:00Z date_updated: 2023-02-23T13:16:18Z day: '29' doi: 10.1109/ICDCS.2014.43 extern: '1' external_id: arxiv: - '1405.5461' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1405.5461 month: '08' oa: 1 oa_version: Preprint page: 348 - 357 publication_status: published publisher: IEEE publist_id: '6883' status: public title: 'The levelarray: A fast, practical long-lived renaming algorithm' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ...