Distributed Computing Group ETH ZurichByzantine Agreement With Interval Validity • October 31st, 2018
Abstract—To solve Byzantine agreement, n nodes with real input values, among which t < n/3 are Byzantine, have to agree on a common consensus value. Previous research has mainly focused on determining a consensus value equal to an input value of some arbitrary node. In this work we instead assume that the values of the nodes are ordered and introduce a novel validity condition which accepts consensus values that are close to the kth smallest value of the correct nodes. We propose a deterministic algorithm that approximates the kth smallest value and show that this approximation is the best possible for the synchronous message passing model. Our approach is furthermore extended to multiple dimensions, where the order is not well-defined, and we show that our algorithm can be applied to determine a value that lies within a box around all correct input vectors.
Darya Melnyk and Roger WattenhoferByzantine Agreement With Interval Validity • November 1st, 2019
