[tahoe-lafs-trac-stream] [tahoe-lafs] #1382: immutable peer selection refactoring and enhancements

[tahoe-lafs]

#1382: immutable peer selection refactoring and enhancements
-------------------------+-------------------------------------------------
     Reporter:  kevan    |      Owner:  markberger
         Type:           |     Status:  new
  enhancement            |  Milestone:  1.11.0
     Priority:  major    |    Version:  1.8.2
    Component:  code-    |   Keywords:  review-needed servers-of-happiness
  peerselection          |  blocks-release
   Resolution:           |
Launchpad Bug:           |
-------------------------+-------------------------------------------------

Comment (by markberger):

 Servers of happiness is limited by the cardinality of the smaller set.

 So in example 1 we have:
 {{{
 server A -> share 0
 server B -> share 1
 }}}
 and then for example two we add:
 {{{
 server C -> share 1
 }}}

 This doesn't increase happiness because share 1 is already matched with
 server B. Matching shares with extra servers doesn't increase happiness.
 Since we don't have any homeless shares to match with server C, we are
 limited by the cardinality of the smallest set, and happiness is set to 2.

 In example 4 we have
 {{{
 server A -> share 0, share 1
 server B -> share 1, share 2
 }}}

 We can match server A with share 0 and server B with share 1. Once again
 we are limited by the cardinality of the smaller set, so even though we
 matched server A with share 1 and server B with share 2 as well, those
 pairs do not increase happiness. Our set of matchings already has servers
 A and B, so any additional pairs with servers A and B will not increase
 happiness.

 However, when we add:
 {{{
 server C → share 1, share 2
 }}}

 we are no longer limited by the cardinality of 2 because each set has a
 cardinality of 3. So now we can match server A with share 0, server B with
 share 1, and server C with share 2. Each of these pairing has a unique
 server and share that is only used once in our set of matchings, therefore
 each pair contributes to a happiness of 3.

 That explanation would be the intuitive way to think about the maximum
 matching of bipartite graphs. I think it is clearer if you show pictures
 of bipartite graphs, but introducing such graphs might be outside the
 scope of the document.

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