Efficient algorithms for new computational models
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/17018 |
| _version_ | 1826211784320614400 |
|---|---|
| author | Ruhl, Jan Matthias, 1973- |
| author2 | David R. Karger. |
| author_facet | David R. Karger. Ruhl, Jan Matthias, 1973- |
| author_sort | Ruhl, Jan Matthias, 1973- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003. |
| first_indexed | 2024-09-23T15:11:21Z |
| format | Thesis |
| id | mit-1721.1/17018 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:11:21Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/170182019-04-10T09:38:00Z Efficient algorithms for new computational models Ruhl, Jan Matthias, 1973- David R. Karger. 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, 2003. Includes bibliographical references (p. 155-163). This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Advances in hardware design and manufacturing often lead to new ways in which problems can be solved computationally. In this thesis we explore fundamental problems in three computational models that are based on such recent advances. The first model is based on new chip architectures, where multiple independent processing units are placed on one chip, allowing for an unprecedented parallelism in hardware. We provide new scheduling algorithms for this computational model. The second model is motivated by peer-to-peer networks, where countless (often inexpensive) computing devices cooperate in distributed applications without any central control. We state and analyze new algorithms for load balancing and for locality-aware distributed data storage in peer-to-peer networks. The last model is based on extensions of the streaming model. It is an attempt to capture the class of problems that can be efficiently solved on massive data sets. We give a number of algorithms for this model, and compare it to other models that have been proposed for massive data set computations. Our algorithms and complexity results for these computational models follow the central thesis that it is an important part of theoretical computer science to model real-world computational structures, and that such effort is richly rewarded by a plethora of interesting and challenging problems. by Jan Matthias Ruhl. Ph.D. 2005-05-19T15:40:48Z 2005-05-19T15:40:48Z 2003 2003 Thesis http://hdl.handle.net/1721.1/17018 54457280 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 163 p. 1188364 bytes 1287306 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Ruhl, Jan Matthias, 1973- Efficient algorithms for new computational models |
| title | Efficient algorithms for new computational models |
| title_full | Efficient algorithms for new computational models |
| title_fullStr | Efficient algorithms for new computational models |
| title_full_unstemmed | Efficient algorithms for new computational models |
| title_short | Efficient algorithms for new computational models |
| title_sort | efficient algorithms for new computational models |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/17018 |
| work_keys_str_mv | AT ruhljanmatthias1973 efficientalgorithmsfornewcomputationalmodels |