TankTread

From ThorxWiki
Jump to: navigation, search

STOP PRESS

keysigning.org has clarified they they use and advocate the tank tread method, with a concession that it could be worded better, maybe with diagrams :) This page left as-was for the moment.



Tanktread is a way to describe an efficient movement of people at a keysigning.

It is described here: http://woozle.org/~neale/papers/tank-tread.html (with pretty javascript on another version here: http://woozle.org/~neale/tmp/tanktread.html ). Note that these pages also describe a now-defunct keysigning protocol proposal.

Here at ThorxWiki, we are only interested in the way people move

So: currently it is advised that people use a 'folded line' method.

everyone forms a long line in the same order as their keys appear in the list. The head of the line then folds back on itself and the participants moving back along the line inspect the ID of each participant standing still

This is a O(2n) process. The space required begins as a line of length n, folds back till it becomes a rectangle of length n/2 and width 2, which then shortens to 2. (because, pedantically, it no longer exists when it shortens to zero)

Tanktread is O(n)

With tanktread, we START at the two lines of n/2 length, and make it a loop - instead of one "fold", there is a fold at each end, and the ends join to become a loop.

The loop slowly rotates, stopping to sign opposite pairs for each person encountered in turn.

It should take less room than folded line, and also less time, albiet at the cost of a slightly more complex initial setup. Everyone finishes at the same time (allowing for a more social post-signing trip to the pub/etc. The space used is a constant over the whole time.

Personal tools
Namespaces

Variants
Actions
Navigation
meta navigation
More thorx
Tools