[tahoe-dev] safety and Tahoe Lock Files
zooko at zooko.com
Mon Mar 10 21:52:23 UTC 2008
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.
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
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.)
and in tickets:
Along the way of writing this post, I found this nice "potted history
of consensus, transactions and 2PC":
> 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.
More information about the tahoe-dev