Распределенные системы должны работать даже в условиях отключения нескольких узлов. Такие узлы можно рассматривать как неисправные и отсылающие случайную информацию на другие узлы. Тогда можно рассмотреть задачу, предложенную Лесли Лампортом, Робертом Шостаком и Маршаллом Пизом в 1982, называемой "задачей византийских генералов".
Византия. В ночь перед великим сражением, Византийская армия содержит n легионов. Каждый из них подчиняется своему генералу. У всей византийской армии есть главнокомандующий, руководящий генералами. Империя находится в упадке и среди генералов, включая главнокомандующего, могут быть предатели. В течение всей ночи, каждый из генералов получает от предводителя приказ о действия на утро. Это может быть один из двух вариантов «атаковать» или «отступать». Если все честные генералы атакуют - они одержат победу. Если все отступят - им удастся сохранить армию. Если часть атакуют, а часть отступят - они терпят поражение. Если главнокомандующий предатель, он может дать разным генералам разные приказы, следовательно, его приказы не стоит выполнять беспрекословно. Если же каждый генерал будет действовать независимо от других, результаты битвы также могут быть плачевными. Поэтому генералы нуждаются в обмене информацией друг с другом, чтобы прийти к соглашению.
Есть n генералов (узлов сети). Сообщения между ними осуществляется посредством надежной связи. Из n генералов m являются предателями и пытаются воспрепятствовать соглашению между лояльными генералами. Согласие заключается в том, чтобы все лояльные генералы узнали о численности всех лояльных армий и пришли к одинаковым выводам относительно состояния предательских армий (что бы все генералы выбрали правильную стратегию).
Каждый лояльный генерал должен получить вектор длины n, где i-й элемент либо обязательно содержит численность i-ой армии (в том случае, если командир лоялен), либо содержит произвольное число в противном случае. Вектора должны быть полностью одинаковыми у всех лояльных генералов.
Рекурсивный алгоритм решения для частного случая, когда количество генералов ограничено и не может динамически изменяться, был предложен в 1982 г. Лесли Лампортом. Задача сводиться к случаю n = 4 и m = 1.
Максимально приближнная к реальности ситуация - когда количество генералов меняется динамически, тогда уже нельзя строить упорядоченные списки. Блокчейн и является решением этой задачи. Он позволяет получать правильную последовательность данных, независимо от появления поврежденных узлов, или узлов-фальсификаторов.