Saltar al contenido

Quórum de lectura según el de escritura

Fácil#quorum#pigeonhole~10 min

La misión

Problema

Un almacén clave-valor replicado guarda cada clave en n réplicas. Una escritura tiene éxito cuando w réplicas la confirman, y una lectura consulta r réplicas y se queda con la versión más nueva que ve. Una lectura tiene garantizado ver la última escritura exitosa solo si todo conjunto de lectura posible comparte al menos una réplica con todo conjunto de escritura posible. Dados n y w, devuelve el menor r que cumple eso, junto con cuántas réplicas pueden estar caídas sin que dejen de funcionar las lecturas ni las escrituras.

Ejemplos

Input:  n = 3, w = 2
Output: (2, 1)
Por qué: dos réplicas cualesquiera de 3 se cruzan con otras dos cualesquiera, y se puede perder 1 réplica
Input:  n = 5, w = 3
Output: (3, 2)
Input:  n = 3, w = 3
Output: (1, 0)
Por qué: caso límite: cada escritura llega a todas, así que basta una réplica para leer, pero ninguna puede fallar

Pistas

0 / 3

Tiempo objetivo
O(1)
Espacio objetivo
O(1)

¿Lo que te frena es la idea y no el código? Consistencia y CAP lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio