VOTING MECHANISMS IN ASYNCHRONOUS BYZANTINE ENVIRONMENTS
Abstract
A source sends a piece of data (message), relayed to a receiver by n processes, some of which can be faulty. We assume that the number of faulty processes is at most f and that faulty processes exhibit a Byzantine behavior. A deciding agent has to make a decision concerning the source message, on the basis of results obtained from the receiver. The environment is totally asynchronous. An Asynchronous Byzantine Voting Mechanism is a method that enables the deciding agent to always correctly determine the source message in this scenario.
We show that there exists a correct Asynchronous Byzantine Voting Mechanism if and only if f < n/3. If this condition is satisfied, we provide such a mechanism. This result should be contrasted with the feasibility of synchronous voting mechansisms, in which the receiver can wait until all fault-free processes convey their values: for this scenario a correct voting mechanism exists whenever f < n/2.
Research partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais.
References
F. Bao , Y. Igarashi and K. Katano , Broadcasting in hypercubes with randomly distributed Byzantine faults, Proc. WDAG'95,LNCS 972 (1995) pp. 215–229. Google Scholar- ACM Transactions on Computer Systems 4, 187 (1986), DOI: 10.1145/6420.6421. Crossref, ISI, Google Scholar
- IEEE Transactions on Computers 36, 1197 (1987). ISI, Google Scholar
- Journal of Algorithms 22, 199 (1997), DOI: 10.1006/jagm.1996.0810. Crossref, ISI, Google Scholar
D. Blough and G. Sullivan , A comparison of voting strategies for fault-tolerant distributed systems, Proc. 9th Symposium on Reliable Distributed Systems (1990) pp. 136–143. Google Scholar- IEEE Trans. on Reliability 43, 604 (1994), DOI: 10.1109/24.370219. Crossref, ISI, Google Scholar
- Information Processing Letters 51, 1 (1994), DOI: 10.1016/0020-0190(94)00064-6. Crossref, ISI, Google Scholar
- Journal of Algorithms 3, 14 (1982). Crossref, ISI, Google Scholar
- Journal of the ACM 32, 841 (1985), DOI: 10.1145/4221.4223. Crossref, ISI, Google Scholar
- IEEE Transactions on Computers 42, 553 (1993), DOI: 10.1109/12.223674. Crossref, ISI, Google Scholar
M. Paquette and A. Pelc , Optimal decision strategies in Byzantine environments, Proc. 11th Colloquium on Structural Information and Communication Complexity (SIROCCO'2004),LNCS 3104 (2004) pp. 245–254. Google Scholar- IEEE Transactions on Electron. Computers 16, 848 (1967). ISI, Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 5, 64 (1994), DOI: 10.1109/71.262589. Crossref, ISI, Google Scholar


