Efficient Consensus and Synchronization for Distributed Systems

Recent interest in decentralized applications calls for distributed systems that replicate their states across a large number of servers communicating over wide-area networks. We propose near-optimal solutions to two fundamental problems in the design and implementation of such systems: consensus and synchronization. First, we propose a universal decomposition of distributed consensus protocols that enables near-optimal throughput and liveness on fluctuating networks. Our key technique is to minimize the amount of communication necessary for participants to safely reach consensus. We design a state-of-the-art information dispersal protocol to achieve that. Second, we propose the first family of efficient rateless error-correcting codes for reconciling set differences. Our codes enable pairs of servers to synchronize system states with near-optimal communication and computation costs. We theoretically analyze these solutions, and implement end-to-end systems to demonstrate strong real-world benefits.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Yang, Lei

Advisor dc:contributor.advisor

• Alizadeh, Mohammad

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/156559

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/156559