20 Aug 2003 Bram   » (Master)

Voting Machines

chalst: Certainly electronic voting machines could in theory both have a paper audit trail and be much more reliable than any past vote counting mechanism. Rebecca Mercuri, whose ejection from a conference got us talking about this in the first place, has some very good thoughts on the topic. Unfortunately the current batch of voting machines are a big step back in terms of reliability, even ignoring their lack of paper trail and likely rigging of elections.


chalst: In the case of two infinites which don't have a clear ordering neither player will successfully challenge the other and they'll have to play another round. The point of it being a game is that the players have the opportunity to try to challenge each other without it ever being necessary to prove that no such challenge exists, since proving the consistency of large infinites is by nature impossible to do without assuming the existence of yet ever larger infinites.

Trust Metrics

I've implemented my latest trust metric. This implementation requires Python 2.3, and includes some 'clever' algorithmic things which should make it reasonably fast in practice. I've tested this code, but not as thoroguhly as I'd like.

from bisect import insort
from __future__ import division
class TM:
    def __init__(self, seed, get_peers):
        self.seed = seed
        self.get_peers = get_peers
        self.point_to = {'phantom': [seed]}
        self.point_from = {seed: ['phantom'], 'phantom': []}
        self.targets = {seed: 1}
        # {peer: [(time, increase)]}
        # stays sorted by time
        self.dispensation_schedule = {'phantom': [(0, 1)]}
        # {peer: [{peer, proportion}]}
        self.dispense_to = {'phantom': [(seed, 1)]}
    def get_closest_peers(self, numaccept):
        result = []
        while True:
            if not result:
                times = [(1, self.seed)]
                times = []
                for i in self.targets.keys():
                        times.append((self.time_to_finish(i), i))
                    except ZeroDivisionError:
            if not times:
                return result
            t, peer = min(times)
            completes = []
            del self.targets[peer]
            if len(result) == numaccept:
                return result
            # change the dispensation schedules of everything which contributed to this new 
            # peer to reflect that their output is earmarked until the new peer is full
            for i in self.point_from[peer]:
                total = 0
                for j, (t2, inc) in enumerate(self.dispensation_schedule[i]):
                    if t2 > t:
                        self.dispensation_schedule[i] = [(t, total)] + self.distribution_schedule[j:]
                    total += inc
                    self.dispensation_schedule[i] = [(t, total)]
            # for all complete peers which newly have all their friends full, 
            # redistribute their outflow to their friends
            completes = []
            for i in self.point_from[peer]:
                for j in self.point_to[i]:
                    if j not in result:
            if completes:
                for c in completes:
                    self.redistribute(c, t)
    def time_to_finish(self, peer):
        incs = {}
        for i in self.point_from[peer]:
            for (t, inc) in self.dispensation_schedule.get(i, []):
                incs[t] = incs.get(t, 0) + inc
        inclist = incs.items()
        current_rate = 0
        current_time = 0
        current_amount = 0
        for t, inc in inclist:
            new_amount = current_amount + (t - current_time) * current_rate
            if new_amount >= 1:
            current_amount = new_amount
            current_time = t
            current_rate += inc
        return current_time + (1 - current_amount) / current_rate
    def redistribute(self, peer, t):
        # pull in friend information of peer's friends
        for p in self.point_to[peer]:
            if not self.point_to.has_key(p):
                self.point_to[p] = self.get_peers(p)
                for x in self.point_to[p]:
                    if self.point_from.has_key(x):
                        self.point_from[x] = [p]
                        self.targets[x] = 1
        # calculate the distribution of peer's outflow
        donefriends = []
        notdonefriends = []
        bounceback = 0
        for friend in self.point_to[peer]:
            if self.point_to[friend]:
                if self.dispense_to.has_key(friend):
                    bounceback += self.dispense_to[friend].get(peer, 0)
            mult = 1 / (len(donefriends) + len(notdonefriends) - bounceback)
        except ZeroDivisionError:
            mult = 0
        newdist = {}
        for friend in notdonefriends:
            newdist[friend] = mult
        for friend in donefriends:
            m = mult * (1 - self.dispense_to[friend].get(peer, 0))
            for p2, amount in self.dispense_to[friend].items():
                if p2 is not peer:
                    newdist[p2] = newdist.get(p2, 0) + amount * m
        # optimize peer out of other peers's distribution lists
        for i in self.point_from[peer]:
            if self.dispense_to.has_key(i):
                d = self.dispense_to[i]
                for friend, amount in newdist.items():
                    if friend is not i:
                        d[friend] = d.get(friend, 0) + amount * d[peer]
                del d[peer]
        self.dispense_to[peer] = newdist
        # add new scheduled distribution
        m = self.dispensation_schedule[peer][0][1]
        for friend, amount in newdist.items():
            insort(self.dispensation_schedule.setdefault(friend, []), (t, amount * m))
        del self.dispensation_schedule[peer]

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!