{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/120398"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/120398","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"All-to-all communication with low communication cost","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Wan, Jun (Computer scientist) Massachusetts Institute of Technology"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Srini Devadas."],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018","date_published":"2018","updated_at":"2026-07-22T22:22:26Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/120398","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Srini Devadas."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Wan, Jun (Computer scientist) Massachusetts Institute of Technology"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-02-14T15:48:02Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2019-02-14T15:48:02Z"]},{"key":"dc:date.issued","label":"Date","values":["2018"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/120398"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["All-to-all communication with low communication cost"]}]}],"canonical_facts":{"dc:contributor.advisor":["Srini Devadas."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Wan, Jun (Computer scientist) Massachusetts Institute of Technology"],"dc:date.accessioned":["2019-02-14T15:48:02Z"],"dc:date.available":["2019-02-14T15:48:02Z"],"dc:date.issued":["2018"],"dc:description":["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)."],"dc:description.abstract":["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."],"dc:description.degree":["S.M."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/120398"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["All-to-all communication with low communication cost"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:26Z"}