{"id":{"repo_id":"unm","oai_identifier":"oai:digitalrepository.unm.edu:cs_etds-1029"},"canonical_url":"https://search.dev.ndltd.org/etd/unm/oai:digitalrepository.unm.edu:cs_etds-1029","repository":{"repo_id":"unm","name":"University of New Mexico","base_url":"https://digitalrepository.unm.edu/do/oai/"},"display":{"title":"Resource-Efficient and Robust Distributed Computing","abstract":"There has been a tremendous growth in the size of distributed systems in the past three decades. Today, distributed systems, such as the Internet, have become so large that they require highly scalable algorithms; algorithms that have asymptotically-small communication, computation, and latency costs with respect to the network size. Moreover, systems with thousands or even millions of parties distributed throughout the world is likely in danger of faults from untrusted parties. In this dissertation, we study scalable and secure distributed algorithms that can tolerate faults from untrusted parties. Throughout this work, we balance two important and often conflicting characteristics of distributed protocols: security and efficiency. Our first result is a protocol that solves the MPC problem in polylogarithmic communication and computation cost and is secure against an adversary than can corrupt a third of the parties. We adapted our synchronous MPC protocol to the asynchronous setting when the fraction of the corrupted parties are less than 1/8. Next, we presented a scalable protocol that solves the secret sharing problem between rational parties in polylogarithmic communication and computation cost. Furthermore, we presented a protocol that can solve the interactive communication problem over a noisy channel when the noise rate in unknown. In this problem, we have focused on the cost of the protocol in the resource-competitive analysis model. Unlike classic models, resource-competitive models consider the cost that the adversary must pay to succeed in corrupting the protocol.","abstract_html":"There has been a tremendous growth in the size of distributed systems in the past three decades. Today, distributed systems, such as the Internet, have become so large that they require highly scalable algorithms; algorithms that have asymptotically-small communication, computation, and latency costs with respect to the network size. Moreover, systems with thousands or even millions of parties distributed throughout the world is likely in danger of faults from untrusted parties. In this dissertation, we study scalable and secure distributed algorithms that can tolerate faults from untrusted parties. Throughout this work, we balance two important and often conflicting characteristics of distributed protocols: security and efficiency. Our first result is a protocol that solves the MPC problem in polylogarithmic communication and computation cost and is secure against an adversary than can corrupt a third of the parties. We adapted our synchronous MPC protocol to the asynchronous setting when the fraction of the corrupted parties are less than 1/8. Next, we presented a scalable protocol that solves the secret sharing problem between rational parties in polylogarithmic communication and computation cost. Furthermore, we presented a protocol that can solve the interactive communication problem over a noisy channel when the noise rate in unknown. In this problem, we have focused on the cost of the protocol in the resource-competitive analysis model. Unlike classic models, resource-competitive models consider the cost that the adversary must pay to succeed in corrupting the protocol.","abstract_has_math":false,"creators":["Movahedi Meimandi, Mahnush"],"institution":null,"degree_name":"Computer Science","degree_level":"Dissertation","degree_discipline":"Department of Computer Science","degree_department":null,"school":null,"contributors":["Saia, Jared","Evans, David","Luan, Shuang","Young, Maxwell"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-05-01T07:00:00Z","date_published":"2016-05-01T07:00:00Z","updated_at":"2026-07-24T05:26:00Z","subjects":["Distributed Computing","Multi-Party Computation","Interactive Communication"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalrepository.unm.edu/cs_etds/30"],"render_values":[{"text":"https://digitalrepository.unm.edu/cs_etds/30","href":"https://digitalrepository.unm.edu/cs_etds/30","code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/1928/32321","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Saia, Jared","Evans, David","Luan, Shuang","Young, Maxwell"]},{"key":"dc:creator","label":"Author","values":["Movahedi Meimandi, Mahnush"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_discipline","label":"Discipline","values":["Department of Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation","Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Computer Science"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Distributed Computing","Multi-Party Computation","Interactive Communication"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/1928/32321","https://digitalrepository.unm.edu/cs_etds/30"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["There has been a tremendous growth in the size of distributed systems in the past three decades. Today, distributed systems, such as the Internet, have become so large that they require highly scalable algorithms; algorithms that have asymptotically-small communication, computation, and latency costs with respect to the network size. Moreover, systems with thousands or even millions of parties distributed throughout the world is likely in danger of faults from untrusted parties. In this dissertation, we study scalable and secure distributed algorithms that can tolerate faults from untrusted parties. Throughout this work, we balance two important and often conflicting characteristics of distributed protocols: security and efficiency. Our first result is a protocol that solves the MPC problem in polylogarithmic communication and computation cost and is secure against an adversary than can corrupt a third of the parties. We adapted our synchronous MPC protocol to the asynchronous setting when the fraction of the corrupted parties are less than 1/8. Next, we presented a scalable protocol that solves the secret sharing problem between rational parties in polylogarithmic communication and computation cost. Furthermore, we presented a protocol that can solve the interactive communication problem over a noisy channel when the noise rate in unknown. In this problem, we have focused on the cost of the protocol in the resource-competitive analysis model. Unlike classic models, resource-competitive models consider the cost that the adversary must pay to succeed in corrupting the protocol."]},{"key":"dc:title","label":"Title","values":["Resource-Efficient and Robust Distributed Computing"]}]}],"canonical_facts":{"dc:contributor":["Saia, Jared","Evans, David","Luan, Shuang","Young, Maxwell"],"dc:creator":["Movahedi Meimandi, Mahnush"],"dc:description.abstract":["There has been a tremendous growth in the size of distributed systems in the past three decades. Today, distributed systems, such as the Internet, have become so large that they require highly scalable algorithms; algorithms that have asymptotically-small communication, computation, and latency costs with respect to the network size. Moreover, systems with thousands or even millions of parties distributed throughout the world is likely in danger of faults from untrusted parties. In this dissertation, we study scalable and secure distributed algorithms that can tolerate faults from untrusted parties. Throughout this work, we balance two important and often conflicting characteristics of distributed protocols: security and efficiency. Our first result is a protocol that solves the MPC problem in polylogarithmic communication and computation cost and is secure against an adversary than can corrupt a third of the parties. We adapted our synchronous MPC protocol to the asynchronous setting when the fraction of the corrupted parties are less than 1/8. Next, we presented a scalable protocol that solves the secret sharing problem between rational parties in polylogarithmic communication and computation cost. Furthermore, we presented a protocol that can solve the interactive communication problem over a noisy channel when the noise rate in unknown. In this problem, we have focused on the cost of the protocol in the resource-competitive analysis model. Unlike classic models, resource-competitive models consider the cost that the adversary must pay to succeed in corrupting the protocol."],"dc:identifier":["http://hdl.handle.net/1928/32321","https://digitalrepository.unm.edu/cs_etds/30"],"dc:language":["English"],"dc:subject":["Distributed Computing","Multi-Party Computation","Interactive Communication"],"dc:title":["Resource-Efficient and Robust Distributed Computing"],"thesis:degree_discipline":["Department of Computer Science"],"thesis:degree_level":["Dissertation","Doctoral"],"thesis:degree_name":["Computer Science"]},"updated_at":"2026-07-24T05:26:00Z"}