Distributed systems are ubiquitous in modern society. These systems consist of a collection of nodes or computers connected through a network. One of the fundamental requirements of any distributed system is fault tolerance – even if some nodes are faulty or hacked, it should not affect the functioning of the system as a whole. In this talk, we will focus on two aspects of fault tolerance:
(1) Is it possible to design a mechanism which allows different nodes to reach consensus, for example, on a common state of the system or data, even in the presence of faulty nodes?
(2) Can multiple nodes send information reliably over a shared communication medium, even when some nodes do not follow the protocol?
To answer the first question, we focus on realizing a cryptographic primitive called the byzantine broadcast, which ensures consensus among honest nodes in a network with one sender and multiple receivers. We use stochastic resources (like correlated randomness or a noisy channel) to realize this primitive. For the second question, we model the setting using a noisy channel with multiple senders and a single receiver (also called a multiple access channel) where some of the senders may maliciously deviate from the protocol. We study communication in this model while ensuring that malicious senders are not able to cause undetected decoding errors for the honest senders.
