Decentralized systems can be more resistant to operator mischief than centralized ones, but they are substantially harder to develop, deploy, and maintain. This cost is dramatically reduced if the decentralized part of the system can be made highly generic, and thus incorporated into many different applications. We show how existing anonymization systems can serve this purpose, securing a public database against equivocation by its operator without the need for cooperation by the database owner. We derive bounds on the probability of successful equivocation, and in doing so, we demonstrate that anonymization systems are not only important for user privacy, but that by providing privacy to machines they have a wider value within the internet infrastructure
The problem of obtaining agreement on a value amongst several---possibly malicious---users is an old one, known as the Byzantine Generals problem, and was first analyzed by Lamport in 1982 @cite_0 . Several officers plan for an attack, in which they must act simultaneously in order to be successful. This is complicated by the knowledge that some of the officers may be traitors---including the general in command of all of them---and may therefore send different messages to different units in an effort to induce a doomed attack.
@cite_0
1991153938 2120510885 1980514553 2091004544
We present a randomized solution for the Byzantine Generals Problems. The solution works in the synchronous as well as the asynchronous case and produces Byzantine Agreement within a fixed small expected number of computational rounds, independent of the number n of processes and the bound t on the number of faulty processes. The solution uses A. Shamir's method for sharing secrets. It specializes to produce a simple solution for the Distributed Commit problem. Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system. This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement. It is shown that, using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals. With unforgeable written messages, the problem is solvable for any number of generals and possible traitors. Applications of the solutions to reliable computer systems are then discussed. In this paper we study the problem of achieving Byzantine agreement among a set of processors, where the processors are computationally sound but their interfaces with the communication channels may be faulty. We consider three types of fault, namely message corruption, message loss, and spurious message generation. We present the following results for this model: (i) If all three types of faults are present then the problem is equivalent to the classical Byzantine generals problem. (ii) In the cases where only message corruption can occur, agreement becomes trivial and can be achieved in one round. (iii) If spurious message generation is ruled out, that is, when interfaces may fault only when sensitized, agreement is possible irrespective of the ratio of the number of processors having faulty interfaces with the total number of processors. By analyzing the states of knowledge that the processors attain in an unreliable system of a simple type, we capture some of the basic underlying structure of such systems. In particular, we study what facts become common knowledge at various points in the execution of protocols in an unreliable system. This characterizes the simultaneous actions that can be carried out in such systems. For example, we obtain a complete characterization of the number of rounds required to reach simultaneous Byzantine agreement, given the pattern in which failures occur. From this we derive a new protocol for this problem that is optimal in all runs, rather than just always matching the worst-case lower bound. In some cases this protocol attains simultaneous Byzantine agreement in as few as two rounds. We also present a nontrivial simultaneous agreement problem called bivalent agreement for which there is a protocol that always halts in two rounds. Our analysis applies to simultaneous actions in general, and not just to Byzantine agreement. The lower bound proofs presented here generalize and simplify the previously known proofs.