8

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.

Stephen S
  • 193
  • 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. – Acccumulation Apr 26 '19 at 19:28
  • 1
    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? – dx_over_dt Apr 26 '19 at 19:42
  • Does the combining function on weights definitely have to be addition? – Daniel Wagner Apr 27 '19 at 03:20
  • 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}. – djna Apr 27 '19 at 05:24
  • 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). – Stephen S Apr 27 '19 at 05:32
  • Yes, the combining function must be addition, mainly because that's the way the software is written already. I'm working within algorithms outside of my control. – Stephen S Apr 27 '19 at 05:32
  • @djna It's true that a quorum with {1, 1, 1, 2, 2} wouldn't have a split brain possibility. But once a quorum is reached with {2,2} for example, it could then occur after. When a quorum is reached, all other servers (weights) are removed from the set of weights, and only the participating weights are considered thereafter. If another failure occurred, the remaining split of {2},{2} would result in a split brain, exactly equal sums. Also, the split does not have to necessarily create only 2 subsets, but any number of subsets (though that may not apply to your example). – Stephen S Apr 27 '19 at 05:35
  • @StephenSchrauger I had expected that the "estate" remains unchanged during failure, estate size 7, quorum 4; in your scenario we make a new estate and hence a new quorum condition. Can we address by having quorum being (n/2)+1? In a {2,2} estate the quorum is 3, which does mean we can't run if we lose another machine, but that's exactly what we need for avoiding split-brain. Avoiding split brain requires extra resource {1} is fine. {1, 1} gives no resilience benefit, quorum is 2, lose a machine, we can't run. {1,1,1} is the minimum requirement, now losing one machine allows service. – djna Apr 27 '19 at 06:32

4 Answers4

9

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.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
  • 3
    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 ;) ). – AnoE Apr 26 '19 at 15:03
  • 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. – Stephen S Apr 26 '19 at 15:23
  • Am I missing something, or does this not allow for adding servers to the pool in the future? – Servaes Apr 26 '19 at 16:24
  • Or you could you apply the rule "Take the set with the largest number of servers. If two sets have the same number, pick the set with the highest ranked member." The two are equivalent, but this one is more transparent. – Acccumulation Apr 26 '19 at 19:33
  • @StephenSchrauger - Careful. If you assign powers-of-two to your servers, then the largest server will alone have 50% of the weight. If it goes down, the rest won't do quorum. I think it's best to just assign them equal values.That makes sure that as long as more than half of your servers are online, the show will go on, no matter which ones. – Vilx- Apr 26 '19 at 20:33
  • 1
    @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. – Ethan Bolker Apr 26 '19 at 20:51
  • 2
    @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. – Vilx- Apr 26 '19 at 21:02
  • @Vilx- Indeed, perhaps he has asked an x-y question. But he does say this limited answer addresses his use case. https://en.wikipedia.org/wiki/XY_problem – Ethan Bolker Apr 26 '19 at 21:15
  • @Vilx I appreciate the concern. When I initially asked the question, I was unaware of the 0-255 limitation, but I didn't want to change the question after I read about that. Regarding the total weight, once a quorum has been reached, I believe the other servers get removed from the calculation moving forward, so it's a new total (and it changes again when new servers join). But yes, I did not generalize the requirements quite precicly how I should have. – Stephen S Apr 27 '19 at 01:00
  • Also, the more generalized binary expansion could still work, if the weights are allowed to be non integer. Then, I could just go with fractions (1/2, 1/4, etc) and add 1 to each. That way, no single server will outweigh another set, and they'll still retain the additive properties I'm looking for. – Stephen S Apr 27 '19 at 01:03
  • @StephenSchrauger - Hmm, you're right, once a quorum (aka Primary Component) has been reached, they will then take the total of that group and if there is another split, then that new number will be used instead. I see what you mean. Yes, then your question was actually correct. Hmm... you can actually still salvage this scheme by giving your servers weights 128+[0/1/2/4/8/16/32/64]. That limits you to 8 servers at most though. – Vilx- Apr 27 '19 at 01:26
  • Your answer assumes the subsets have equal size; you should explain why it works even with subsets of different sizes. – Greg Martin Apr 27 '19 at 01:38
  • @GregMartin I thought that was pretty clear, and so apparently did the OP. – Ethan Bolker Apr 27 '19 at 01:41
  • @Acccumulation this doesn't work, because the servers in one set don't know whether the servers in the other set are just not reachable from them, or totally offline. – Paŭlo Ebermann Apr 27 '19 at 12:17
5

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

ajotatxe
  • 65,084
-1

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?

TonyK
  • 64,559
  • 5
    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. – Noah Schweber Apr 26 '19 at 14:13
  • 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. – Stephen S Apr 26 '19 at 14:13
  • @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. – TonyK Apr 26 '19 at 14:14
  • 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). – Stephen S Apr 26 '19 at 14:16
  • @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. – TonyK Apr 26 '19 at 14:23
  • If neither group adds up to more than 50%, they all declare themselves offline. For instance, if there are 3 locations with 3 servers each, if the entire internet goes down, each location has 3 servers that talk to each other, add up their weights, and realize they don't have a quorum. It's ok to have no quorum. If, however, one datacenter loses internet, the other two are still online. Each server does know about the other servers; what they don't know is if that server is offline, or if they themselves are offline. That's what the quorum computation is designed to determine. – Stephen S Apr 26 '19 at 14:26
  • In addition, I'm working with software already created. Your solution would probably work in a new implementation of other software, having a server randomly selected to be tie-breaker, and a new one is selected if that one goes offline. But the software I'm using doesn't have that dynamic ability. – Stephen S Apr 26 '19 at 15:45
  • @StephenSchrauger excuse me if this is a dumb question. What you're doing sounds really interesting. One thing I don't understand is why you need weights at all? Can't they just know that they are in communication with > 50% of the available servers and make the determination that way? – user875234 Apr 26 '19 at 16:23
  • @user875234 See this page on weighted clusters. Servers can join and leave gracefully, but when one or more unexpectedly lose communication, all servers try to figure out if they have 50%. If they have less or exactly 50%, both sides go still offline, but at exactly 50% the more effective solution is to allow one side to continue operating. They can't both continue operating (as that would fork the data set and would require manual work to merge together). – Stephen S Apr 26 '19 at 17:46
  • @StephenSchrauger - OK, but what do you gain from adding different weights to the servers? The page says that you can do it, but doesn't say why you shoud do it. – Vilx- Apr 26 '19 at 20:38
-1

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.

EvilSnack
  • 277
  • 1
    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. – Daniel Wagner Apr 27 '19 at 03:17