Deterministic voting in distributed systems using error-correctingcodes

Distributed voting is an important problem in reliable computing. In an N Modular Redundant (NMR) system, the N computational modules execute identical tasks and they need to periodically vote on their current states. In this paper, we propose a deterministic majority voting algorithm for NMR systems. Our voting algorithm uses error-correcting codes to drastically reduce the average case communication complexity. In particular, we show that the efficiency of our voting algorithm can be improved by choosing the parameters of the error-correcting code to match the probability of the computational faults. For example, consider an NMR system with 31 modules, each with a state of m bits, where each module has an independent computational error probability of 10^-3. 1, this NMR system, our algorithm can reduce the average case communication complexity to approximately 1.0825 m compared with the communication complexity of 31 m of the naive algorithm in which every module broadcasts its local result to all other modules. We have also implemented the voting algorithm over a network of workstations. The experimental performance results match well the theoretical predictions     

A dynamic voting scheme in distributed systems

A dynamic weighted voting scheme for consistency and recovery control of replicated files in distributed systems is presented. The purpose of a replicated file is to improve the availability of a logical file in the presence of site failures and network partitions. The accessible physical copies of a replicated file will be mutually consistent and behave as a single copy. The recovery scheme requires no manual intervention. The control scheme tolerates any number of site failures and network partitions as well as repairs. Correctness results are given     

Verifying anonymity in voting systems using CSP

We present formal definitions of anonymity properties for voting protocols using the process algebra CSP. We analyse a number of anonymity definitions, and give formal definitions for strong and weak anonymity, highlighting the difference between these definitions. We show that the strong anonymity definition is too strong for practical purposes; the weak anonymity definition, however, turns out to be ideal for analysing voting systems. Two case studies are presented to demonstrate the usefulness of the formal definitions: a conventional voting system, and Prêt à Voter, a paper-based, voter-verifiable scheme. In each case, we give a CSP model of the system, and analyse it against our anonymity definitions by specification checks using the Failures-Divergences Refinement (FDR2) model checker. We give a detailed discussion on the results from the analysis, emphasizing the assumptions that we made in our model as well as the challenges in modelling electronic voting systems using CSP.     

基于同态加密策略的电子选举系统

针对电子选举系统的安全性问题,提出了一种基于同态加密策略保护选民隐私的高安全性的电子选举系统设计方案。该系统采用同态加密策略进行选民的投票结果运算,采用非对称密码算法保证数据信息传输过程中的数据安全,保护选民的身份和意愿不被暴露。     

Hack-a-vote: Security issues with electronic voting systems

In a quest for election legitimacy, officials are increasingly deploying direct recording electronic (DRE) voting systems. A project to assess their trustworthiness revealed both the ease of introducing bugs into such systems and the difficulty of detecting them during audits.     

Parameterized computational complexity of control problems in voting systems

Voting systems are common tools in a variety of areas. This paper studies parameterized computational complexity of control of Plurality, Condorcet and Approval voting systems, respectively. The types of controls considered include adding or deleting candidates or voters, under constructive or destructive setting. We obtain the following results: (1) constructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter “number of added candidates”, (2) destructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter “number of added candidates”, (3) constructive control by adding voters in Condorcet voting is W[1]-hard with respect to the parameter “number of added voters”, (4) constructive control by deleting voters in Condorcet voting is W[1]-hard with respect to the parameter “number of deleted voters”, (5) constructive control by adding voters in Approval voting is W[1]-hard with respect to the parameter “number of added voters”, and (6) constructive control by deleting voters in Approval voting is W[2]-hard with respect to the parameter “number of deleted voters”.     

A new dynamic voting algorithm for distributed database systems

We consider the problem of keeping a distributed database system that has been partitioned because of site or communication link failures partially operable while ensuring data consistency. A dynamic-voting-consistency algorithm is proposed, and its correctness is demonstrated. The proposed algorithm results in improved efficiency in executing read requests by not requiring a read quorum. This algorithm is effective in environments where the majority of user requests are “read” types of requests. Furthermore, the proposed algorithm results in efficient recovery by avoiding updating those data objects that are still current. Under the proposed algorithm, the majority partition would be available even if changes in the network topology take place at a higher rate than the update rate, as long as only simple partitioning takes place     

