[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] More robustness calculations. Robustness sections do...
Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/tmp/cvs-serv28635/sync-batching
Modified Files:
sync-batching.pdf sync-batching.tex
Log Message:
More robustness calculations. Robustness sections done?
Index: sync-batching.pdf
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.pdf,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
Binary files /tmp/cvs2JYki0 and /tmp/cvsqE1vLU differ
Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.22
retrieving revision 1.23
diff -u -d -r1.22 -r1.23
--- sync-batching.tex 22 Jan 2004 23:40:24 -0000 1.22
+++ sync-batching.tex 23 Jan 2004 00:54:38 -0000 1.23
@@ -8,6 +8,10 @@
\newcommand\emailaddr{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
\newcommand\XXXX[1]{{\small\bf [XXXX #1]}}
+\newcommand{\workingnote}[1]{} % The version that hides the note.
+%\newcommand{\workingnote}[1]{(**#1)} % The version that makes the note visible.
+
+
\newenvironment{tightlist}{\begin{list}{$\bullet$}{
\setlength{\itemsep}{0mm}
\setlength{\parsep}{0mm}
@@ -20,7 +24,11 @@
%\title{The Disadvantages of Cascade Mix Networks and How to Overcome Them}
%\title{The Advantages of Free-Route Mix Networks
%\title{Synchronous Batching:\\Cascade Networks vs Free-Route Networks
-\title{Synchronous Batching:\\From Cascade Networks to Free Routes
+%\title{Synchronous Batching:\\From Cascade Networks to Free Routes
+%\title{Mixing in Step:\\Synchronous Batching from Cascade Networks to
+% Free Routes
+\title{Groove Mixing:\\Synchronous Batching from Cascade Networks to
+ Free Routes
\thanks{Portions of this paper were inspired by discussions with David
Hopwood. We would consider him an author, but have been unable to contact
him since beginning the paper. We'll keep trying.}}
@@ -600,52 +608,106 @@
\subsection{Robustness of Message Delivery}
-[Would a graph or three help illustrate these robustness points? -PS]
-[you won't get robustness graphs at this point. but you will get to
-start with a graph with 16x16 and 1x16 showing great anonymity, to
-motivate your discussion. perhaps you want to add a few robustness
-tables, to show off the numbers? make sure you're comparing similar
-situations between topologies, so the comparisons mean something. -RD]
+
+
It might seem from Fig.~\ref{fig:?} that the best anonymity is
achieved with a 16x16 free-route network. There is almost no falloff
in entropy until each node has a ninety percent chance of being
-compromised.
-But this ignores robustness of message delivery. (Robustness of
+compromised. But this ignores robustness of message delivery. (Robustness of
anonymity is discussed below.) With only a single node failure, for
randomly chosen routes through this mixnet, nearly two thirds of
messages will be undelivered (because they will need to pass through
-it at some point). With any quarter of the nodes nonfunctional, only
-one percent of messages will be delivered through the network. This
-makes such a network very brittle.
+it at some point). Such a network is very brittle.
+This illustrates that robustness can be an important question.
-A 4x4 cascade network does much better. A single failed node affects
-only one quarter of the messages. And two failed nodes have a one in
-ten chance of being no worse than a single failed node. On the other
-hand there is a ninety percent chance that half the messages are
-blocked by two failed nodes. With a quarter of the nodes down, there
-is only a .035 probability that these will be distributed so as to
-block all of the messages.
-In a 4x4 stratified topology, a single failed node also stops a
-quarter of the messages. Given a balanced message distribution across all
-layers of the network, a second failed node will always affect more
-messages. But, there is only a ten percent chance that two node
-failures chosen at random will block half the messages. And, with a
-quarter of the nodes gone there is only a $5.5 \times 10^{-4}$
-probability that this will happen in a way that blocks all the
-messages.
+\begin{table} \caption{Percent messages delivered: Worst adversary dist.}
+\renewcommand{\arraystretch}{1.3}
+\begin{center}
+\begin{tabular}[b]{| l || c | c | c | c |}
+
+\hline
+Topology & 1 crash & 2 crash & 3 crash & 4 crash \\
+\hline
+\hline
+16x16 free & 36 & 12 & 04 & 1 \\
+4x4 casc. & 75 & 50 & 25 & 0 \\
+4x4 strat. & 75 & 50 & 25 & 0 \\
+16x4 free & 77 & 59 & 44 & 32 \\
+\hline
+
+\end{tabular}
+\end{center}
+\end{table}
-Of the scenarios we have considered, a 16x4 free route is the most
-robust to message loss. For randomly chosen routes, a single failed node can be
-expected to block delivery of only 6.7 percent of the messages. Four
-failed nodes can be expected to block delivery on only a third of the
-messages.
-% Comparing apples to oranges here? You say 1/3 here, and 10^-4 above.
-% The small chance sounds more impressive, but it's of a different
-% thing? -RD
-At least as significant is that this is the expected
-fraction of messages blocked regardless of which four nodes fail.
+
+\begin{table} \caption{Percent messages delivered: Best adversary dist.}
+\renewcommand{\arraystretch}{1.3}
+\begin{center}
+\begin{tabular}[b]{| l || c | c | c | c |}
+
+\hline
+Topology & 1 crash & 2 crash & 3 crash & 4 crash \\
+\hline
+\hline
+16x16 free & 36 & 12 & 04 & 01 \\
+4x4 casc. & 75 & 75 & 75 & 75 \\
+4x4 strat. & 75 & 56 & 42 & 32 \\
+16x4 free & 77 & 59 & 44 & 32 \\
+\hline
+
+\end{tabular}
+\end{center}
+\end{table}
+
+\begin{table}
+\caption{Exp.\ percent messages delivered: Random adversary dist.}
+\label{table:expected-delivery}
+\renewcommand{\arraystretch}{1.3}
+\begin{center}
+\begin{tabular}[b]{| l || c | c | c | c |}
+
+\hline
+Topology & 1 crash & 2 crash & 3 crash & 4 crash \\
+\hline
+\hline
+
+16x16 free & 36 & 12 & 04 & 01 \\
+4x4 casc. & 75 & 55 & 39 & 27 \\
+4x4 strat. & 75 & 55 & 39 & 27 \\
+16x4 free & 77 & 59 & 44 & 32 \\
+
+\hline
+
+\end{tabular}
+\end{center}
+\end{table}
+
+Table~\ref{table:expected-delivery} shows that
+4x4 cascades and 4x4 stratified networks do roughly the same on
+average, but for very different reasons. Probability that
+configurations will block all messages increases much more quickly for
+cascades, but the maximum possible delivery of messages remains much
+higher. This can be seen in the table reflecting the most favorable
+adversary distribution for up to four node crashes. To further
+illustrate, if half of the nodes are bad in the 4x4 cascade topology,
+then in about 1 in 6 cases a quarter of the messages get through, and
+in exactly 6 cases of 12870 half of the messages get through the
+cascades. For all other distributions, no messages get through. If
+half of the nodes are bad in the 4x4 stratified network, then the
+highest percentage of messages that can pass through is 6.25.
+However, some messages will be passed in the majority of adversary
+distributions.
+
+Of the scenarios we have considered, a 16x4 free route has the best
+expected chance of message delivery for random distributions of the
+adversary. It outperforms the others unless the adversary has a
+particularly innocuous distribution, in which case cascades do better.
+Also note that the expected fraction of passed messages is the same
+for free routes regardless of which four nodes fail. In this sense
+it is the most robust wrt adversary distribution not just the adversary
+size.
\subsection{Robustness of Anonymity}
@@ -730,7 +792,7 @@
layer-3 and layer-4. Remaining messages are down to .32 of the
original mixnet batch. In this case, despite all the luck of the
adversary, the anonymity is thus still better than that of a message
-sent into a cascade processing a quarter of the original messages. And
+sent into a cascade processing a quarter of the original mixnet batch. And
this is also better than the anonymity of the stratified 4x4 network
with just two hostilely crashed entry nodes.
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/