Как синхронизировать работу сети независимых серверов, если известно, что некоторые из них могут сломаться или быть захвачены хакерами, посылающими ложную информацию? Эта проблема является главным вызовом при проектировании отказоустойчивых баз данных, сетей блокчейн и бортовых компьютеров космических кораблей. В 1982 году Лесли Лампорт математически формализовал эту проблему в виде знаменитой «Задачи византийских генералов».

В классическом императивном программировании изменение переменной или узла в дереве безвозвратно уничтожает старое значение. Если вам нужно отменить действие (Ctrl+Z), вам приходится заранее сохранять копию всей структуры, что катастрофически расходует оперативную память. В функциональном программировании и математической логике мутации запрещены. Для решения проблемы эффективного хранения истории изменений были придуманы персистентные структуры данных.

Ранее мы выяснили, что если задача может быть математически описана структурой матроида (как задача о минимальном остовном дереве), то для ее идеального решения достаточно использовать самый банальный Жадный алгоритм. Однако в реальном мире, при составлении сложных расписаний инженерам часто приходится сталкиваться с ограничениями, поступающими сразу из нескольких разных систем правил. Как оптимизировать решение, удовлетворяющее сразу двум матроидам?