Comparing multiagent systems research in combinatorial auctions and voting

In a combinatorial auction, a set of items is for sale, and agents can bid on subsets of these items. In a voting setting, the agents decide among a set of alternatives by having each agent rank all the alternatives. Many of the key research issues in these two domains are similar. The aim of this paper is to give a convenient side-by-side comparison that will clarify the relation between the domains, and serve as a guide to future research.     

Automated anonymity verification of the ThreeBallot and VAV voting systems

In recent years, a large number of secure voting protocols have been proposed in the literature. Often these protocols contain flaws, but because they are complex protocols, rigorous formal analysis has proven hard to come by. Rivest’s ThreeBallot and Vote/Anti-Vote/Vote (VAV) voting systems are important because they aim to provide security (voter anonymity and voter verifiability) without requiring cryptography. In this paper, we construct CSP models of ThreeBallot and VAV, and use them to produce the first automated formal analysis of their anonymity properties. Along the way, we discover that one of the crucial assumptions under which ThreeBallot and VAV (and many other voting systems) operate—the short ballot assumption—is highly ambiguous in the literature. We give various plausible precise interpretations and discover that in each case, the interpretation either is unrealistically strong or else fails to ensure anonymity. We give a revised version of the short ballot assumption for ThreeBallot and VAV that is realistic but still provides a guarantee of anonymity.     

Electronic voting systems: Requirements,design, and implementation

The term “Electronic Voting (e-voting)” refers to the use of computers or computerized equipment to cast votes in an election. e-voting aims at increasing participation, lowering the costs of running elections and improving the accuracy of the results. This paper details the requirements, design and implementation of a special type of electronic voting systems, the remote on-line voting system, suitable for university setting where students can cast their votes anytime, anywhere and using fixed and mobile electronic devices including personal computers, personal digital assistants and smart and regular phones. To avoid web content replication for each of the connecting devices, the implemented system separates the data content from its presentation form. The separation is achieved by using modern technologies such as the extensible markup language to represent the web data content and the extensible style language transformation style sheets to customize the presentation of such content on different connecting devices, thus, achieving true “author once, publish to any device” design and implementation.     

Capacity expansion of linked reservoir systems

A procedure is presented for the analysis of time phasing of reservoir system development. The formulation is based on a multi-purpose reservoir model with stochastic inflows. The object is to select the reservoir sizing, timing of expansion and to establish operating policies such that the total cost associated with the system of linked reservoirs is minimized. The capacity expansion aspect is formulated as a mixed integer continuous linear programming problem. Due to the resulting problem size and its general structure, Benders' decomposition is applied. A numerical example illustrating the procedure is given.     

Manipulation can be hard in tractable voting systems even for constant-sized coalitions

Voting theory has become increasingly integrated with computational social choice and multiagent systems. Computational complexity has been extensively used as a shield against manipulation of voting systems, however for several voting schemes this complexity may cause calculating the winner to be computationally difficult. Of the many voting systems that have been studied with regard to election manipulation, a few have been found to have an unweighted coalitional manipulation problem that is NP-hard for a constant number of manipulators despite having a winner problem that is in P. We survey this interesting class of voting systems and the work that has analyzed their complexity.     

Privacy and verifiability in voting systems: Methods,developments and trends

One of the most challenging aspects in computer-supported voting is to combine the apparently conflicting requirements of privacy and verifiability. On the one hand, privacy requires that a vote cannot be traced back from the result to a voter, while on the other hand, verifiability states that a voter can trace the effect of her vote on the result. This can be addressed using various privacy-enabling cryptographic primitives which also offer verifiability.As more and more refined voting systems were proposed, understanding of first privacy and later verifiability in voting increased, and notions of privacy as well as notions of verifiability in voting became increasingly more refined. This has culminated in a variety of verifiable systems that use cryptographic primitives to ensure specific kinds of privacy. However, the corresponding privacy and verifiability claims are not often verified independently. When they are investigated, claims have been invalidated sufficiently often to warrant a cautious approach to them.The multitude of notions, primitives and proposed solutions that claim to achieve both privacy and verifiability form an interesting but complex landscape. The purpose of this paper is to survey this landscape by providing an overview of the methods, developments and current trends regarding privacy and verifiability in voting systems.     

