Re: [freehaven-dev] Freehaven Simulation

[dmolnar@belegost.mit.edu]

My roommate Brendan was kind enough to listen to me rant about the
previous message for a little bit. He didn't know of any previous work on
something like this, but we did notice a few things.

* In a fully connected graph with totally reliable edges, we can calculate
  the probability each share has of disappearing on each turn :
	
	pr[Share dies] =  pr[Node holding share decides to trade] *
			  pr[Node picks an evil node to trade with]


* If all the nodes have the same probability of trading, and all the
  probability of picking an evil node is the same no matter where you
  are in the graph, then the probability of a share dying is constant
  at each step. It's just a question of how many steps on average 
  are needed before it does die...

* If the edges are uniformly unreliable, by which I mean each and every
  edge has the same probability of failure on every step for the duration
  of that step only, then that becomes just another factor above. 
  That is, we have 

	pr[Dying] = pr[Trade?] * pr[PickEvilNode] * pr[EdgeWorks]

* Now we can get closer to the "real world" by introducing non-uniformity
  in each of these factors. That is, 
	- Not all nodes trade with the same frequency
	- Not all nodes are always evil. we could have 
	   pr[PickEvilNode] = Pr[PickAdversaryNode] * Pr[AdversaryIsBad]

	- Not all edges work at the same probability.

  I'm not sure how to go about doing the math for this, but I bet it 
  exists...this doesn't seem that exotic. 

* Next we might want to include some kind of dependencies or conditions. 
  "IF" statements. "IF share is of file X, then the adversary kills it." 

* Next, we might want to include some state, besides position of shares.
	
	- Maybe once an edge goes down, it goes down for good?

* Then it seems that the trust network affects both 
	pr[Trade?]
	and pr[PickAdversaryNode]
	by making the selection of a trading partner non-uniform. That is,
	we might think about it as the trust network assigns some 
	probability weights ("trust ratings") to all other nodes in the
	network. 
		Then when it comes time to pick a trading partner, 
	the partner is picked according to those weightings.

Thanks, 
-David