An O(log n) expected rounds randomized byzantine generals protocol
An O(log n) expected rounds randomized byzantine generals protocol
复制标题
O(log n) 预期回合随机拜占庭将军协议
DOI：
--
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
Gabriel Bracha
中科院分区：
文献类型：
--
作者：
Gabriel Bracha
拜占庭将军协议使进程能够在存在故障进程的情况下可靠地广播消息。这些协议运行在一个由<italic>n</italic>进程，<italic>t</italic>进程组成的系统中。协议在消息交换的同步轮中执行。结果表明，在没有窃听、不使用加密的情况下，对于任意ε > 0和<斜体>t</斜体> = <斜体>n</斜体>/(3 + ε)，存在一个期望轮数<斜体>O</斜体>（log <斜体>n</斜体>）的随机化协议。如果允许加密方法，那么，对于ε > 0和<斜体>t</斜体> = <斜体>n</斜体>/(2 + ε)，存在一个随机协议，其期望轮数<斜体>O</斜体>（log <斜体>n</斜体>）。这是对确定性协议所需<斜体>t</斜体> + 1轮数的下界的改进，也是对随机非加密协议的<斜体>t</斜体>/log <斜体>n</斜体>预期轮数的改进。
Byzantine Generals protocols enable processes to broadcast messages reliably in the presence of faulty processes. These protocols are run in a system that consists of <italic>n</italic> processes, <italic>t</italic> of which are faulty. The protocols are conducted in synchronous rounds of message exchange. It is shown that, in the absence of eavesdropping, without using cryptography, for any ε > 0 and <italic>t</italic> = <italic>n</italic>/(3 + ε), there is a randomized protocol with <italic>O</italic>(log <italic>n</italic>) expected number of rounds. If cryptographic methods are allowed, then, for ε > 0 and <italic>t</italic> = <italic>n</italic>/(2 + ε), there is a randomized protocol with <italic>O</italic>(log <italic>n</italic>) expected number of rounds. This is an improvement on the lower bound of <italic>t</italic> + 1 rounds required for deterministic protocols, and on a previous result of <italic>t</italic>/log <italic>n</italic> expected number of rounds for randomized noncryptographic protocols.