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$?
If Melisandre foresaw another character closing blue eyes, why did she follow Stannis?
Stark VS Thanos
Pressure to defend the relevance of one's area of mathematics
Does higher resolution in an image imply more bits per pixel?
Was Unix ever a single-user OS?
You look catfish vs You look like a catfish?
Selecting a secure PIN for building access
How to efficiently calculate prefix sum of frequencies of characters in a string?
Can commander tax be proliferated?
Does the Darkness spell dispel the Color Spray and Flaming Sphere spells?
Disabling Resource Governor in SQL Server
Why do money exchangers give different rates to different bills
What are the spoon bit of a spoon and fork bit of a fork called?
Applying a function to a nested list
Visa for volunteering in England
Can I use 1000v rectifier diodes instead of 600v rectifier diodes?
Field Length Validation for Desktop Application which has maximum 1000 characters
Can a cyclic Amine form an Amide?
Why is this a valid proof for the harmonic series?
Is it cheaper to drop cargo than to land it?
Is Cola "probably the best-known" Latin word in the world? If not, which might it be?
My ID is expired, can I fly to the Bahamas with my passport
Write to EXCEL from SQL DB using VBA script
Transfer over $10k
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 Apr 26 at 13:57
Stephen SchraugerStephen Schrauger
1485
$endgroup$
|
show 3 more comments
$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 Apr 26 at 13:57
Stephen SchraugerStephen Schrauger
1485
$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
|
show 3 more comments
$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 Apr 26 at 13:57
Stephen SchraugerStephen Schrauger
1485
$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 Apr 26 at 13:57
Stephen SchraugerStephen Schrauger
1485
asked Apr 26 at 13:57
Stephen SchraugerStephen Schrauger
1485
edited Apr 26 at 17:50
Stephen Schrauger
asked Apr 26 at 13:57
Stephen SchraugerStephen Schrauger
1485
asked Apr 26 at 13:57
Stephen SchraugerStephen Schrauger
1485
asked Apr 26 at 13:57
Stephen SchraugerStephen Schrauger
1485
1485
$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
|
show 3 more comments
$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
$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
$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
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$
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$
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 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
$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
|
show 3 more comments
4 Answers
4
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 Apr 26 at 14:18
Ethan BolkerEthan Bolker
47.1k555123
$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
|
show 9 more comments
$begingroup$
If the weights needn't be integer, you can choose them from the set
$$left1+frac1p:ptext primeright$$
answered Apr 26 at 14:05
ajotatxeajotatxe
54.7k24090
$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
yesterday
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 Apr 26 at 14:12
TonyKTonyK
44.4k358137
$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
|
show 5 more comments
$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.
answered Apr 27 at 1:40
EvilSnackEvilSnack
992
$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
add a comment |
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
4 Answers
4
active
oldest
votes
4 Answers
4
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 Apr 26 at 14:18
Ethan BolkerEthan Bolker
47.1k555123
$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
|
show 9 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 Apr 26 at 14:18
Ethan BolkerEthan Bolker
47.1k555123
$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
|
show 9 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 Apr 26 at 14:18
Ethan BolkerEthan Bolker
47.1k555123
$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 Apr 26 at 14:18
Ethan BolkerEthan Bolker
47.1k555123
edited Apr 26 at 14:29
answered Apr 26 at 14:18
Ethan BolkerEthan Bolker
47.1k555123
answered Apr 26 at 14:18
Ethan BolkerEthan Bolker
47.1k555123
answered Apr 26 at 14:18
Ethan BolkerEthan Bolker
47.1k555123
47.1k555123
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
|
show 9 more comments
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
3
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$
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$
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
$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
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
$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
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
$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
|
show 9 more comments
$begingroup$
If the weights needn't be integer, you can choose them from the set
$$left1+frac1p:ptext primeright$$
answered Apr 26 at 14:05
ajotatxeajotatxe
54.7k24090
$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
yesterday
add a comment |
$begingroup$
If the weights needn't be integer, you can choose them from the set
$$left1+frac1p:ptext primeright$$
answered Apr 26 at 14:05
ajotatxeajotatxe
54.7k24090
$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
yesterday
add a comment |
$begingroup$
If the weights needn't be integer, you can choose them from the set
$$left1+frac1p:ptext primeright$$
answered Apr 26 at 14:05
ajotatxeajotatxe
54.7k24090
$endgroup$
If the weights needn't be integer, you can choose them from the set
$$left1+frac1p:ptext primeright$$
answered Apr 26 at 14:05
ajotatxeajotatxe
54.7k24090
edited yesterday
answered Apr 26 at 14:05
ajotatxeajotatxe
54.7k24090
answered Apr 26 at 14:05
ajotatxeajotatxe
54.7k24090
answered Apr 26 at 14:05
ajotatxeajotatxe
54.7k24090
54.7k24090
$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
yesterday
add a comment |
$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
yesterday
$begingroup$
Why bother taking the square root? (For that matter, why bother adding 1?)
$endgroup$
– Daniel Wagner
Apr 27 at 3:14
$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
yesterday
$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
yesterday
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 Apr 26 at 14:12
TonyKTonyK
44.4k358137
$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
|
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 Apr 26 at 14:12
TonyKTonyK
44.4k358137
$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
|
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 Apr 26 at 14:12
TonyKTonyK
44.4k358137
$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 Apr 26 at 14:12
TonyKTonyK
44.4k358137
edited Apr 26 at 14:13
answered Apr 26 at 14:12
TonyKTonyK
44.4k358137
answered Apr 26 at 14:12
TonyKTonyK
44.4k358137
answered Apr 26 at 14:12
TonyKTonyK
44.4k358137
44.4k358137
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
|
show 5 more comments
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
5
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$
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$
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$
@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$
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
$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
|
show 5 more comments
$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.
answered Apr 27 at 1:40
EvilSnackEvilSnack
992
$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
add a comment |
$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.
answered Apr 27 at 1:40
EvilSnackEvilSnack
992
$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
add a comment |
$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.
answered Apr 27 at 1:40
EvilSnackEvilSnack
992
$endgroup$
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.
answered Apr 27 at 1:40
EvilSnackEvilSnack
992
answered Apr 27 at 1:40
EvilSnackEvilSnack
992
answered Apr 27 at 1:40
EvilSnackEvilSnack
992
answered Apr 27 at 1:40
EvilSnackEvilSnack
992
992
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
add a comment |
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
1
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
$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
add a comment |
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
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