28 Jun 2003 Bram   » (Master)

BitTorrent home

Sourceforge's CVS has been terrible recently. I would like to move BitTorrent's hosting somewhere else. Ideally to a place which is already hosting other things, has been doing so for a while, and is free.

I need the following -

  • A CVS repository, with ViewCVS, globally available anonymous CVS, the ability to set up new accounts, and access control. This should go without saying, but CVS should update immediately, which sourceforge isn't doing any more. It should also be possible to easily download a whole repository tarball.

  • Mailing lists which support moderation with more than one moderator, make the archives available online, do a reasonable job of keeping people from harvesting addresses, and give me easy access to the list of subscribed addresses so I can easily move it elsewhere later if necessary.

  • Download hosting, which allows new files to be easily published and taken down, tracks download stats, and can be linked to with a simple hyperlink (unlike sourceforge's redirection crap). This is currently about 40 gigabytes a day.

Anyone who would like to volunteer or suggest resources please mail me.

Random Picking

An interesting problem came up in BitTorrent development. There are n things, some of which pass and some of which don't. We would like to do a scan over all things and stop at the first one which passes. We could scan from the beginning, but that would lack an another property we want which is that each acceptable thing should have about an equal probability of being picked.

Scanning could be done randomly but that involves generating lots of random numbers, which can be very slow. I came up with a neat trick. Arrange the n objects into a list, pick an s less than n at random and a d less than n and relatively prime to n at random, then scan through (s + d * i) % n for each i < n.

What is the maximum possible bias towards or away from a particular object this technique can have? I think it works fine in practice.

Algorithm obfuscation

I realized the other day why my attempts to come up with simplistic invariants for circuit satisfiability problems were going absolutely nowhere.

Consider some algorithm for solving some problem. We will now generate an equivalent algorithm which is only slightly slower but whose operation is completely obfuscated. Select a secure hash function (we assume there are infinitely many of these, and they cannot all be summed up simply). Memory will instead of containing bits in the unobfuscated algorithm instead contain a single plaintext counter and many (count, bit) pairs. Whenever writing to memory, instead of writing out the bit you would have increment the counter by 1, then store (count, hash(count)[0] xor mybit). Memory can be read out by computing hash(count) xor memvalue. This completely and thoroughly obfuscates memory, to the point that I've decided to give up looking for a simple invariant to prove an absolute lower bound on runtime. Ah well.

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!