@EverOne
R&D Management since 2011

Как обеспечить избыточную целостность?

Пытаемся с коллегами найти решение логической задачи, уже, если честно, нет уверенности что оно есть.
Итак задача:

Есть 1000 заключенных, и есть числа от 1 до 1000, которым присвоено собственное значение. Например:
1 = 0f88Hs
2 = UdD16j
3 = NkP4V4
4 = bRKitt
5 = 3rLqBA
6 = 5gH6LE
7 = 0wrICY
8 = 58CEoM
9 = 1oCn43
...
1000 = Id2401

Каждый заключенный знает свою пару [ число = значение ] и пару предыдущего, как минимум. Но еще он может запомнить N-ное количество случайных пар (или не случайных, по договоренности).
Утром придут надзиратели и уведут заключенных - случайное количество (до 75%, то есть может остаться 250 человек, а может и 500) случайных заключенных. Например, на расстрел. Количество и порядок неизвестен.
Итак, вопрос: каково минимальное количество пар и по какому алгоритму должен запомнить каждый заключенный для гарантированного восстановления последовательности значений? Как изменится этот алгоритм если уведут 90% заключенных или только 25%? Как равномерно перераспределить нагрузку если к имеющейся 1000 добавят еще 1000, а чисел останется столько же, просто два заключенных будут помнить одно и то же число?
  • Вопрос задан
  • 399 просмотров
Пригласить эксперта
Ответы на вопрос 4
chupasaurus
@chupasaurus
Сею рефлекторное, злое, временное
Дополню Deerenaros : Оптимальное решение - Folded Reed—Solomon Code, который к тому же подозрительно похож на условие задачи. С использованием этого алгоритма каждому заключённому необходимо запомнить помимо своего O(1/ε) частей кода, где ε - отношение остающихся заключенных к общему, 1/ε округляем вверх для необходимой избыточности.
Как оно работает - из исходных пар составляется код Рида-Соломона размером 1000*(1+O(1/ε)) букв (размер буквы в битах исходя из размера данных, присваемых числах, в задаче это 6 бит), каждый заключенный помимо исходной пары со своим номером запоминает части кода на местах 1000εn ... 1000ε(n+1)-1, n - свой номер. Минимальная выборка в виде заключенных с номерами 1..1000ε даст 1000ε своих пар, 1000 кусков кода и пару 1000-го, что больше минимально необходимых 1000ε+1.
В изначальном варианте: ε=¼, О(1/ε)=4, код размером 1000*(1+4)=5000 букв, устойчивость FRS-кода - до n*(1-ε)-1=3999 потерь, тогда как мы теряем только 3749. Для ε=⅒ им придётся запоминать 10 кусков кода, для ε=¾ - один (как и для ∀ε>½). Если количество заключенных увеличить, то пусть заключенные с одинаковыми номерами будут запоминать разные части кода: например один как уже определили, второй со сдвигом на 10 от своего номера; в таком случае код можно поровну распределить на всех и число частей для запоминания уменьшится нацело вдвое.
Ответ написан
Комментировать
Deerenaros
@Deerenaros
Программист, математик, задрот и даже чуть инженер
Эм, так вам избыточные коды. Рида-Соломона, например. Или каскадные, они более гибкие.
Ответ написан
Вместо «заключённых» мне проще представлять жесткие диски, флешки или абстрактные контейнеры с данными.

Для проверки на устойчивость будем рассматривать наихудшую ситуацию намеренного удаления злыми «наздирателями» комбинации контейнеров, приносящей гарантированный урон целостности.

В каждом хранится «своё» значение + 1 значение из «предыдущего». На деле, неважно, какого именно, т.к. последовательность их более никак не играет. В этой ситуации гарантировано сохранение данных только при удалении 1 единственного контейнера. Т.к. вторым непременно выберем тот, что хранит избыточно данные первого.

Удаляем N контейнеров. Цель – начисто удалить данные хотя бы одного. Т.е. выбираем все те, кто хранит избыточно данные этого «избранного».

Единственный вариант защититься – хранить избыточно в N+1 контейнерах. Вернее, число копий каждой единицы данных должно быть на 1 больше потенциально удаляемых. По алгоритму не усложняя можно хрниать в N следующих.
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Располагаем всю последовательность (1-1000) в кольцо.
Допустим, хотим запас прочности: 2.
Затем, делим это кольцо пополам и каждый X запоминает диаметральное значение:
1 => 1, 500
2 => 2, 501
и т.д.

Запас прочности 3:
1 => 1, 333, 666
2 => 2, 334, 667
и т.д.

Чтобы уменьшить объём хранимой информации, можно прибегнуть к энтропийному кодированию.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы