8
$\begingroup$

I'm trying to figure out a way to assign weights to a group of servers (a galera cluster of database servers), and I want to always be able to compute a quorum, meaning no set of weights should ever be allowed to add up to exactly 50% (a quorum in this case means over 50%).

Is there a mathematical formula to generate a set of (probably unique) numbers so that you can never sum any subset of those numbers to equal any subset of the remaining numbers? Additionally, no individual number should be double or more than double of any other number.

For example, with [3, 4, 5], there is no way to take any set of 1, 2, or 3 of those to add up to be equal to any subset of remaining numbers. There will always be an inequality, so a quorum can be computed (or it can be determined that no quorum is available, in the case where too many servers are disconnected from each other).

I understand this is a problem relating to server administration, but it seems to be of a mathematical nature.

What I'd like to be able to do is assign individual weights to a initial pool of servers, but ideally be able to generate another weight if another server gets added to the pool in the future.

The practical application is that all servers know their own weight, and they know the total weight of all servers. If a server suddenly dies, or connectivity fails between a few of them, the servers try to determine if they have a quorum. Each server that can still communicate with another will add up their weights, and if the total of their weights is more than exactly 50% of the initial set's total, then there is a quorum, and those servers will declare themselves to be the new canonical group. If they fail to get over 50%, they don't have a quorum and will declare themselves to be offline or otherwise unable to continue service.

$\endgroup$
  • $\begingroup$ Do they have to be integers? Also, you just give each one a rank, and then ties are settled by which one has the highest rank. $\endgroup$ – Acccumulation Apr 26 at 19:28
  • 1
    $\begingroup$ If I understand your use-case, a quorum is used to make sure multiple copies of data aren't corrupted during data transfer. If the majority of servers agree on a value, then that value is considered correct. If you assign weights to servers, isn't it possible that a small number of servers with corrupted data and high weights can overrule a larger number of servers with accurate data and low weights? $\endgroup$ – dx_over_dt Apr 26 at 19:42
  • $\begingroup$ Does the combining function on weights definitely have to be addition? $\endgroup$ – Daniel Wagner Apr 27 at 3:20
  • $\begingroup$ I don't think this "never sum any subset of those numbers to equal any subset of the remaining numbers? " is quite right, I think you require that no complete partitioning of the total set into two groups can produce groups with equal totals. It's quite acceptable to have the set {1, 1, 1, 2, 2} which has many equal subsets {1,2} {1,2} and {2}, {2}. But it works for your purpose: you cannot get split-brain with that set, required quorum is 4, achieved by partitions such as {2,2} or {1,1,1,2}. $\endgroup$ – djna Apr 27 at 5:24
  • $\begingroup$ I don't know if it must be integers; the documentation is vague there (I actually opened a question on another SE to find out). A quorum isn't used to ensure data is transferred without corruption. Rather, it is used to self determine if the database should allow itself to continue service requests (to prevent future corruption or forking of data). $\endgroup$ – Stephen Schrauger Apr 27 at 5:32
9
$\begingroup$

For $n$ servers, consider weights $$ 1 + m, 2 + m, 4 + m, \ldots, 2^n + m $$ for $m$ large enough to make sure each is less than twice each of the others.

The uniqueness of subset sums for subsets of equal size follows from the uniqueness of binary expansions.

$\endgroup$
  • 3
    $\begingroup$ Seems like just $m = 2^n-1$ ? Then the final result are numbers between $2^n, ..., 2^{n+1}-1$ (with "..." according to your rule ;) ). $\endgroup$ – AnoE Apr 26 at 15:03
  • $\begingroup$ This works out perfectly for my use case, thanks! In my specific use-case, the documentation says the weight can only be from 0-255, so this formula will only work with a max of 8 servers (n=0...7, and assuming the software only allows integer weights), but that's good enough for my purposes. $\endgroup$ – Stephen Schrauger Apr 26 at 15:23
  • $\begingroup$ Am I missing something, or does this not allow for adding servers to the pool in the future? $\endgroup$ – Servaes Apr 26 at 16:24
  • 1
    $\begingroup$ @Vilx- This answers the mathematical question about sums of subsets. Whether it really works for servers is a different question. The servers all have about the same weight since $m$ is relatively large - none has more than half. And I think the OP is looking for a quorum among remaining servers - a subset of a subset. $\endgroup$ – Ethan Bolker Apr 26 at 20:51
  • 2
    $\begingroup$ @EthanBolker - yes, it does answer the mathematical question, however I'm trying to warn Stephen that it does not solve his practical problem because he has asked the wrong question. Also, he has said that he only has values 0-255 available (so either a small n or a small m) , and both his words and the Galera link he gave talks about the percentage of the total weight, not some subset. So, again - wrong question from him. $\endgroup$ – Vilx- Apr 26 at 21:02
5
$\begingroup$

If the weights needn't be integer, you can choose them from the set $$\left\{1+\frac1p:p\text{ prime}\right\}$$

$\endgroup$
  • $\begingroup$ Why bother taking the square root? (For that matter, why bother adding 1?) $\endgroup$ – Daniel Wagner Apr 27 at 3:14
  • $\begingroup$ Adding $1$ avoids that some weight is more than the double of some another. The square root, on second thought, is not necessary. $\endgroup$ – ajotatxe Apr 28 at 7:44
-1
$\begingroup$

Perhaps you are over-thinking this? What do you lose by taking a quorum as being simply more than 50% of the servers? If you want a way to break ties when the servers are split into two groups of equal size, just name one server as being special, and take the group that contains the special server.

Or am I missing something?

$\endgroup$
  • 5
    $\begingroup$ Given that this is a comment on the motivation of the question rather than a response to the specific mathematical question, this should probably be a comment instead of an answer. $\endgroup$ – Noah Schweber Apr 26 at 14:13
  • $\begingroup$ What if that special server is the one that goes offline? If 8/9 servers are still up, but the special one is down, then the whole service will go down. The purpose is to avoid single points of failure. $\endgroup$ – Stephen Schrauger Apr 26 at 14:13
  • $\begingroup$ @StephenSchrauger: No, because 8/9 is more than 50%. It's only when a group contains exactly 50% of the servers that you need to use the tie-breaker criterion. $\endgroup$ – TonyK Apr 26 at 14:14
  • $\begingroup$ True, but if that special server goes offline, there then exists the possibility of a future network outage that splits 4 servers from the other 4. They both add up to exactly 50% (or rather, they add up to be equal to each other), which is a specific situation that I'm trying to avoid (in a galera cluster, that's called a split brain condition). $\endgroup$ – Stephen Schrauger Apr 26 at 14:16
  • $\begingroup$ @StephenSchrauger: But then what if neither group adds up to more than 50%? If they don't know about the offline server, how can they calculate the sum of all the weights? (And if they do know about the offline server, then they can nominate a new special server.) It seems to me that you are asking the impossible. $\endgroup$ – TonyK Apr 26 at 14:23
-1
$\begingroup$

If "probably unique" turns out to be "actually, no, they don't need to be unique," then weight one server as 2n+1, and all of the remaining servers as 2n. Then no matter how the two groups are chosen, one group will always have an odd sum and the others will always have an even sum. The two sums will thus never be the same.

$\endgroup$
  • 1
    $\begingroup$ This does not appear to answer the question; the question is quite clear that the two subsets under consideration need not partition the original set. So with your scheme if there are three or more servers, taking the two subsets to be each singletons of weight 2n gives equal sums. $\endgroup$ – Daniel Wagner Apr 27 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.