An introduction to Devotee and Condorcet voting
Debian uses a fairly elaborate, complex voting mechanism based on a
variant (Clone-proof Schwartz Sequential Dropping, or Beat-path
Winner, or the Schulze method) of the Condorcet method. Actually,
Debian adds a couple of twists to a pure Condorcet, as detailed in
This talk shall give an historical overview on how the Debian
voting mechanism evolved, from a monolithic, fragile mail post
processor to the current mechanism, and shall talk about the future
plans for the system to make it more useful to entities that are
not the Debian project itself.
The Condorcet method generates more confusion than anything else in
the Debian voting mechanism, a number voters expressing their
inability to predict how their ballot would affect the
outcome. There shall be an explanation of the system in layman's
terms, along with examples and graphs of various example votes.
Next, the paper shall explain the current design, along with its
UNIX like philosophy of decomposing the problem into various parts,
each addressed by a separate program that does one thing. It shall
explain the various phases of the voting process, and the various
subsystems that implement it. It also shall explain the design
goals whci were involved in creating the current implementation
(including the overriding requirements or idempotency,
reproducibility, and non-repudiability, privacy, and over all, that
there should never be any data loss).
The first phase is part of the communications subsystem, and is the
only asynchronous part of the mechanism; this is the phase in which
ballots, or ballot requests are received, and routed to the proper
vote (or the proper ballot(s) are returned). Since this phase is
asynchronous, great care is taken with locking to ensure that there
are no collisions or races.
The next phase is the mail handling and decryption subsystem, which
is responsible for dealing with mime, and calling the encryption
subsystem to decrypt encrypted ballots.
The next subsystem is the ballot checking subsystem, and has
several components; one from the encryption subsystem which
performs gpg signature checks using the official key-rings, another
that does the checks against the Debian LDAP directory. This
subsystem is the one that is in greatest need of enhancement and
should really be far more flexible, and that is addressed later in
the paper. Finally, the ballot is checked, and tallied.
The results and statistics system is responsible for actually
determining the winner, and generating various graphs of incoming
statistics during the voting period.
The communications subsystem is also responsible for communicating
acknowledgements or error messages to the voters, including the
obscuring mechanisms required for publishing a tally sheet in a
The problem with the current implementation is that this it is
fairly rigidly tailored to Debian's requirements; the quorum and
majority requirements should be optional checks in the checks
subsystem, as well as the gpg or the ldap checks. Really, we need a
plugin mechanism to add more checks, and to optionally perform the
check (or not) on a vote by vote basis.
A more generalized concept is to treat the whole vote engine as a
work flow platform, with a ballot entering the system with various
requirements (defaulting to a set based on the vote configuration,
or determined during processing). The best pattern for this seems
to be the blackboard pattern; a ballot shall come in with a base
set of processing requirements, and there shall be a number of
processing elements that provide processing. For example, there
shall be a mime examination plugin that determines whether the
ballot is in mime (add mime processing requirement, whether it is
encrypted, or signed -- add proper processing needs from
encryption). Processing steps can have dependencies, for example,
once cannot tally a vote unless the ballot has been decrypted. Each
processing element then scans the blackboard for tasks that can be
done (and which are not blocked by unmet prerequisites).
The advantage is that the system can be made flexible enough to
meet the needs of various constituencies whose processing
requirements are not identical to those of the Debian project.
Why am I the one best suited to give this task? Well, I am the
author of Devotee (DEbian VOTe Engine), and I have conducted more
votes for the project than anyone else has, and I am the only one
actively working on Devotee.