[tahoe-dev] "servers of happiness"

David-Sarah Hopwood david-sarah at jacaranda.org
Wed Oct 14 04:58:16 UTC 2009

Zooko Wilcox-O'Hearn wrote:
> I asked my wife Amber for help formalizing my intuition about what  
> sort of share placement makes me happy.  We came up with this:
> First of all, let's call a set of servers "sufficient" if you can  
> download the file from that set (i.e. if at least K distinct shares  
> are hosted in that set of servers).

Call it K-sufficient.

> Now consider the largest set of servers such that every K-sized  
> subset of it is sufficient.
> Let's call the size of that largest set S.

This largest set isn't necessarily unique. I think you mean:

  A set U is K-happy iff every K-sized subset of U is K-sufficient.
  Let S be the largest integer such that there exists a K-happy set
  of size S.

Then S is unique, even though there may be more than one K-happy set
of that size.

> Now my intuition about  
> "Happyness" is that I configure a Happyness number H, and if an  
> upload results in an S >= H then I'm happy.

Note that this only makes sense for H >= K. If H < K then consider
an arbitrary set U of size H: it is vacuously K-happy, because it has
no K-sized subsets. Therefore S >= H, because there must exist K-happy
sets at least as large as U. This is despite the fact there the file
may not be downloadable from any set of servers.

Anyway, your intuition, if it is correct, is equivalent to the
simpler statement:

  I am happy iff there exists a K-happy set of size H.

because if there exists a K-happy set of any size S >= H, then
there exists a K-happy set of size H.

(This follows from the fact that if U' is a subset of U, then
the set of K-sized subsets of U' is a subset of the set of K-sized
subsets of U. Therefore, if there is a K-happy set of size S then
all subsets of it are K-happy, and therefore there are K-happy
sets of sizes 0..S-1.)

David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

More information about the tahoe-dev mailing list