[freehaven-cvs] A few numbers about choosing nodes twice in a row.

[syverson@seul.org]

Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/tmp/cvs-serv10094/sync-batching

Modified Files:
	sync-batching.pdf sync-batching.tex 
Log Message:
A few numbers about choosing nodes twice in a row.


Index: sync-batching.pdf
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.pdf,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
Binary files /tmp/cvs6i7yZw and /tmp/cvsaoAKoW differ

Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.25
retrieving revision 1.26
diff -u -d -r1.25 -r1.26
--- sync-batching.tex	23 Jan 2004 18:55:37 -0000	1.25
+++ sync-batching.tex	23 Jan 2004 19:38:47 -0000	1.26
@@ -445,14 +445,12 @@
 
 \subsection{Choosing the same node twice in a row}
 
-XXXneed to rewrite this subsection.
-
 Conventional wisdom (see e.g.~\cite{minion-design}) suggests that
 in a free-route network, Alice should never choose the same node twice
 in a row when picking her path. The goal is to reduce the chance that
-the path contains only bad nodes. But we find that for a sufficiently
+the path contains only bad nodes. We find that for a sufficiently
 large network, this increased complexity in path selection has little
-impact on Alice's entropy.
+impact on Alice's entropy. 
 
 Intuitively, when the adversary density is low, entropy will be high
 in either case; whereas when most nodes are owned by the adversary,
@@ -462,8 +460,16 @@
 chance of selecting a bad node next is $\frac{B-1}{G+B}$ if
 the current node is bad and $\frac{B}{G+B}$ otherwise.
 The difference is only $\frac{1}{G+B}$: it does not depend on what
-fraction of the nodes are bad. As the network size grows,
-the shift in probability distribution becomes negligible.
+fraction of the nodes are bad. For a 16x4 free-route mixnet with
+4 bad nodes, the difference amounts to a 2\% chance of an all bad
+path if the same node cannot be picked twice in a row and a 3.9\% chance
+if it can. With 8 bad nodes, this becomes 5.1\% and 6.3\% respectively.
+As the percent of bad nodes grows, the shift in probability becomes
+more negligible. This is also true as the network size grows.
+For example, for a 32x4 mixnet with half bad nodes, the difference
+is 5.7\% vs.\ 6.3\% . At what point this difference can safely
+be ignored is a question that can only be answered in context, but
+we will ignore it for the present.
 
 % Mention that we have that entropy different for each of \ell hops.
 % But it's just \ell times the above negligible difference, right? -RD
@@ -847,8 +853,8 @@
 
 %\section*{Acknowledgements}
 David Hopwood for the initial impetus and ideas; Camilla Fox, Rachel
-Greenstadt, Chris Laas, and Itamar Shtull-Trauring for probability
-discussions;
+Greenstadt, LiWu Chang, Chris Laas, Ira Moskowitz,
+and Itamar Shtull-Trauring for probability discussions;
 
 %======================================================================
 

***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/