Median Validity in Asynchronous Approximate Agreement

Speaker: Akhil Bandarupalli. Akhil is a PhD student at Purdue University, being advised by Aniket Kate.

Title: Median Validity in Asynchronous Approximate Agreement

Abstract:

Median validity is a validity property in Byzantine agreement where the protocol's output validity is measured by the output's relative distance to the median of honest inputs. Byzantine Agreement protocols with this validity property are essential in sensor networks where sensors wish to agree on a reading close to the ground truth reading. Median validity is also finding increasing usage in blockchain oracles, where data from the outside world is fed into the blockchain. Stolz et al. [1] showed that in an n=3t+1 system, it is impossible for a BA algorithm to achieve anything higher than 0-validity. In this work, we explore median validity in asynchronous approximate consensus. We work with this impossibility result and force the adversary to choose between low output validity and high round complexity. We develop an Approximate Agreement protocol called \textit{Cleffa} where the adversary must choose between low validity and high runtime. Given that the adversary wants to keep the validity of agreement below $c$ with probability $p = 1-\frac{1}{2^{\kappa}}$, Cleffa achieves $\epsilon$-agreement in expected rounds $r = log_2(\frac{\Delta}{\epsilon}) + log_2(c^{\frac{1}{\kappa}}(1-c^{\frac{1}{\kappa}}))$ rounds." 

[1] Stolz, David, and Roger Wattenhofer. "Byzantine agreement with median validity." In 19th International Conference on Principles of Distributed Systems (OPODIS 2015), vol. 46, p. 22. Schloss Dagstuhl–Leibniz-Zentrum für Informatik GmbH, 2016.

Location: LWSN 1106 and Zoom (https://purdue-edu.zoom.us/j/91817312903?pwd=NFNKeHoyZlV2aVp3ZUdwRzRHR3Fhdz09)