[tahoe-dev] safety and Tahoe Lock Files

[zooko]

On Mar 7, 2008, at 4:43 PM, Jim McCoy wrote:
>
> The problem here is that for mutable files you seem to want
> consistent, available, and distributed/partition-tolerant when in fact
> you only get to choose two of the three.

Jim:

You are wrong to think that we are unaware of this general  
principle.  (In fact, I'm slightly surprised that you thought that we  
were being so naive -- don't you know us better than that?)  What we  
are discussing here is what trade-offs are possible between  
consistency, availability/performance, simplicity of implementation,  
and what abstractions are offered to the user.


As sometimes happens with rigorous, general theories, it is possible  
to do better than the celebrated impossibility result suggests, by  
realizing that your case is not the general case.  For example, the  
Byzantine Generals result proves that you can't come up with a  
consensus if more than 1/3 of your nodes are faulty or malicious.   
Some people (present company excluded, of course) might think that  
this implies that you can't reliably read a file from a decentralized  
storage grid if more than 1/3 of the storage servers are faulty of  
malicious.  However, this conclusion would be wrong, because reliably  
reading a file is not the general consensus problem -- it is an  
easier problem (at least if you are allowed to rely on the second-pre- 
image-resistance of SHA-256 and the unforgeability of digital  
signatures).

On the other hand, handling rollback attack is, I think, more or less  
the general consensus problem...


For better or for worse, the traffic that people post to tahoe-dev is  
but the tip of the iceberg.  More detailed docs about the evolving  
strategy for robust, distributed, mutable files is available in docs:

http://allmydata.org/trac/tahoe/browser/docs/mutable.txt # (Featuring  
an amusing rhetorical flourish about how celebrated is the  
consistency vs. availability issue in academia.)
http://allmydata.org/trac/tahoe/browser/docs/dirnodes.txt

and in tickets:

http://allmydata.org/trac/tahoe/ticket/205
http://allmydata.org/trac/tahoe/ticket/207
http://allmydata.org/trac/tahoe/ticket/312
http://allmydata.org/trac/tahoe/ticket/332


Along the way of writing this post, I found this nice "potted history  
of consensus, transactions and 2PC":

http://betathoughts.blogspot.com/2007/06/brief-history-of- 
consensus-2pc-and.html


> Please read "Two-level, Self-Verifying Data for Peer-to-Peer Storage"
> by Eaton, Weatherspoon, and Kubiatowicz

Sounds like a good one!  Thanks for the reference.

Regards,

Zooko