[freehaven-cvs] sb: more polishing on model, section 6

[arma@seul.org (Roger Dingledine)]

Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching

Modified Files:
	model.tex sync-batching.tex 
Log Message:
sb: more polishing on model, section 6


Index: model.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/model.tex,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- model.tex	26 Jan 2004 12:58:34 -0000	1.6
+++ model.tex	26 Jan 2004 13:55:14 -0000	1.7
@@ -98,27 +98,28 @@
 \label{singlemix}
 
 Consider a single mix receiving a batch of $K$ messages, including the
-targeted message $m$.  Assume that the mix has not been compromised and
-that it collects all $K$ messages before distributing them to their
+targeted message $m$.  Assume an uncompromised mix that
+collects all $K$ messages before distributing them to their
 respective destinations.  In this case, the mixing performed by the
 mix can be interpreted as permutation in a virtual buffer of size $K$.
 In particular, the targeted message $m$ appears in any of the $K$
 output positions with equal probability after passing through the mix.
-Therefore, each mix can be modeled by a simple Markov chain
+Therefore, each mix can be modeled by a simple Markov chain as below
 (recall that state $s$ represents the current position of message $m$,
-and let $t$ be the sequential number of the current hop). The compromised
+and let $t$ be the sequential number of the current hop). However,
+the compromised
 mix performs no mixing at all, and thus does not change
 the position of any message it processes.
 
 \begin{figure}
 \begin{minipage}[ht]{5.75cm}
-\caption{Model of a good mix}
 \includegraphics[scale=0.3]{goodmix}
+\caption{Model of a good mix}
 \end{minipage}
 \hfill
 \begin{minipage}[ht]{5.75cm}
-\caption{Model of a bad mix}
 \includegraphics[scale=0.3]{badmix}
+\caption{Model of a bad mix}
 \end{minipage}
 \hfill
 \end{figure}
@@ -130,12 +131,11 @@
 assuming a fixed number of hostile mixes, in each scenario we will assume
 a fixed \emph{probability} that a randomly selected mix is hostile.
 
-For each topology, the behavior of a single node is modeled as described
-in section~\ref{singlemix}.  The main difference between topologies
+For each topology, the behavior of a single node is modeled as
+in Section~\ref{singlemix}.
+The main difference between topologies
 is how the targeted message moves through the network, resulting in
-different mixing distributions~(\ref{maindist}).
-
-
+different mixing distributions in Equation~(\ref{maindist}).
 
 \subsubsection{Assumptions.}
 
@@ -154,10 +154,10 @@
 within the network is exactly equal to the statistically expected load
 given a particular network topology.  This assumption is approximated
 with very high probability when the number of messages in a single batch
-is significantly higher than the number of network nodes, and randomness
-involved in message routing is obtained from unbiased coin tosses in
-the same way for all messages (see section \ref{subsec:average-actual}
-for a detailed discussion).
+is significantly higher than the number of network nodes (see
+Section~\ref{subsec:average-actual} for a detailed discussion), and
+randomness involved in message routing is obtained from unbiased coin
+tosses in the same way for all messages.
 
 Intuitively, suppose there are four mixes in the first layer of the
 network, and batch size is 128.  We will analyze the average-case
@@ -171,7 +171,7 @@
 % either assumption, 
 
 Under the equal loading assumption, we treat the size of the input/output
-buffer for each mix (see section~\ref{singlemix}) as a constant which is
+buffer for each mix (see Section~\ref{singlemix}) as a constant which is
 determined only by batch size and network topology, and is independent
 of the actual random distribution of a given batch through the network.
 

Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.42
retrieving revision 1.43
diff -u -d -r1.42 -r1.43
--- sync-batching.tex	26 Jan 2004 12:58:34 -0000	1.42
+++ sync-batching.tex	26 Jan 2004 13:55:14 -0000	1.43
@@ -453,13 +453,13 @@
 \label{fig:badnodes}
 \end{figure}
 
-Figure~\ref{fig:badnodes} shows the entropy that Alice can expect when
-using each of the three topology choices we investigated. Because
-the cascade network immediately divides the incoming batch by the
-number of cascades, it provides substantially less protection even
-when many nodes in the network are compromised. The stratified and
-free-route topologies have similar expected entropy. In this section
-and Section~\ref{sec:metrics} we will examine other metrics for deciding
+Figure~\ref{fig:badnodes} shows the entropy Alice can expect from
+each of the three topologies.
+The cascade network immediately divides the incoming batch by the
+number of cascades, so it provides substantially less protection even
+with many compromised nodes. The stratified topology provides about
+the same expected entropy as the free-route topology.
+In this section and the next we will examine other metrics for deciding
 which is best. Further graphs in Appendix~\ref{sec:entropy-per-hop}
 indicate how much entropy is achieved after a given number of steps
 through each network.
@@ -475,7 +475,7 @@
 equivalently, vulnerable nodes) are randomly distributed. That is,
 rather than letting the adversary have his pick of nodes, we instead
 let the adversary control all the machines that have some security
-vulnerability. A related approach would be place particularly secure
+vulnerability. A related approach would be to place particularly secure
 and trusted (or at least jurisdictionally separate) nodes in key places
 in the topology: if such nodes are discouragingly secure, they are no
 longer an appealing target.
@@ -491,8 +491,8 @@
 \subsection{Choosing the same node twice in a row}
 
 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, to reduce her risk of picking only bad
+a free-route network, Alice should never pick the same node twice in
+a row: it increases her risk of picking only bad
 nodes. We find that for a sufficiently large network, this increased
 complexity in path selection has little impact on Alice's entropy.
 
@@ -557,8 +557,8 @@
 The graphs and analysis above are for average entropy---the network's
 behavior for very large batches. But in reality the batch size
 may be quite small, and each sender chooses paths independently from the
-others. We must consider the variance we could get in entropy depending
-on how the path choices actually turn out.
+others. We must consider the possible variance in entropy depending
+on the actual path choices.
 
 For $m$ messages to $u$ buckets (nodes in a layer), we find the chance
 that any bucket will have less than $p$ messages based on
@@ -575,21 +575,22 @@
 
 For $m=128$ messages and $u=4$ nodes (i.e.~cascade or stratified network),
 the chance of any node getting less than 16 messages (compared to
-the 32 we expect each to get) is $6*10^{-4}$---meaning with very high
+the 32 we expect each to get) is $6 \cdot 10^{-4}$---meaning with very high
 probability the average entropy approximates the behavior we will see
 in reality. On the other hand, for $u=16$ nodes (free-route), 48\% of
 the time some node will get less than half the expected number. It is
 not until a batch size of 480 that this metric reaches 1\%.
 
-This result is plausible: each link on a free-route network has a smaller
+This result makes sense: each link on a free-route network has a smaller
 expected number of messages, so variations have a bigger impact. Whether
 it is acceptable depends on a number of factors. First, how large do we
-expect batches to be in reality? If 500 messages or more, then we're fine.
+expect batches to be in reality? The Mixmaster network receives more than
+1000 messages an hour, which seems plenty sufficient.
 Second, how bad is it when a link varies by half the expected volume? If
 we change our metric to require at least 2 messages on each link for
 $m=128$, then we find that only 1\% of the cases fall outside this value.
 Another significant question is how the number of layers affect the
-results. The more layers, the greater the chance that some of them will
+results: the more layers, the greater the chance that some of them will
 well balanced. But, the exact relation and its effect on entropy are
 open questions.
 

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