Hierarchical voting

Quasilocal voting operators considered in this paper are intended to transform the sets of voters' opinions given in the form of individual binary relations into collective binary relations. Three classes of such operators are analyzed: those specified by characteristic conditions, those satisfying structural constraints on the initial and resulting binary relations, and those presented in an explicit form. The results obtained generalize well-known results on the Arrow paradox.     

The method of bearing systems “picture construction” using the voting method

This paper is occupied with the problem of bearing-constructions structure generation using a computer. The input is the requirement from a functional viewpoint and partly with respect to the strength state. The approach is based on methods of “pattern recognition” and uses the voting method     

Multivalued logic voting scheme for residual evaluation in failure detection and isolation systems

This paper deals with Failure Detection and Isolation procedures using the generalized Parity Space Approach. The decision scheme uses the structural properties of the residuals and leads to the analysis of fault events signatures. In a classical approach, these signatures are binary words. We propose a multivalued voting scheme, which allows to follow some specifications connected with false alarms and miss-isolation. The performances of the proposed approach are compared with these of the classical one using two examples.     

Remote electronic voting systems: an exploration of voters' perceptions and intention to use

Coupling telephone and web interfaces with computers for balloting outside the polling place, remote electronic voting systems (REVS) give the voter a choice: polling booth, absentee ballot, or remote voting. Not only does this e-Government technology raises issues such as security, voter participation, and accessibility, REVS technologies themselves differ in features and enabling conditions. How users (voters) perceive REVS's availability, mobility, accuracy, privacy protection, and ease of use, is likely to affect their use intention. Intention to use or not to use a voting technology can translate into a decision to vote or not – and there are no ‘do-overs’. We develop a model and report on a survey of potential voters – people waiting to be impaneled on a jury – in regard to the impact of REVS characteristics on voting intentions and how the two most discussed REVS technologies of telephone- and web-based interfaces are perceived.     

On multilevel voting

Summary In a distributed system mutual exclusion is often used to maintain consistency when restricted operations are performed. Mechanisms guaranteeing mutual exclusions should be both resilient and efficient. Resiliency implies high resource availability in the face of failures, while efficiency implies low overhead incurred by performing restricted operations. In this paper, we propose and study a general paradigm, called multilevel voting, which provides a general framework to assist in the design of resilient and efficient mutual exclusion mechanisms. The proposed method uses multiple level quorum consensus. Unlike another method based on the use of multiple quorum consensus, the proposed model only contains one type of integrity constraints. This has the benefit of being conceptually simple and easy to reason about. The strong resemblance with the traditional quorum consensus makes it easy for the proposed paradigm to embed any technique based on traditional quorum schemes. We show that the proposed model represents the exact class of coteries. This means that not only does it have all the power of coteries, but also all schemes under the model are correct. Thus, should the need arise, we can interchange two schemes freely without using any extra mechanisms to ensure correctness. We study a number of issues that have impact on performance such as the degree of a multilevel scheme and the order of a coterie. We explain how the model can be extended also to model the schemes for the synchronization of read and write of replicated data. We provide algorithms for the design of multilevel schemes in the context of mutual exclusion and that of read and write of replicated data. J. Tang received the M.S. degree in computer science from the University of Iowa in 1983 and the Ph.D degree in computer science from the Pennsylvania State University in 1988. Since 1988, he has been an assistant professor with the Department of Computer Science, Memorial University of Newfoundland, St. John's, Newfoundland, Canada. His current research interests include distributed computing, fault tolerance in distributed systems, database modeling and multidatabase systems.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada, individual operating grant OGP0041916