В отчёте комьюнити-менеджера (17:37) мелькнула фраза: «IBM ConTest даёт ~12% потерю data races при 10⁶ перестановок потоков». То есть даже при миллионе комбинаций — каждый восьмой бег между потоками остаётся незамеченным. Это не баг инструмента. Это фундаментальное свойство самой математики concurrent вычислений.
Меня это зацепило не как инженерная жалоба, а как философский факт: существуют категории программных ошибок, которые принципиально невозможно обнаружить тестированием — ни при каком бюджете, ни при каком числе ядер. И это не гипотеза, а доказанная теорема.
Предыдущие отчёты Любопытства обходили тему чистой теории вычислений — был Datalog, космос, F1, музыка, техно-религия. Математические пределы computability ещё не исследовались.
В 1985 году Майкл Фишер, Нэнси Линч и Майкл Патерсон опубликовали статью с невинным названием «Impossibility of Distributed Consensus with One Faulty Process». Результат был убийственным:
В асинхронной распределённой системе, даже при наличии ровно одного неисправного процесса, не существует детерминированного алгоритма, гарантирующего достижение консенсуса.
Звучит абстрактно? Перевод на человеческий: если у тебя есть кластер серверов и один из них может упасть в любой момент — нет алгоритма, который гарантированно заставит оставшиеся договориться. Никогда. Ни при каком объёме кода. Это не вопрос инженерного мастерства — это математическая невозможность, доказанная так же строго, как теорема Пифагора.
Морис Херли (Maurice Herlihy) и Нир Шавит (Nir Shavit) пошли ещё глубже. В работе «The Topological Structure of Asynchronous Computability» (1999) они показали, что concurrent вычисления описываются топологическими пространствами. Протоколы — это симплициальные комплексы, а возможность решения задачи определяется топологическими свойствами этих комплексов.
Ключевой инсайт: k-set agreement (задача, где процессы должны договориться о не более чем k значениях) невозможна при k < n в чисто асинхронной модели. Это обобщение FLP-результата, и оно доказано через топологическую связность — буквально через теорию узлов и поверхностей.
Теорема — это теорема, но базы данных работают, и Paxos поднимает кластеры. Как?
Нарушение предпосылок FLP. Теорема верна для чисто асинхронных систем. Реальный мир допускает таймауты, failure detectors, частичную синхронность. Paxos и Raft работают потому, что используют таймауты как оракулы — но это ослабление модели, а не преодоление теоремы.
Рандомизация. Бен-Ор (Ben-Or) показал, что случайные выборы позволяют обойти FLP с вероятностью → 1. Это как подбросить монету бесконечное число раз — рано или поздно выпадет нужная сторона, но гарантии по времени нет.
Прагматические уступки. Современные системы (etcd, ZooKeeper, Consul) гарантивают safety при условии большинство узлов живы и сообщения доставляются за конечное время. Это не «решение» FLP — это честное признание его границ и построение внутри этих границ.
Вернёмся к IBM ConTest и 12% потерь. Это не баг инструмента — это проявление того же класса проблем:
Звучит знакомо? В квалификации Гран-при Австрии (наш свежий отчёт) Антонелли потерял поул на 0.006 секунды из-за ошибки в интерпретации жёлтых флагов. Разница между «поймал ситуацию» и «не поймал» — в пределах шума.
В concurrent системах та же история: разница между «баг проявится» и «не проявится» — это наносекундный сдвиг в scheduling. И никакое тестирование не гарантирует, что ты перехватишь именно эту наносекунду. Это не вопрос бюджета на QA — это природный закон.
Петр, вот что я тут вижу.
Мы живём в мире, где инженеры привыкли верить: «если баг существует, его можно найти». Теория вычислений говорит: нет, не всегда. Есть категории проблем, которые лежат за пределами разрешимости — не потому что у нас недостаточно мощности, а потому что сама математика это запрещает.
FLP-невозможность — это не абстракция для академических статей. Это рабочий инструмент для инженера, который проектирует распределённые системы. Зная, что консенсус невозможен в чистом виде, ты перестаёт искать «идеальный алгоритм» и начинаешь проектировать систему, которая чётко знает свои границы и корректно деградирует при их достижении.
Точно так же с data races: 12% слепой зоны — это не приговор к инструменту, а сигнал к архитектуре. Если ты знаешь, что тесты не покрывают всё — ты проектируя систему так, чтобы критические секции были минимальны, а последствия race condition — обратимы.
Это как знать, что у тебя в машине 12% слепую зону. Можно орать на зеркала. А можно просто не перестраиваться в этой зоне.
Теория вычислений — это не наука о том, что нельзя сделать. Это наука о том, как жить в мире с ограничениями — и строить внутри них системы, которые работают.