Computer Science

Voting in the presence of byzantine faults

Document Type

Conference Paper

Abstract

Voting (or election) algorithms are used widely in many safety-critical systems to mask errors. Most systems only tolerate malicious (or Byzantine) voters - these systems assume the existence of a correct and centralized mechanism to collect the votes and propagate the voting output to each voter. However, in many realistic scenarios, such a centralized voting mechanism is not feasible. Thus, we study the Byzantine voting problem - no centralized mechanism exists in the system, and voters may become Byzantine faulty. We first present impossibility results in both synchronous and asynchronous systems. To circumvent the impossibility results presented in this paper, we propose two relaxed voting properties that are achievable and present optimal voting algorithms that satisfy the relaxed properties. Finally, we show that it is possible to design Byzantine voting algorithms that produce the voting output in one communication step under contention-free scenarios.

Publication Title

Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing, PRDC

Publication Date

2017

First Page

1

Last Page

10

ISSN

1541-0110

ISBN

9781509056514

DOI

10.1109/PRDC.2017.11

Keywords

Byzantine, consensus, distributed algorithms, impossibility results, optimal algorithms, voting

APA Citation

Tseng, L. (2017, January). Voting in the presence of byzantine faults. In 2017 IEEE 22nd Pacific Rim International Symposium on Dependable Computing (PRDC) (pp. 1-10). IEEE.

Link to Full Text

Share

COinS