The Clerk/eVote(R)  A Specialized Database Server

by Marilyn Davis Ph.D.
Software Author
Deliberate.Com

The idea of a specialized database server came to me around 1990
when I was struggling with a relational DBMS, making software for big
warehouses and distribution centers. I realized that the warehouse
application has only a few types of data and that if we saved them to
disk ourselves, we could avoid the layer of code in our software that
maps our data to the generalized format, and back again.

This was one of those ideas that kept re-exploding as I realized that
saving data in its natural format would allow dynamic rearrangement of
the data, and automatic schema evolution by users, tasks
considered impossible at that time. I also realized that, by keeping
the data special to their purpose, the natural language of the
application could be carried throughout the code, never reverting to
generalized records. This would be an aid when dealing with the
complexities involved in providing the dynamic features.

An outspoken advocate for Electronic Democracy since the 1986
Presidential elections, this new idea translated itself, in my mind,
into the answer: a specialized database server for keeping
votes, combined with a conferencing system, would create a medium for
a perfectly non-hierarchical ideal democracy. The work of administering 
the voting system would be shared by the users and the software; the 
human administrator would effectively be obsolesced.

When the correct architecture for the problem came to me, I could no
longer just advocate Electronic Democracy;  I built it.

As expected, the specialized vote-server, The Clerk, written in
C++, provides all imaginable features for voters: anyone can initiate
a poll; users can change their votes as long as the poll is open;
polls can be public allowing all the participants to view each
others' votes, private, or if-voted, allowing us to know
who voted, but not how they voted. Several poll types are
supported: yes/no, numeric, and grouped. The
software is easily enhanced to add new features and poll types by
extending the existing classes. As expected, The Clerk maintains the
data on the fly, requiring no help from the administrator. True to
the promise of object-oriented architecture, the addition of each new
feature has made the code more robust.

The Architecture

At the very center of The Clerk are the three classes:
Ballot, Voter, and Item: a tertiary
relationship. Each Item object represents a poll item
in the conferencing system. When a voter object votes, it
retrieves its ballot and passes it to the the appropriate
item object. The item knows which bits of the
ballot are for storing the vote for itself. It marks the
ballot and adjusts its statistics.

---

Fig. 1. Central Classes of The Clerk

---

The Item classes are in a hierarchy, facilitating the
addition of Condorcet, Borda, and any statistical algorithms. The
process is to add another subclass and string the facility through to
the user-interface. The current hierarchy is shown in Fig 2. The
sidebar on Poll Types lists the possible poll types this
hierarchy provides in the user-interface.

---

Fig. 2 ItemList Class and the Item Hierarchy.

---

The ItemList provides the dynamic schema for mapping the
items onto the ballot, also shown in Fig 2. It
coordinates with the BallotBox to delete data that is no
longer needed. This is a grooming task that takes place when
the system is idle. Other grooming tasks will appear as we discuss
other classes.

The Ballots

The ballots are dynamic. When an poll is closed and then
dropped from the conference, and when the software is otherwise idle,
the ballots are collapsed, rolling the storage bytes for
other items toward the top, and making space for new polls. The
item objects recalculate their new places in the
ballots, and everything is set to continue.

The ballot's header has a voter id (explained next), a
last_time_accessed date stamp, and a 2-byte action field.
Into the action field is recorded whether or not the participant has
voting privileges, is a mail or telnet client, is on vacation, or has
left the conference. A voter will remain in the data even after she
has left the conference if she has authored a poll that is still
active. 2-bytes of the header are empty.

Ballots can grow to accommodate any number of poll
items. The software doubles the ballot size when the number
of unused bytes gets low. This, again, is a grooming task and takes
place when the system is otherwise idle.

The Voter ID

Each ballot has a header that contains an unsigned long id to
identify the voter. Because an unsigned long can hold numbers up to
about 4 billion, this is a natural hint that we should limit our
population at 4 billion.

Currently there are two main eVote user interfaces: a telnet client,
and a mail client. The voter's id, in the telnet interface, is the
Unix user id. 

