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.

Minefield

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)]
else:
times = []
for i in self.targets.keys():
try:
times.append((self.time_to_finish(i), i))
except ZeroDivisionError:
pass
times.sort()
if not times:
return result
t, peer = min(times)
completes = []
result.append(peer)
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:]
break
total += inc
else:
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:
break
else:
completes.append(i)
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()
inclist.sort()
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:
break
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].append(p)
else:
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):
donefriends.append(friend)
bounceback += self.dispense_to[friend].get(peer, 0)
else:
notdonefriends.append(friend)
try:
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]
```

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!