¿Existe una forma de generar una lista de números distintos de manera que ningún subconjunto tenga una suma igual?

Question

Estoy tratando de encontrar una manera de asignar pesos a un grupo de servidores (un grupo de galera de servidores de bases de datos), y quiero poder calcular siempre un quórum, lo que significa que nunca se debe permitir que ningún conjunto de pesos sume exactamente el 50% (un quórum en este caso significa más del 50%).

¿Existe una fórmula matemática para generar un conjunto de números (probablemente únicos) de forma que nunca se pueda sumar ningún subconjunto de esos números para que sea igual a cualquier subconjunto de los números restantes? Además, ningún número individual debe ser el doble o más del doble de cualquier otro número.

Por ejemplo, con [3, 4, 5], no hay forma de tomar cualquier conjunto de 1, 2 o 3 de esos para que sumen y sean iguales a cualquier subconjunto de números restantes. Siempre habrá una desigualdad, por lo que se puede calcular un quórum (o se puede determinar que no hay quórum, en el caso de que haya demasiados servidores desconectados entre sí).

Entiendo que es un problema relacionado con la administración del servidor, pero parece ser de naturaleza matemática.

Lo que me gustaría es poder asignar pesos individuales a un grupo inicial de servidores, pero idealmente poder generar otro peso si se añade otro servidor al grupo en el futuro.

La aplicación práctica es que todos los servidores conocen su propio peso, y conocen el peso total de todos los servidores. Si un servidor muere repentinamente, o falla la conectividad entre algunos de ellos, los servidores intentan determinar si tienen quórum. Cada servidor que aún pueda comunicarse con otro sumará sus pesos, y si el total de sus pesos es más que exactamente el 50% del total del conjunto inicial, entonces hay quórum, y esos servidores se declararán como el nuevo grupo canónico. Si no consiguen superar el 50%, no tienen quórum y se declararán desconectados o incapaces de continuar con el servicio.

Answer 1

Para $n$ servidores, considere los pesos $$ 1 + m, 2 + m, 4 + m, \ldots, 2^n + m $$ para $m$ lo suficientemente grande como para que cada uno sea menos del doble de los otros.

La unicidad de las sumas de subconjuntos para subconjuntos de igual tamaño se deduce de la unicidad de las expansiones binarias.

Answer 2

Si los pesos no tienen que ser enteros, puedes elegirlos del conjunto $$\left\{1+\frac1p:p\text{ prime}\right\}$$

Answer 3

¿Quizás estás pensando demasiado en esto? ¿Qué se pierde al considerar que el quórum es simplemente más del 50% de los servidores? Si quieres una forma de desempatar cuando los servidores están divididos en dos grupos de igual tamaño, simplemente nombra un servidor como especial, y toma el grupo que contiene el servidor especial.

¿O me estoy perdiendo algo?

Answer 4

Si "probablemente únicos" resulta ser "en realidad, no, no necesitan ser únicos", entonces ponderar un servidor como 2n+1, y todos los restantes como 2n. Entonces, no importa cómo se elijan los dos grupos, un grupo siempre tendrá una suma impar y los otros siempre tendrán una suma par. Por tanto, las dos sumas nunca serán iguales.