Is there a way to generate a list of distinct numbers such that no two subsets ever have an equal sum?Proving the product of two real numbers is maximum when the numbers are equal given their sum is constantLargest number of pairs that can be added while keeping the population at least 60% maleAmong any $2000$ distinct real numbers there are $a,b,c,d$ such that $|(a-b)/(c-d)-1|<10^-5$Proof that sum of two inequalities (with same direction of the sign) holds for positive numbersDo there exist several positive real numbers such that their sum is $1$ and sum of their squares is less than $0.01$Find two fractions such that their sum added to their product equals $1$Prove that there are four distinct real number $x,y,z,w$,such $|xz+yw|ge |sqrt5(xw-yz)|$Do there exist real numbers such that the following inequality is violated?Integers inequalityHow to prove that $1 + a + 4 sqrt1+a^2 + b^2 leq 4 sqrt1+a^2 + sqrta^2+b^2 + sqrt1+b^2 + 2b $ for $a, b > 0$?
What causes platform events to fail to be published and should I cater for failed platform event creations?
Check if a string is entirely made of the same substring
Checks user level and limit the data before saving it to mongoDB
Did the BCPL programming language support floats?
On The Origin of Dissonant Chords
Can't get 5V 3A DC constant
What makes accurate emulation of old systems a difficult task?
How would 10 generations of living underground change the human body?
Contradiction proof for inequality of P and NP?
Can I criticise the more senior developers around me for not writing clean code?
How do I deal with a coworker that keeps asking to make small superficial changes to a report, and it is seriously triggering my anxiety?
Is there a way to generate a list of distinct numbers such that no two subsets ever have an equal sum?
Could the terminal length of components like resistors be reduced?
A Note on N!
What happens to Mjolnir (Thor's hammer) at the end of Endgame?
Does tea made with boiling water cool faster than tea made with boiled (but still hot) water?
How does Captain America channel this power?
What happens in the secondary winding if there's no spark plug connected?
What term is being referred to with "reflected-sound-of-underground-spirits"?
Dynamic SOQL query relationship with field visibility for Users
Is it idiomatic to construct against `this`
Do I have an "anti-research" personality?
Is the claim "Employers won't employ people with no 'social media presence'" realistic?
How to have a sharp product image?
Is there a way to generate a list of distinct numbers such that no two subsets ever have an equal sum?
Proving the product of two real numbers is maximum when the numbers are equal given their sum is constantLargest number of pairs that can be added while keeping the population at least 60% maleAmong any $2000$ distinct real numbers there are $a,b,c,d$ such that $|(a-b)/(c-d)-1|<10^-5$Proof that sum of two inequalities (with same direction of the sign) holds for positive numbersDo there exist several positive real numbers such that their sum is $1$ and sum of their squares is less than $0.01$Find two fractions such that their sum added to their product equals $1$Prove that there are four distinct real number $x,y,z,w$,such $|xz+yw|ge |sqrt5(xw-yz)|$Do there exist real numbers such that the following inequality is violated?Integers inequalityHow to prove that $1 + a + 4 sqrt1+a^2 + b^2 leq 4 sqrt1+a^2 + sqrta^2+b^2 + sqrt1+b^2 + 2b $ for $a, b > 0$?
$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.
inequality
asked 7 hours ago
Stephen SchraugerStephen Schrauger
1404
$endgroup$
add a comment |
$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.
inequality
asked 7 hours ago
Stephen SchraugerStephen Schrauger
1404
$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
2 hours ago
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
2 hours ago
add a comment |
$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.
inequality
asked 7 hours ago
Stephen SchraugerStephen Schrauger
1404
$endgroup$
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.
inequality
inequality
asked 7 hours ago
Stephen SchraugerStephen Schrauger
1404
asked 7 hours ago
Stephen SchraugerStephen Schrauger
1404
edited 4 hours ago
Stephen Schrauger
asked 7 hours ago
Stephen SchraugerStephen Schrauger
1404
asked 7 hours ago
Stephen SchraugerStephen Schrauger
1404
asked 7 hours ago
Stephen SchraugerStephen Schrauger
1404
1404
$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
2 hours ago
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
2 hours ago
add a comment |
$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
2 hours ago
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
2 hours ago
$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
2 hours ago
$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
2 hours ago
1
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
2 hours ago
$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
2 hours ago
add a comment |
3 Answers
3
active
oldest
votes
$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.
answered 7 hours ago
Ethan BolkerEthan Bolker
46.9k555122
$endgroup$
2
$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
6 hours ago
$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
6 hours ago
$begingroup$
Am I missing something, or does this not allow for adding servers to the pool in the future?
$endgroup$
– Servaes
5 hours ago
$begingroup$
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.
$endgroup$
– Acccumulation
2 hours ago
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
59 mins ago
|
show 3 more comments
$begingroup$
If the weights needn't be integer, you can choose them from the set
$$left1+frac1sqrt p:ptext primeright$$
answered 7 hours ago
ajotatxeajotatxe
54.5k24090
$endgroup$
add a comment |
$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?
answered 7 hours ago
TonyKTonyK
44.2k358137
$endgroup$
3
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
|
show 5 more comments
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3203325%2fis-there-a-way-to-generate-a-list-of-distinct-numbers-such-that-no-two-subsets-e%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
answered 7 hours ago
Ethan BolkerEthan Bolker
46.9k555122
$endgroup$
2
$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
6 hours ago
$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
6 hours ago
$begingroup$
Am I missing something, or does this not allow for adding servers to the pool in the future?
$endgroup$
– Servaes
5 hours ago
$begingroup$
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.
$endgroup$
– Acccumulation
2 hours ago
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
59 mins ago
|
show 3 more comments
$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.
answered 7 hours ago
Ethan BolkerEthan Bolker
46.9k555122
$endgroup$
2
$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
6 hours ago
$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
6 hours ago
$begingroup$
Am I missing something, or does this not allow for adding servers to the pool in the future?
$endgroup$
– Servaes
5 hours ago
$begingroup$
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.
$endgroup$
– Acccumulation
2 hours ago
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
59 mins ago
|
show 3 more comments
$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.
answered 7 hours ago
Ethan BolkerEthan Bolker
46.9k555122
$endgroup$
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.
answered 7 hours ago
Ethan BolkerEthan Bolker
46.9k555122
edited 7 hours ago
answered 7 hours ago
Ethan BolkerEthan Bolker
46.9k555122
answered 7 hours ago
Ethan BolkerEthan Bolker
46.9k555122
answered 7 hours ago
Ethan BolkerEthan Bolker
46.9k555122
46.9k555122
2
$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
6 hours ago
$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
6 hours ago
$begingroup$
Am I missing something, or does this not allow for adding servers to the pool in the future?
$endgroup$
– Servaes
5 hours ago
$begingroup$
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.
$endgroup$
– Acccumulation
2 hours ago
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
59 mins ago
|
show 3 more comments
2
$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
6 hours ago
$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
6 hours ago
$begingroup$
Am I missing something, or does this not allow for adding servers to the pool in the future?
$endgroup$
– Servaes
5 hours ago
$begingroup$
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.
$endgroup$
– Acccumulation
2 hours ago
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
59 mins ago
2
2
$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
6 hours ago
$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
6 hours ago
$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
6 hours ago
$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
6 hours ago
$begingroup$
Am I missing something, or does this not allow for adding servers to the pool in the future?
$endgroup$
– Servaes
5 hours ago
$begingroup$
Am I missing something, or does this not allow for adding servers to the pool in the future?
$endgroup$
– Servaes
5 hours ago
$begingroup$
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.
$endgroup$
– Acccumulation
2 hours ago
$begingroup$
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.
$endgroup$
– Acccumulation
2 hours ago
1
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
59 mins ago
$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
59 mins ago
|
show 3 more comments
$begingroup$
If the weights needn't be integer, you can choose them from the set
$$left1+frac1sqrt p:ptext primeright$$
answered 7 hours ago
ajotatxeajotatxe
54.5k24090
$endgroup$
add a comment |
$begingroup$
If the weights needn't be integer, you can choose them from the set
$$left1+frac1sqrt p:ptext primeright$$
answered 7 hours ago
ajotatxeajotatxe
54.5k24090
$endgroup$
add a comment |
$begingroup$
If the weights needn't be integer, you can choose them from the set
$$left1+frac1sqrt p:ptext primeright$$
answered 7 hours ago
ajotatxeajotatxe
54.5k24090
$endgroup$
If the weights needn't be integer, you can choose them from the set
$$left1+frac1sqrt p:ptext primeright$$
answered 7 hours ago
ajotatxeajotatxe
54.5k24090
edited 7 hours ago
answered 7 hours ago
ajotatxeajotatxe
54.5k24090
answered 7 hours ago
ajotatxeajotatxe
54.5k24090
answered 7 hours ago
ajotatxeajotatxe
54.5k24090
54.5k24090
add a comment |
add a comment |
$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?
answered 7 hours ago
TonyKTonyK
44.2k358137
$endgroup$
3
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
|
show 5 more comments
$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?
answered 7 hours ago
TonyKTonyK
44.2k358137
$endgroup$
3
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
|
show 5 more comments
$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?
answered 7 hours ago
TonyKTonyK
44.2k358137
$endgroup$
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?
answered 7 hours ago
TonyKTonyK
44.2k358137
edited 7 hours ago
answered 7 hours ago
TonyKTonyK
44.2k358137
answered 7 hours ago
TonyKTonyK
44.2k358137
answered 7 hours ago
TonyKTonyK
44.2k358137
44.2k358137
3
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
|
show 5 more comments
3
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
3
3
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
$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
7 hours ago
|
show 5 more comments
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3203325%2fis-there-a-way-to-generate-a-list-of-distinct-numbers-such-that-no-two-subsets-e%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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
2 hours ago
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
2 hours ago