To facilitate the email interface there is, within The Clerk, a single
instance of a WhoList class that assigns an id to each email
address in the online community. The WhoList also keeps a
count of the number of conferences that the address is subscribed to.

The WhoList's records are variable length, kept in alphabetic
order on the email address. It is hashed for quick retrieval of the
numeric id. It keeps an array of offsets into the data file, one for
each id, to provide quick retrieval of the email address.

Container Classes

Each of the three central classes, Voter, Item, and
Ballot, has its container class: VoterList,
ItemList, and BallotBox. These container classes
are components of the Conference class, shown in Fig. 1.

The BallotBox is responsible for keeping the ballots
compact and in order for fast retrieval. They are stored in hashed
blocks with a special block at the end of the data file for the most
recent additions. When a new voter joins a conference, the new
ballot is sorted into that last block, the new voters'
block. Later, when the system is otherwise idle, the blocks are
groomed. The ballots in the new-voters' block are ordered
into the older ballots, the inactive ballots are
dropped, and the hash table is reset.

The ballots are collapsed to regain the space taken by
finished poll items through a coordination between the
ItemList and the BallotBox. The BallotBox
requests a list of dead bytes from the ItemList. It
uses this list to collapse the ballots and then instructs the
ItemList to remove the dead items from its list.

All this ordering goes on when The Clerk decides it's not busy with
online users, when the grooming tightens up everything for speed and
space.

If the system becomes very busy, and grooming becomes an emergency,
grooming happens, busy or not.

The Clerk's Communication with the Voter

The Clerk's main() function is an infinite loop (one hopes)
that watches for incoming messages on the Inter-Process
Communication messaging facility from eVote(R) clients, i.e. user
interface processes with live voting users. The Clerk has one
permanent message queue for incoming requests from users. It is
managed by the single instance of the InQ class. Each eVote
process has a temporary message queue of its own for receiving
messages back from The Clerk. These are objects of the OutQ
class.

---


Fig. 3.  The Clerk's Message Queue System

---

Although there is exactly one incoming message queue for The Clerk,
there can be multiple Clerks running simultaneously on one machine,
working different data sets and different queue id's.

Many of the incoming messages from eVote clients correspond to the
function calls that are defined in The Clerk's library. These are:
ADJOURN_CONF, CHECK_CONF, CREATE_CONF,
CREATE_ITEMS,  DROP_CONF, DROP_ITEMS,
DROP_VOTER, ENTERING (used when a voter enters a
conference), HELLO (the initial handshake to check that The
Clerk is running), HOW_VOTED (to report the vote of other
voters when the poll type allows it), I_READ,
I_VOTE, JOINING (for entering a conference for the
first time), LEAVING, MOVE (for changing the email
address of a participant in the mail interface), SEND_STATS,
WHO_SIGNED, WHO_VOTED, WHOS_IN. Some
messages are for maintenance or helping to complete a command:
CHANGE_ACTION, CHANGE_VSTATUS, DO_DEBUG,
DOWN_PRIORITY, DROP_OLDQS, ENTER_ADMIN,
EXIST_CONF, FLUSH_LOG, GET_UNIQUEID,
GROW_CONF, LEAVE_ADMIN, MID_DROPPED,
NEW_EXE, NEW_LOG, PULL_STAMP,
PUSH_STAMP, QUIT, REORDER_CONF,
SEND_STAMP, SYNC_CONF, UID_EXIST,
UP_PRIORITY, WHO_DROP, WHO_IS,
WHO_NUM, WHO_SYNC.

When the InQ object receives a message, it instantiates a
corresponding object from the Instruction hierarchy of classes.

---

Fig 4. The Instruction hierarchy of classes

---

Virtual classes are NeedsQ, HasQ, MaybeQ,
and RespondOnce, which inherits from NeedsQ. These
are not directly instantiated but handle the tasks associated with
maintaining the outgoing message queues which are instances of the
OutQ class. The AboutItem class is also never
instantiated; it inherits from HasQ.

