부산대학교 도서관

Summary: ``Typically, protocols for Byzantine agreement (BA) are designed to run in either a {\it synchronous} network (where all messages are guaranteed to be delivered within some known time $\Delta$ from when they are sent) or an {\it asynchronous} network (where messages may be arbitrarily delayed). Protocols designed for synchronous networks are generally insecure if the network in which they run does not ensure synchrony; protocols designed for asynchronous networks are (of course) secure in a synchronous setting as well, but in that case tolerate a lower fraction of faults than would have been possible if synchrony had been assumed from the start. \par ``Fix some number of parties $n$, and $0 < t_a < n/3 \leq t_s < n/2$. We ask whether it is possible (given a public-key infrastructure) to design a BA protocol that is resilient to (1) $t_s$ corruptions when run in a synchronous network and (2) $t_a$ faults even if the network happens to be asynchronous. We show matching feasibility and infeasibility results demonstrating that this is possible if and only if $t_a + 2 \cdot t_s < n$.''