Lower bounds in distributed computing
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2008
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/43030 |
| _version_ | 1826214753787183104 |
|---|---|
| author | Fan, Rui, 1977- |
| author2 | Nancy A. Lynch. |
| author_facet | Nancy A. Lynch. Fan, Rui, 1977- |
| author_sort | Fan, Rui, 1977- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. |
| first_indexed | 2024-09-23T16:10:55Z |
| format | Thesis |
| id | mit-1721.1/43030 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:10:55Z |
| publishDate | 2008 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/430302019-04-12T08:54:23Z Lower bounds in distributed computing Fan, Rui, 1977- Nancy A. Lynch. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. Includes bibliographical references (p. 167-170). Distributed computing is the study of achieving cooperative behavior between independent computing processes with possibly conflicting goals. Distributed computing is ubiquitous in the Internet, wireless networks, multi-core and multi-processor computers, teams of mobile robots, etc. In this thesis, we study two fundamental distributed computing problems, clock synchronization and mutual exclusion. Our contributions are as follows. 1. We introduce the gradient clock synchronization (GCS) problem. As in traditional clock synchronization, a group of nodes in a bounded delay communication network try to synchronize their logical clocks, by reading their hardware clocks and exchanging messages. We say the distance between two nodes is the uncertainty in message delay between the nodes, and we say the clock skew between the nodes is their difference in logical clock values. GCS studies clock skew as a function of distance. We show that surprisingly, every clock synchronization algorithm exhibits some execution in which two nodes at distance one apart have Q( lo~gD clock skew, where D is the maximum distance between any pair of nodes. 2. We present an energy efficient and fault tolerant clock synchronization algorithm suitable for wireless networks. The algorithm synchronizes nodes to each other, as well as to real time. It satisfies a relaxed gradient property. That is, it guarantees that, using certain reasonable operating parameters, nearby nodes are well synchronized most of the time. 3. We study the mutual exclusion (mutex) problem, in which a set of processes in a shared memory system compete for exclusive access to a shared resource. We prove a tight Q(n log n) lower bound on the time for n processes to each access the resource once. . (cont.) Our novel proof technique is based on separately lower bounding the amount of information needed for solving mutex, and upper bounding the amount of information any mutex algorithm can acquire in each step. We hope that our results offer fresh ways of looking at classical problems, and point to interesting new open problems by Rui Fan. Ph.D. 2008-11-07T18:54:03Z 2008-11-07T18:54:03Z 2008 2008 Thesis http://hdl.handle.net/1721.1/43030 243603548 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 170 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Fan, Rui, 1977- Lower bounds in distributed computing |
| title | Lower bounds in distributed computing |
| title_full | Lower bounds in distributed computing |
| title_fullStr | Lower bounds in distributed computing |
| title_full_unstemmed | Lower bounds in distributed computing |
| title_short | Lower bounds in distributed computing |
| title_sort | lower bounds in distributed computing |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/43030 |
| work_keys_str_mv | AT fanrui1977 lowerboundsindistributedcomputing |