Bee's Strategy Against Byzantines Replacing Byzantine Participants (Extended Abstract)

摘要

Schemes for the identification and replacement of two-faced Byzantine processes are presented. The detection is based on the comparison of the (blackbox) decision result of a Byzantine consensus on input consisting of the inputs of each of the processes, in a system containing n processes p_1,..., p_n. Process p_i that received a gossiped message from p_j with the input of another process p_k, that differs from p_k's input value as received from p_k by p_i, reports on p_k and p_j being two-faced. If enough processes (where enough means at least t + 1, t < n is a threshold on the number of Byzantine participants) report on the same participant p_j to be two-faced, participant p_j is replaced. If less than the required t + 1 processes threshold report on a participant p_j, both the reporting processes and the reported process are replaced. If one of them is not Byzantine, its replacement is the price to pay to cope with the uncertainty created by Byzantine processes. The scheme ensures that any two-faced Byzantine participant that prevents fast termination is eliminated and replaced. Such replacement may serve as a preparation for the next invocations of Byzantine agreement possibly used to implement a replicated state machine.