\documentstyle[twoside, fancyheadings, doublespace, fullpage, epsf]{article}
\setstretch{1.5}
\textheight 8.8 in

\lhead{ David Molnar ({\it dmolnar@hcs.harvard.edu})}
\rhead{Free Haven Project: Notes Towards A Simulation Model \\
\today}

\begin{document}

\pagestyle{fancy}
\pagenumbering{arabic}

\section{Introduction; What This Is}

The Free Haven protocol uses parameters which are specified by
individual servers and publishers. For example, the size and expiration
date of shares is set at creation time as the publisher wishes. We
currently have no idea what the best parameters are. One way to find out
is to create a model of our system, and then use simulations or analysis
to determine good parameters. 

This is the first stab at such a model. 

\section{General Model}

This section tries to outline the most general model possible. The next
section will consider simplifications necessary for a first round
simulation and analysis. 

The servnet is considered as a directed graph. Each node in the graph
represents a server. Each edge represents a means which the origin has of
communicating with the terminal. For the purposes of this model, these
edges are assumed to be anonymous channels. 

\it{picture of graph goes here}

Because every node is assumed to know about every other node, we have a
fully connected graph. Now we can define some terms for talking about how
the Free Haven protocol works on this graph.

\subsection{Data and Terms}

We have defined the graph $G = (N, E)$ with $N$ the set of servnet nodes
and $E$ the set of anonymous channels. 

There is a notion of time divided into discrete \emph{steps.} Time starts
at step 0 and is then unbounded. 

Free Haven is a system for storing \emph{files}. Files are defined as sets
of \emph{shares}. A share is a unit of data; shares may have a certain
\emph{size} and an \emph{expiration date.} 

Each node $X$ has the following state associate with it :

\begin{description}

\item[share store:] Each node has a ``share store" which represents 
		    the shares currently held by that node, and the node's
		    holding capacity. 

\item[trust function] Each node has a function $\phi_X : N \rightarrow
[0,1]$ which maps nodes to a real ``trust value" between 0 and 1. The
value 1 represents fully trusted. The value 0 represents not trusted at
all. 

\item[metatrust function] Each node has a function $\psi_X : N \rightarrow
[0, 1]$ which maps nodes to a real ``meta-trust value" between 0 and 1.
The value 0 means that the node has no confidence in its value of
$\phi_X(n)$ for a particular $n \in N$; the value 1 means that the node
has complete confidence in its value of $\phi_X(n)$. 

\item[trade probability function] Each node has a function which models
the ``decision" to trade on each step and returns a probability betwen 0
and 1. Not yet clear what this should depend on. Certainly the timestep,
but also the values of the share store, trust functions, and meta-trust
functions? (e.g. "Trade only if about to expire share and median trust is
above some threshold with high confidence"). 

\end{description}

\subsection{Step Update}

We now describe how the system evolves from step to step. 

NOTE : this needs work to fit with the general framework established in
the previous subsection...

At each step, each node N does the following :
\begin{itemize}
\item

	1) N decides with probability p1 "Do I want to trade?" 
	If N does not want to trade, continue.
\item

	2) If N wants to trade,
then 
\begin{itemize}
\item

		2.1) N selects uniformly at random from the set of all
other
		servnet nodes a destination D	
\item

		2.2) N selects uniformly at random from the set of all its
shares a share S1
\item

		2.3) D selects uniformly at random from the set of all its
shares a share S2
		NOTE 1 : What if either N or D have no shares?? My
		inclination is to just trade for a "null share." It
		doesn't make sense to forbid trades, or else trading
		is quickly restricted to a very small set of nodes. 
		What do we do in the real protocol, again?
\item

		2.4) The nodes N and D exchange their shares S1 and S2
\end{itemize}
\item

	3) If D is an adversary node, then it destroys S1. If D is not
	an adversary node, then it keeps S1.
		NOTE 2 : What should an adversary node trade out??
		In the model as just described, it never has any shares
		to trade (by definition!). Should it always trade out
		null shares, or should it make up special 
		marked "adversary shares" so we can see how far they
		propagate through the network?	

\item
4) Continue. 

\end{itemize}


\section{Metrics}

This section discusses metrics of ``goodness" for the preceding model, 
such as ``how many nodes must be corrupted before a file is lost." 

\section{First Round Simulation and Analysis : Simplified Model}

This needs work to make each of these assumptions precise/mathematical in
terms of the first section. 

\begin{itemize}

\item
 Each node has zero or more shares. No shares are created during the 
  simulation. 
\item The initial placement of shares is arbitrary (set by the user of the
  sim). Maybe it's confined to a bunch of start nodes.
\item Some arbitrary percentage P of the nodes are controlled by an
adversary.


\item
 This percentage is fixed at network construction time. That is, we have
  a static adversary. 

\item
 
The adversary's only behavior is to drop packets on the floor, always. 
  The adversary does *not* decide whether or not to drop something - it 
  just drops all incoming packets.

\item

 All nodes trust all other nodes completely and forever. That is, we
  don't model the effect of the trust network in the first version. 
  Note that this means we will get wildly different answers for constants
  and robustness in the first version than we will in the final one. 
  This will allow us to quantitatively estimate the importance of the 
  trust network.

\item

 All files use the same number of shares. All files use a n/2 threshold. 
  (i.e. 15 out of 30 required to reconstruct). * All shares are the same
size. 
\item

 Nodes have unlimited storage space for shares.  

\item

 No shares ever expire during the time of the simulation. 

\item
 Nodes will trade for anything. 

\item
 All trades are always successful. 

\end{itemize}

\section{Mathematical Techniques and Related Work}

This section discusses mathematical techniques for analysing this model,
and related work on similar models. 

\end{document}