The Instruction classes that are instantiated are in
one-to-one correspondence with the incoming message types. The
deliver function of the InQ object, i.e., The Clerk's
incoming message queue manager, has a big switch over the message type
to construct the matching Instruction object. It constructs
the instruction and immediately deletes it. In the
Instruction classes, the constructors contain the calls to
complete the request from the client.

For example, Listing 1. is the constructor for the
CreateItems class. An object of this class is created and
destroyed when a participant generates a new poll question, or set of
questions.


Listing 1.


CreateItems::CreateItems(char *input, int pid, ITYPE itype, int len)
  :HasQ(input, pid, itype)
{
  int no_items;
  
  switch(p_voter->p_conf()->create_items(input, len,
                                         uid, &no_items))
    {		
    case OK:
      qlist.send(NEW_STAT, qid, sizeof(ITEM_STAT)*no_items);
      break;
    case NOT_OK:   // item id is already there  
      qlist.send(REDUNDANT, qid, 1);
      break;
    case PROBLEM:  // no system resources
      qlist.send(NO_ITEM, qid, 1);
      break;
    case UNDECIDED:// not finished creating the last item group
	           // try again soon
      qlist.send(RESEND, qid, 1);
      break;
    }
}		



The input variable holds the actual message which is passed
on to the conference object whose itemlist does the
actual work of creating the new item(s) and claiming space in
the ballots.

Shared Memory

While the statistics about polls, and the personal information
requested by a voter, are communicated via the OutQ objects,
a another interprocess communication facility, shared memory, is
used for slow-moving data. The list of poll items and their
properties (public, private, or if_voted, where
users can see if another voter has voted, but not how he
voted; yes/no or numeric; visible or hidden,
where the statistics are available only after the poll is closed;
single or grouped; and the title) are stored in shared
memory so that all the eVote clients that are currently active in the
same conference can see them.

The conference's itemlist object is responsible for
maintaining the shared memory. When a new poll is created for a
conference, if the growing list of poll items requires a new
patch of shared memory, a message is sent to all active eVote clients.
This dynamic notification feature enables the voters to conduct their
meeting in real time.

User Interfaces

At this time, The Clerk has two user interfaces and invites more.

The Clerk's first user interface is a simple text-based telnet
interface, designed with conferencing systems and BBS's in mind.

The explosion of the internet dampened enthusiasm for conferencing
systems. Email arose as the dominant form of communication, and email
lists became the community discussion medium. So the email user
interface was built to allow the email communities to make formal
decisions. Although this interface has proven itself to be useful,
it does not take advantage of the real-time facility of The Clerk.


The Email Interface -- A Complete Example

Three Levels of Participation

eVote's email list interface provides three levels of participation:

1. Voter -- any user can vote, change their vote, and has the
same power to query the data as does the administrator of the poll and
the list's owner.

2. User/administrator -- any user can initiate a poll. Under
ordinary circumstances, only the user who starts a poll can close or
drop it from the data.

3. List owner -- Some commands are password protected. These
provide over-riding powers so that the owner can close/drop any poll,
change the voting privileges, or move a participant's ballot
to a new email address. The list's owner also retains the same
responsibilities and powers as owners of lists without eVote.


Five Executables

As shown in Fig 5, the overall architecture of the email facility has
five executables.

---

Fig. 5. eVote's mail interface

eVote(R) is five programs that work together: eVote_Clerk, The
Clerk; eVote_insert, the email list user interface;
eVote_mail, the mail administrator's utility interface;
eVote_petition, the interface for signers of petitions; and
eVote, the command center for controlling The Clerk.



                       _______________
                      |               |
                      |  eVote_Clerk  |
                      |    -------    |
                      |      The      |
                      |     Clerk     |
                      |_______________|
                      /|\ /|\  /|\  /|\
                       |   |    |     |
                       |   |    |     |
                   STARTS  |    |   COMMUNICATES WITH
                   /       |    |                |
                 /         |    |                |
               /           |    |               \|/
 _______________           |    |             _________________
