All-to-all communication with low communication cost

Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.

Bibliographic Details
Main Author: Wan, Jun (Computer scientist) Massachusetts Institute of Technology
Other Authors: Srini Devadas.
Format: Thesis
Language:eng
Published: Massachusetts Institute of Technology 2019
Subjects:
Online Access:http://hdl.handle.net/1721.1/120398
_version_ 1826216756518060032
author Wan, Jun (Computer scientist) Massachusetts Institute of Technology
author2 Srini Devadas.
author_facet Srini Devadas.
Wan, Jun (Computer scientist) Massachusetts Institute of Technology
author_sort Wan, Jun (Computer scientist) Massachusetts Institute of Technology
collection MIT
description Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.
first_indexed 2024-09-23T16:52:37Z
format Thesis
id mit-1721.1/120398
institution Massachusetts Institute of Technology
language eng
last_indexed 2024-09-23T16:52:37Z
publishDate 2019
publisher Massachusetts Institute of Technology
record_format dspace
spelling mit-1721.1/1203982024-06-28T12:55:30Z All-to-all communication with low communication cost Wan, Jun (Computer scientist) Massachusetts Institute of Technology Srini Devadas. 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: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018. Cataloged from PDF version of thesis. Includes bibliographical references (pages 61-64). In an all-to-all broadcast, every user wishes to broadcast its message to all the other users. This is a process that frequently appears in large-scale distributed systems such as voting and consensus protocols. In the classic solution, a user needs to receive n messages and n signatures where n is the number of users in the network. This is undesirable for large-scale distributed systems that contain millions or billions of users and can be the throughput bottleneck for some existing systems. In this thesis, we propose two protocols for the all-to-all broadcast problem. Our protocols upper bound the number of bits each user receives by [Theta](n log log2 n), which is a huge improvement from the conventional n times the signature size. Besides the all-to-all protocol, we also provide new results regarding random graphs and regular graphs. These results are used in our protocol to prove its efficiency. But they are interesting by themselves and have independent theoretic value. by Jun Wan. S.M. 2019-02-14T15:48:02Z 2019-02-14T15:48:02Z 2018 2018 Thesis http://hdl.handle.net/1721.1/120398 1083763300 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 64 pages application/pdf Massachusetts Institute of Technology
spellingShingle Electrical Engineering and Computer Science.
Wan, Jun (Computer scientist) Massachusetts Institute of Technology
All-to-all communication with low communication cost
title All-to-all communication with low communication cost
title_full All-to-all communication with low communication cost
title_fullStr All-to-all communication with low communication cost
title_full_unstemmed All-to-all communication with low communication cost
title_short All-to-all communication with low communication cost
title_sort all to all communication with low communication cost
topic Electrical Engineering and Computer Science.
url http://hdl.handle.net/1721.1/120398
work_keys_str_mv AT wanjuncomputerscientistmassachusettsinstituteoftechnology alltoallcommunicationwithlowcommunicationcost