[tahoe-lafs-trac-stream] [tahoe-lafs] #2107: don't place shares on servers that already have shares

[tahoe-lafs]

#2107: don't place shares on servers that already have shares
-------------------------+-------------------------------------------------
     Reporter:  zooko    |      Owner:
         Type:           |     Status:  new
  enhancement            |  Milestone:  undecided
     Priority:  normal   |    Version:  1.10.0
    Component:  code-    |   Keywords:  upload servers-of-happiness brians-
  peerselection          |  opinion-needed
   Resolution:           |
Launchpad Bug:           |
-------------------------+-------------------------------------------------

Comment (by daira):

 Replying to [comment:26 zooko]:
 > Where "Servers-of-Happiness-Level" is defined as:
 >
 >     ''Servers-of-Happiness-Level: the size of the largest set of servers
 such that '''any''' K-sized subset of it can recover the file.''
 >
 > (I think. Did I get that definition right??)

 Not exactly. Suppose that there is no K-sized subset of servers that can
 recover the file; then there is no such largest set, and so this wording
 would not give a well-defined result.

 The correct definition is:

 ''Servers-of-Happiness-Level: the size of a maximum matching in the graph
 relating servers to shares that they hold.''

 or equivalently:

 ''Servers-of-Happiness-Level: the maximum number of links that can be
 drawn from servers to shares that they hold, such that no server and no
 share appears more than once.''


 The original definition could instead be repaired by setting the result to
 0 when there is no K-sized subset that can recover the file, but that
 would be less useful. The difference doesn't matter for deciding when an
 upload or repair meets a happiness threshold `shares.happy` >= K, but it
 does matter for defining intermediate steps of a placement algorithm.

-- 
Ticket URL: <https://tahoe-lafs.org/trac/tahoe-lafs/ticket/2107#comment:30>
tahoe-lafs <https://tahoe-lafs.org>
secure decentralized storage