|               |          |    |            |                 |
|     eVote     |          |    |            |  eVote_insert   |----> Runs
|   ---------   |          |    |            |     -------     |  resend
|    Command    |          |    |            |  The email list |   or your
|     center    |          |    |            |    interface    |   mailer,
|_______________|          |    |            |_________________|        as
                     COMMUNICATES WITH            /|\          appropriate.
                           |     \                 |              /|\
                           |       \            wrapper, part|    
                           |         \          of Majordomo, runs |
                          \|/          \        eVote_insert &     |
               _______________________   \      eVote_petition     |
              |                       |    \       |               |
              |       eVote_mail      |      \|   \|/              |
              |  -------------------  |       _______________________
              |  Mail administrator's |      |                       |
              |  utility Interface    |      |     eVote_petition    |
              |_______________________|      |  -------------------  |
                                             |  Accepts signatures   |
                                             |  for petitions only. |
                                             |  Also an email        |
                                             |  interface.          |
                                             |_______________________|



eVote_insert

The Email Interface coordinates with Majordomo, the popular open
source email list server. Majordomo provides the discussion medium;
eVote provides the voting facility. This cooperation is configured in
the alias file of the Mail Transfer Agent (Exim, Qmail, ...) so
other list servers can be substituted with minimal effort.  See the
Sidebar on How eVote(R)/Clerk Integrates With Majordomo for details.

eVote_petition

There are two facilities in eVote's email interface: polling in email
lists; and petition support. The petition facility allows
participation from anyone while the email list facility only allows
addresses on the email list to participate. 

Petitions are administered collaboratively by members of a
petition list, which is any list whose name starts with the word
petition: petitiona, petitionb, etc. Polls initiated
in petition lists have the option of being open to non-members.

The eVote_mail Executable

eVote_mail allows the site administrator to synchronize The Clerk's
list of subscribers to Majordomo's list. The site administrator can
use this program to disallow voting from an address; or to drop an
address from all lists. Also, this program can be instructed to clean
Majordomo's list of old bad addresses. Similarly, this program will
delete stale messages that have been awaiting confirmation.

The eVote Executable

The eVote executable is the command center for eVote. It can be
called with various arguments. Depending on the argument, eVote will
start, stop, or check The Clerk, synchronize data, or flush or restart
the log.


The eVote_Clerk Executable

eVote_Clerk runs all the time in the computer's background
establishing new polls, dropping old items, accepting,
tallying, storing, and reporting votes and statistics. eVote_Clerk
has no direct user-interface. It is started, controlled, and stopped
by the eVote executable.


Two Enhancements For Elections

As it is, the eVote(R)/Clerk system is not designed for, or suitable
for, Presidential elections. However, with two major enhancements, it
promises to be the most secure and accurate solution. The required
enhancements are:

1. A networking layer so that networked Clerks manage the distributed
data. The network will also facilitate a check on other Clerks' data
and calculations. For example, if a voter votes with one Clerk, and
is sent a receipt from that Clerk, and later, a second receipt is sent
to the voter from a different, randomly chosen, Clerk, this will
ensure the integrity of all The Clerks.

2. A secure encryption layer so that only software and the voter
can see that voter's ballot.

With these enhancements, The Clerk can provide more security than
generalized database servers for three reasons:

1. Clerks can redundantly and geographically distribute the votes
onto many small computers running the GNU System.

2. The individual administrators have minimal responsibility and
minimal power, and each administrator is watched by the network of
Clerks.
	
3. The Clerk involves the voters in facilitating not only recounts
and redundant checks, but also revotes.


We can go confidently into our electro-democratic age.



------

Marilyn Davis, marilyn@deliberate.com, earned her Ph.D. in Theoretical
Radio Astronomy in the ancient past. Now she waits tables and teaches
C and the Gnu development tools. She seeks to demonstrate that a
person of meager means can use these miracle tools to change
everything.