Narrow Results

Diagnosing the quality of components in fault-tolerant computer systems often requires numerous tests with limited resources. It is usually the case that repeated tests on a selected, limited number of components are performed and the results are taken into account so as to infer a diagnostic property of the computer system as a whole. In this paper we abstract fault-tolerant testing as the following problem concerning the color of the majority in a set of colored balls. Given a set of balls each colored with one of two colors, the majority problem is to determine whether or not there is a majority in one of the two colors. In case there is such a majority, the aim is to output a ball of the majority color, otherwise to declare that there is no majority. We propose algorithms for solving the majority problem by repeatedly testing only k-tuple queries. Namely, successive answers of an oracle (which accepts as input only k-tuples) to a sequence of k-tuple queries are assembled so as to determine whether or not the majority problem has a solution. An issue is to design an algorithm which minimizes the number of k-tuple queries needed in order to solve the majority problem on any possible input of n balls. In this paper we consider three querying models: Output, Counting, and General, reflecting the amount and type of information provided by the oracle on each test for a k-tuple.

We study the behavior of the number of votes cast for different electoral subjects in majority elections, and in particular, the Albanian elections of the last 10 years, as well as the British, Russian, and Canadian elections. We report the frequency of obtaining a certain percentage (fraction) of votes versus this fraction for the parliamentary elections. In the distribution of votes cast in majority elections we identify two regimes. In the low percentiles we see a power law distribution, with exponent about -1.7. In the power law regime we find over 80% of the data points, while they relate to 20% of the votes cast. Votes of the small electoral subjects are found in this regime. The other regime includes percentiles above 20%, and has Gaussian distribution. It corresponds to large electoral subjects. A similar pattern is observed in other first past the post (FPP) elections, such as British and Canadian, but here the Gaussian is reduced to an exponential. Finally we show that this distribution can not be reproduced by a modified "word of mouth" model of opinion formation. This behavior can be reproduced by a model that comprises different number of zealots, as well as different campaign strengths for different electoral subjects, in presence of preferential attachment of voters to candidates.

We compare different actual forms of democracy and analyse in which way they are variations of a “natural consensus decision process”. We analyse how a “pure consensus procedure” is open to boycott of a minority, and how a “consensus decision followed by majority voting” is open to “false play” by a majority. We introduce a “random consensus procedure” in order to come closer to a natural decision process, and investigate how for such decision procedure false play of a minority is plausible to happen. We introduce the combined notion of “quantum parliament” and “quantum decision procedure”, and prove it to be the only one, when applied after consensus decision, that is immune to false play. We define a new form of democracy applying a quantum consensus system for its decision procedures.