Distributed Computing with Imperfect Randomness

摘要: Randomness is a critical resource in many computational scenarios, enabling solutions where deterministic ones are elusive or even provably impossible. However, the randomized to these tasks assume access source of unbiased, independent coins. Physical sources randomness, on other hand, rarely unbiased and although they do seem exhibit somewhat imperfect randomness. This gap modeling questions relevance current tasks. Indeed, there has been substantial investigation this issue complexity theory context applications efficient algorithms cryptography. In paper, we seek determine whether modeled appropriately, “good enough” for distributed algorithms. Namely can with randomness all that perfect comparable efficiency ? We answer question affirmative, problem Byzantine agreement. construct protocols agreement variety scenarios (synchronous asynchronous networks, without private channels), which players have Our essentially as best known protocols, despite defects