Здравствуйте, Finder_b, Вы писали:

F_>Применив ко множеству всех входных сообщений, актор G находящий в начальном состоянии s0. Мы получим множество состояний S1 достижимых на первом шаге ленты. Мы можем представить их в виде направленного графа состоящего из дуг (s0, G(s0,t)). Продолжая процесс рекурсивно бесконечное число раз, мы получим направленный слабый граф всех достижимых состояний SR (state, reachable) информационной системы G. Все возращённые в ходе обхода графа ответы являются множеством достижимых ответов RR. Мы будем рассматривать только детерминированные актёры, у которых мощность множества RR меньше максимальной комбинаторной мощьности Q (=Σ(i=1..|Q|) |Q|!*|Q-i|/i!*(|Q|-i)!), для |Q|=2 |RR|<=5. Используя цепи Маркова и зная вероятность события E мы можем получить вероятность попадания в каждое состояние sr.
F_>Чтобы проанализировать CAP теорему наложим на нашу систему следующие ограничения. Для простоты, число возможных запросов пользователя, то есть мощность множества Q двумя.
F_>CAP теорема рассматривает только системы в состоянии аварии по разделению. Пути в графе SR где возникала изоляция актора Ai (isolated actor) от как минимум одного актора Ax x ∈ 1, 2, ..,k; x≠i. Тесть значения Lx этих акторов, увеличивалось по сравнению с предыдущим шагом). Назовём такие состояния в SR партиционированными. Все возможные пути, исходящие из партиционированного состояния непрерывно проходящие через состояния, в которых сохранялось партиционирование, назовем партиционированными путями выполнения. Если в течении партиционированного пути выполнения, на актор Ax поступил запрос Q1 и при этом он не поступал ранее, назовем такой путь подчиняющимся CAP теореме или CAP путем. Если на пути подчиняющимся CAP теореме любой из актеров возвратил ответ R связанный с запросом Q1 то такой путь мы будем называть путем где сохранилась доступность. Коэффициент доступности будет равен суммарной вероятности попадания на пути где сохранилась доступность по отношению суммарной вероятности попадания на CAP путь. Если мощность RR на всех путях, исходящих из SR принадлежащего CAP пути меньше пяти то такой CAP путь мы будем называть консистентным.
Не вполне понял, откуда взялась константа 5.
F_>Это возможно если запросы Q1 и Q2 обрабатывались акторами в одном порядке, или запросы не связаны (результат не зависит от порядка их обработки). Коэффициент консистентной равен суммарной вероятности попадания на консистентные пути по отношению к общей вероятности попадания на CAP путь. Коэффициент устойчивости разделению – это средний процент узлов, которые были доступны, в путях где сохранилась доступность. Легко проверить численными методами что для любого конечного автомата, у которого операции связаны (результат операций зависит от последовательности их поступления) сумма коэффициентов меньше или равна двум.
Интересный подход. Что-то подобное, кмк, я встречал в работах по распределённым алгоритмам.
Сходу не соображу, как его применить — реальные системы имеют довольно-таки большое пространство состояний; как за обозримое время выполнить предлагаемую вами свёртку мне непонятно.
Я попробовал другой подход — берём метрику согласованности, которая специфична для нашей прикладной задачи; берём модель кластера, которая реализует точный или "оптимистичный" вариант консенсуса. Берём псевдослучайное расписание сбоев (разделений сети). Берём некий набор клиентских запросов — и смотрим, как ведёт себя система, путём выполнения относительно большого количества экспериментов.

F_>Тут наверняка есть куча косяков. Так как люди, которые могу написать такое определение правильно, работают в гугле за много бабок, а не формочки в банке клепают. Но у меня есть железная отмазка. Я писал это доказательство в пятницу вечером . А последнюю его часть вообще глубокой ночью. Но буду благодарен за указания на эти косяки.

F_>PS Из такого определения следует несколько важных выводов. Первый что если запросы пользователя не взаимодействую, или можно сделать чтобы они не взаимодействовали на каком-то отрезке графа, то мы можем получить все три буквы СAP. Кап теорема вообще не применима к системам со случайным поведением. Оба этих свойства очень интересны с точки зрения проектирования криптовалют третьего поколения.
Тут не всегда легко понять, где взаимодействуют, а где — нет.
Ну, вот например запрос на пополнение счёта никак не зависит от всех предыдущих запросов, поэтому его не обязательно обрабатывать через кворум. Чисто так, достаточно подтверждения от небольшого количества узлов, чтобы избежать потери durability при необратимом сбое носителя.
А вот запросы на списание сильно зависят от всех предыдущих запросов. При разделении сети можно легко получить несколько историй, которые локально корректны, но при слиянии нарушают согласованность.
Запросы на списание/пополнение разных счетов в целом коммутативны; но они могут стать некоммутативными, если мы включим в транзакцию перевод с одного счёта на другой.