부산대학교 도서관

Summary: ``Typically, protocols for Byzantine agreement (BA) aredesigned to run in either a {\it synchronous} network (where allmessages are guaranteed to be delivered within some known time $\Delta$from when they are sent) or an {\it asynchronous} network (wheremessages may be arbitrarily delayed). Protocols designed forsynchronous networks are generally insecure if the network in whichthey run does not ensure synchrony; protocols designed for asynchronousnetworks are (of course) secure in a synchronous setting as well, butin that case tolerate a lower fraction of faults than would have beenpossible 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) todesign a BA protocol that is resilient to (1) $t_s$ corruptions whenrun in a synchronous network and (2) $t_a$ faults even if the networkhappens to be asynchronous. We show matching feasibility andinfeasibility results demonstrating that this is possible if and onlyif $t_a + 2 \cdot t_s < n$.''