On the complexity of synchronization
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2017
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/111856 |
| _version_ | 1826206238621302784 |
|---|---|
| author | Gelashvili, Rati |
| author2 | Nir Shavit. |
| author_facet | Nir Shavit. Gelashvili, Rati |
| author_sort | Gelashvili, Rati |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017. |
| first_indexed | 2024-09-23T13:25:59Z |
| format | Thesis |
| id | mit-1721.1/111856 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:25:59Z |
| publishDate | 2017 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1118562019-04-12T22:22:45Z On the complexity of synchronization Gelashvili, Rati Nir Shavit. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 183-197). The field of distributed algorithms revolves around efficiently solving synchronization tasks, such as leader election and consensus. We make contributions towards a better understanding of the complexity of central tasks in standard distributed models. In the population protocols model, we demonstrate how to solve majority and leader election efficiently, in time 0(log² n), using 0(log n) states per node, for n nodes. Central to our algorithms is a new leaderless phase clock technique. We also prove tight lower bounds on the state complexity of solving these tasks. In shared memory, we prove that any nondeterministic solo terminating consensus algorithm for anonymous processes has to use [omega](n) read-write registers. Then, we show how to solve n-process wait-free consensus by combining synchronization instructions that would be considered "weak" according to Herlihy's consensus hierarchy. This collapses the hierarchy when instructions can be applied to the same memory location, as is the case in all existing multicore processors. We suggest an alternative hierarchy and provide a practical universal construction using only "weak" instructions, that performs as well as the Compare-and-Swap-based solution. Space complexity of solving k-set agreement is a problem that highlights important gaps in our understanding and state-of-the-art methods. No general lower bound better than 2 is known. We introduce a new technique based on an indirect black-box application of Sperner's Lemma through an algorithmic reduction to the impossibility of wait-free k-set agreement. We design a simulation such that for any protocol either the simulating processes solve wait-free k-set agreement (impossible), or they simulate an execution of that uses many registers. Finally, time complexity of leader election is a long-standing open problem. We give an algorithm with 0(log* k) time complexity in asynchronous message-passing system, for k participants. by Rati Gelashvili. Ph. D. 2017-10-18T14:42:24Z 2017-10-18T14:42:24Z 2017 2017 Thesis http://hdl.handle.net/1721.1/111856 1004959717 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 197 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Gelashvili, Rati On the complexity of synchronization |
| title | On the complexity of synchronization |
| title_full | On the complexity of synchronization |
| title_fullStr | On the complexity of synchronization |
| title_full_unstemmed | On the complexity of synchronization |
| title_short | On the complexity of synchronization |
| title_sort | on the complexity of synchronization |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/111856 |
| work_keys_str_mv | AT gelashvilirati onthecomplexityofsynchronization |