Randomized algorithms for reliable broadcast
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/47746 |
| _version_ | 1811072106678452224 |
|---|---|
| author | Vaikuntanathan, Vinod |
| author2 | Shafi Goldwasser. |
| author_facet | Shafi Goldwasser. Vaikuntanathan, Vinod |
| author_sort | Vaikuntanathan, Vinod |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009. |
| first_indexed | 2024-09-23T09:00:59Z |
| format | Thesis |
| id | mit-1721.1/47746 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:00:59Z |
| publishDate | 2009 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/477462019-04-10T20:14:00Z Randomized algorithms for reliable broadcast Vaikuntanathan, Vinod Shafi Goldwasser. 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, 2009. Includes bibliographical references (p. 82-85). In this thesis, we design randomized algorithms for classical problems in fault tolerant distributed computing in the full-information model. The full-information model is a strong adversarial model which imposes no restrictions on the computational power of the faulty players nor on the information available to them. Namely, the faulty players are infinitely powerful and are privy to all the communications in the network. Our main result is the construction of two efficient randomized protocols for Byzantine agreement, a classical problem in distributed computing. Byzantine agreement is the problem of simulating the reliable broadcast functionality in a network where all communication is person-to-person. We design two randomized Byzantine agreement protocols in a synchronous network with an expected round-complexity of O(log n) rounds. One of the protocols is resilient against an all-powerful, full-information adversary that corrupts less than a third of the number of players (whereas the other protocol is resilient against a fourth fraction of corruptions). Our protocols have the following additional features. * The fault-tolerance of our protocols can be increased to less a half fraction of faults, if there is a public-key infrastructure setup available that allows the players to compute (public-key) digital signatures. * Our protocols work even if the source of randomness is a "somewhat random" source (also called a Santha-Vazirani source). The price we pay is a decreased fault-tolerance. Our second result is the design of a compiler that transforms a randomized distributed protocol that tolerates benign, fail-stop faults into a protocol that tolerates malicious, Byzantine faults. Fail-stop faults follow the protocol specification, but may stop in the middle of the execution. On the other hand, Byzantine faults are arbitrarily malicious. (cont.) The resulting protocol has almost the same fault-tolerance and efficiency as the original protocol. Our compiler suggests a modular way to design distributed protocols: first, design a protocol that tolerates fail-stop faults, and use our compiler to "boost" the fault-tolerance to Byzantine faults. The design of the compiler is based on a new protocol technique that we develop, called "auditing" of distributed protocols. by Vinod Vaikuntanathan. Ph.D. 2009-10-01T15:37:48Z 2009-10-01T15:37:48Z 2009 2009 Thesis http://hdl.handle.net/1721.1/47746 428735875 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 85 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Vaikuntanathan, Vinod Randomized algorithms for reliable broadcast |
| title | Randomized algorithms for reliable broadcast |
| title_full | Randomized algorithms for reliable broadcast |
| title_fullStr | Randomized algorithms for reliable broadcast |
| title_full_unstemmed | Randomized algorithms for reliable broadcast |
| title_short | Randomized algorithms for reliable broadcast |
| title_sort | randomized algorithms for reliable broadcast |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/47746 |
| work_keys_str_mv | AT vaikuntanathanvinod randomizedalgorithmsforreliablebroadcast |