Publication
Distributed systems, which enable the efficient processing of large-scale data and complex tasks across multiple interconnected processes, offer significant advantages over single-machine systems. These include enhanced scalability, improved fault tolerance, and the effective utilization of geographically distributed resources. A fundamental challenge in such systems lies in achieving coordination among unsynchronized processes that often operate over unreliable networks and must tolerate various types of failures. Achieving consensus -- agreement on a shared state or decision across processes -- is central to overcoming this challenge but remains a highly non-trivial problem. Consensus mechanisms underpin critical (distributed) services such as distributed key generation (DKG), secure multi-party computation (MPC), blockchain technologies, and state machine replication (SMR), emphasizing their indispensable role in modern computing.
Despite their significance, existing consensus protocols face notable limitations. Many struggle to scale efficiently due to poor performance or over-reliance on cryptographic tools such as threshold signatures, which demand costly setup and computationally intensive algebraic operations. Furthermore, reliance on these ``heavyweight'' cryptographic primitives compromises their security in a post-quantum world. As distributed systems continue to grow in scale and importance, there is a pressing need for consensus solutions that are not only efficient but also resilient to emerging security threats and future technological advancements.
This thesis addresses these challenges by revisiting two fundamental problems in distributed computing -- \emph{graded consensus} and \emph{Byzantine agreement}.
We present the first complexity-optimal protocols for these problems that either leverage only lightweight'' cryptographic primitives, such as hash functions, or entirely eliminate the reliance on cryptography. Our solutions span all major network models -- \emph{asynchrony}, \emph{partial synchrony}, and \emph{synchrony}. By introducing algorithms that match or exceed the best known solutions, all while relying on little'' cryptography, this thesis advances the state of the art in consensus protocols and lays the foundation for more efficient and future-proof distributed systems capable of meeting the evolving demands of modern computing.