TankTread
(first draft.) |
(stoppress) |
||
| (One intermediate revision by one user not shown) | |||
| Line 1: | Line 1: | ||
| + | |||
| + | = 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. |
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. This page is only interested in the way people move. |
+ | 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. |
So: currently it is advised that people use a 'folded line' method. |
||
| Line 9: | Line 16: | ||
{{Quote|left|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|http://keysigning.org/methods/sassaman-efficient}} |
{{Quote|left|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|http://keysigning.org/methods/sassaman-efficient}} |
||
| − | This is a O(2n) process. |
+ | 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) == |
== Tanktread is O(n) == |
||
| − | The layout is the same, but it's a loop instead. The loop slowly rotates, stopping to sign in pairs for each person in turn. Instead of one "fold", there is a fold at each end, and the ends join to become a loop. Everyone finishes at the same time. |
+ | 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. |
+ | 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. |
Latest revision as of 09:32, 10 February 2010
[edit] 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)
[edit] 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.
