Byzantine Resilient Computing with the Cloud

We study a framework for modeling distributed network systems assisted by a reliable and powerful cloud service. Our framework aims at capturing hybrid systems based on a point to point message passing network of machines, with the additional capability of being able to access the services of a trusted high-performance external entity (the cloud). We focus on one concrete aspect that was not studied before, namely, ways of utilizing the cloud assistance in order to attain increased resilience against Byzantine behavior of machines in the network. Our network is modeled as a congested clique comprising $k$ machines that are completely connected to form a clique and can communicate with each other by passing small messages. In every execution, up to $\beta k$ machines (for suitable values of $\beta \in [0, 1)$) are allowed to be Byzantine, i.e., behave maliciously including colluding with each other, with the remaining $\gamma k$ or more machines being \emph{honest} (for $\gamma=1-\beta$). Additionally, the machines in our congested clique can access data through a trusted cloud via queries. This externality of the data captures many real-world distributed computing scenarios and provides a natural context for exploring Byzantine resilience for essentially all conceivable problems. Moreover, we are no longer bound by the usual limits of $\beta < 1/3$ or even $\beta < 1/2$ that are typically seen in Byzantine Agreement. We focus on a few fundamental problems. We start with the ${\textsf{Download}}$ problem, wherein the cloud stores $n$ bits and these $n$ bits must be downloaded to all of the $k$ machines. In addition to ${\textsf{Download}}$, we also consider the problem of computing the ${\textsf{Disjunction}}$ and ${\textsf{Parity}}$ of the bits in the cloud. We study these problems under several settings comprising various $\beta$ values and adversarial capabilities.
Comment: 54 pages