Типы и Архетипы

[вторник] Голый король и два генерала Стандартная загадка: на неком острове у части жителей голубые глаза. Каждый видит цвет глаз всех остальных, но не свой и кто понял, что у него голубые глаза, на следующее утро уезжает. Голубоглазых ровно k и k >= 2, значит, каждый из них и так видит вокруг другие голубые глаза. Все знают, что голубоглазые есть, но годами ничего не происходит. Приезжает гость и при всех говорит: "Здесь есть голубоглазый". Он не сказал ничего нового, все это и так видели. Но на k-е утро ровно k человек собирают вещи и уезжают. Но как объявление давно известного факта меняет поведение? Всё дело в лестнице знания, есть факт X, есть "я знаю X". Есть "все знают X" - это взаимное знание, mutual knowledge. А есть цепочка "все знают, что все знают, что все знают…" - вот её целиком и иногда называют общим знанием. Само понятие вроде введено Lewis в 1969, переиспользовано Aumann в теории игр в 1976, а в распределёнку его перенесли Halpern и Moses. До гостя факт был взаимным знанием высокого порядка, но башня где-то наверху обрывалась. Объявление при всех замкнуло её до бесконечности и синхронизировало отсчёт дней, ну и дальше индукция: будь голубоглазый один, он увидел бы вокруг только не-голубоглазых и уехал бы в первое утро. При k каждый видит k−1 и рассуждает: "если бы их было k−1, они уехали бы на (k−1)-е утро, не уехали - значит лишний это я". Все k уезжают на k-е. В последнее время мы говорили про детекторы, про то, что нужно добавить системе, чтобы она договорилась. А общее знание похожее, это тоже своего рода детектор, но он про границу, про ресурс одновременности, произвести который очень дорого. Точно такая же логика в задаче двух генералов: атаковать двум генерадам надо одновременно, а договориться можно только гонцом через долину с врагом, соответственно, гонец может не дойти, нужно подтверждение. Но и гонец с подтверждением может не дойти - нужно подтверждение подтверждения. Последнее сообщение в цепочке всегда ненадёжно, сколько ни посылай гонцов. Это и доказали Halpern и Moses (JACM, 1990): общее знание достижимо только через одновременное публичное событие, которое все наблюдают и наблюдают, что наблюдают другие. Досылкой по ненадёжному каналу такого не достичь, если ослабить требование, то получим ровно настолько же ослабленную координацию. Эта проблема и интуиция применима не только в распределёнке. Например, в "Голом короле" каждый видит, что король гол, каждый против. Но это взаимное знание, не общее: я не знаю, что и ты знаешь, что знают все. Общее знание нельзя построить из сообщений, его надо синтезировать одновременным публичным событием, которое все наблюдают и видят, что видят другие. Общества изобрели для этого ритуалы: свадебное "говорите сейчас или молчите вовек", коронация, городской глашатай, площадь. И тут как раз блокчейн можно воспринимать как способ производства этого общего знания, инженерную "городскую площадь". "Все знают, что все знают, ... , что транзакция пришла", из-за этого важны финальность и публичный порядок, поэтому консенсус дорог, это синтез того самого одновременного публичного события, которое, по Halpern-Moses, сообщениями не достаётся. Стоимость консенсуса = цена производства общего знания. Итог Если общее знание нельзя досылать, а можно только синтезировать одновременным событием, - то всё, что мы строим, от площади до реестра, это машины одного класса. И тогда: что в вашей системе играет роль общего синхронизирующего события и кто за это платит?