Сообщение Re[7]: Сервисы, передающие изменения другим сервисам и т.д. от 16.04.2022 2:54
Изменено 16.04.2022 9:12 Finder_b
Re[7]: Сервисы, передающие изменения другим сервисам и т.д.
Здравствуйте, Sinclair, Вы писали:
F_>>Но в реальности требуется статически доказать что они действительно 100% CA, так как во всех виденных мной системах была масса не очевидных на первый взгляд путей через граф их состояния, которые приводили к потере либо C либо A. Хотя все такие пути ну очень маловероятны, но их большое количество и склонность корреляции приводили к снижению С и A где-то до 95% от вероятности аварии.
S>Хотелось бы понять, как именно вы придаёте численные значения метрикам С и P.
S>Если с A всё понятно, то что такое C=80%, или P=51%?
Конечно в самой кап теореме этого нет. Поскольку она описывает математическую абстракцию в дискретном мире. Но задачка математически определить эти коэффициенты любопытная. Смог придумать два определения. Одно простое и понятное, но к сожалению, совершенно неправильное и на практике неприменимое. Второе боле-менее правильное и применимое на практике, но немного сложное.
Первое описания: кап теорема описывает абстрактную систему, в которой есть всего одно состояние, и в которой есть всего один тип связи, и которая может сломаться одним единственным способом. Реальная система имеет множество состояний, и много типов связей, которые нарушаются множеством различных способов. Такую систему можно представить, как составленную из множества систем подчиняющихся CAP теореме. Каждая из этих подсистем не обязана вести себя одинаково. Некоторые могут быть AP, некоторые CP, некоторые СА. Так как эти подсистемы взаимодействуют на границе их взаимодействия буду присутствовать системы, имеющие только одну букву. Например, на границе недоступной системы (CP) и некосистентной (АP) будет присутствовать система, которая одновременно недоступна, и некосистентна (только P). Посчитав отношение количества подсистем, которые являются доступными к общему количеству подсистем мы найдем коэффициент A. Также поступим для остальных кофинетов.
Это совершено неправильно с математической точки зрения, зато понятно.
Вот более правильное объяснение, которое еще и практически применимо. Я постарался обойтись только теорией конечных автоматов. Думаю, все программисты ее хорошо знают:
Представим узел нашей системы Ak виде конечного автомата (A: actor), у которого есть множество возможных состояний Sk (S: state). Акторов в системе k=[1.. ∞). На каждом шаге, n, ленты Ak производит символ rk (r: responce) принадлежащий алфавиту (множеству) R ответов пользователю, зависящее только от входящего символа, и текущего состояния rk=f(Sk,ik). Алфавит R включает пустой элемент (r0), который означает что на этом шаге у A нет ответа пользователю. Поскольку мы имеем дело с распределенной системой, то кроме ответов пользователю, A на каждом шаге производит сообщение для каждого k узла системы Mk эти сообщения собраны в упорядоченную последовательность MO=(M1,M2,…, Mk) (кортеж Message Output). Таким образом выходной алфавит A состоит из упорядоченной пары символов (r, MO). Для каждого A существует бесконечный автомат N (N: network). N принимает упорядоченную пару из символов L=[1..∞) (L: Latency) и MO всех A. Nk возвращает символ Mik (message input) который равен кортежу из символов Mk для узла Ak, полученный на шаге n-L. Входящий символ конечного автомата Ak принадлежит алфавиту, представлявшему собой кортеж из трех символов (Mik, qk, ek). Символ q (Q, query) принадлежит алфавиту Q запросов пользователя. Символ e (E: Event) событие которое случилось с нашим актором. Событие принадлежит множеству E состоящему из таких событий как истечение таймаута, перезагрузка информационной системы, изменение настроек узла и т.п. Акторы Ak и Nk можно представить виде единого бесконечного автомата (актора) Gk (G: Grap node) принимающего на вход ленту Tk (tape) из кортежей (qk, ek, Lk) и возвращающего символ R. Информационную систему состоящею из акторов G1, G2, …, Gk, … можно представить в виде бесконечного автомата r=G(s,t) принимающему символ t из алфавита виде кортежа T=(T1, T2, …, Tk) и возражающую кортеж символов r=(R1, R2, …, Rk) и имеющий состояние виде кортежа (S1,S2,..,Sk).
Применив ко множеству всех входных сообщений, актор G находящий в начальном состоянии s0. Мы получим множество состояний S1 достижимых на первом шаге ленты. Мы можем представить их в направленного графа состоящего из дуг (s0, G(s0,t)). Продолжая процесс рекурсивно бесконечное число раз, мы получим направленный слабый граф всех достижимых состояний SR (state, reachable) информационной системы G. Все возращённые в ходе обхода графа ответы являются множеством достижимых ответов RR. Мы будем рассматривать только детерминированные актёры, у которых мощность множества RR меньше или равна мощности Q в квадрате. Используя цепи Маркова и зная вероятность события E мы можем получить вероятность попадания в состояние каждое состояние sr.
Чтобы проанализировать CAP теорему наложим на нашу систему следующие ограничения. Для простоты, число возможных запросов пользователя, то есть мощность множества Q двумя.
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 путь мы будем называть консистентным. Коэффициент консистентной равен суммарной вероятности попадания на консистентные пути по отношению к общей вероятности попадания на CAP путь. Коэффициент устойчивости разделению – это среднее количество узлов, которые были доступны, в путях где сохранилась доступность. Легко проверить численными методами что для любого конечного автомата, у которого операции связаны (результат операций зависит от последовательности их поступления) сумма коэффициентов меньше или равна двум.
Тут наверняка есть куча косяков. Так как люди, которые могу написать такое определение правильно, работают в гугле за много бабок, а не формочки в банке клепают. Но у меня есть железная отмазка. Я писал это доказательство в пятницу вечером
. А последнюю его часть вообще глубокой ночью. Но буду благодарен за указания на эти косяки.
PS Из такого определения следует несколько важных выводов. Первый что если запросы пользователя не взаимодействую, или можно сделать чтобы они не взаимодействовали на каком-то отрезке графа, то мы можем получить все три буквы СAP. Кап теорема вообще не применима к системам со случайным поведением. Оба этих свойства очень интересны с точки зрения проектирования криптовалют третьего поколения.
F_>>Но в реальности требуется статически доказать что они действительно 100% CA, так как во всех виденных мной системах была масса не очевидных на первый взгляд путей через граф их состояния, которые приводили к потере либо C либо A. Хотя все такие пути ну очень маловероятны, но их большое количество и склонность корреляции приводили к снижению С и A где-то до 95% от вероятности аварии.
S>Хотелось бы понять, как именно вы придаёте численные значения метрикам С и P.
S>Если с A всё понятно, то что такое C=80%, или P=51%?
Конечно в самой кап теореме этого нет. Поскольку она описывает математическую абстракцию в дискретном мире. Но задачка математически определить эти коэффициенты любопытная. Смог придумать два определения. Одно простое и понятное, но к сожалению, совершенно неправильное и на практике неприменимое. Второе боле-менее правильное и применимое на практике, но немного сложное.
Первое описания: кап теорема описывает абстрактную систему, в которой есть всего одно состояние, и в которой есть всего один тип связи, и которая может сломаться одним единственным способом. Реальная система имеет множество состояний, и много типов связей, которые нарушаются множеством различных способов. Такую систему можно представить, как составленную из множества систем подчиняющихся CAP теореме. Каждая из этих подсистем не обязана вести себя одинаково. Некоторые могут быть AP, некоторые CP, некоторые СА. Так как эти подсистемы взаимодействуют на границе их взаимодействия буду присутствовать системы, имеющие только одну букву. Например, на границе недоступной системы (CP) и некосистентной (АP) будет присутствовать система, которая одновременно недоступна, и некосистентна (только P). Посчитав отношение количества подсистем, которые являются доступными к общему количеству подсистем мы найдем коэффициент A. Также поступим для остальных кофинетов.
Это совершено неправильно с математической точки зрения, зато понятно.
Вот более правильное объяснение, которое еще и практически применимо. Я постарался обойтись только теорией конечных автоматов. Думаю, все программисты ее хорошо знают:
Представим узел нашей системы Ak виде конечного автомата (A: actor), у которого есть множество возможных состояний Sk (S: state). Акторов в системе k=[1.. ∞). На каждом шаге, n, ленты Ak производит символ rk (r: responce) принадлежащий алфавиту (множеству) R ответов пользователю, зависящее только от входящего символа, и текущего состояния rk=f(Sk,ik). Алфавит R включает пустой элемент (r0), который означает что на этом шаге у A нет ответа пользователю. Поскольку мы имеем дело с распределенной системой, то кроме ответов пользователю, A на каждом шаге производит сообщение для каждого k узла системы Mk эти сообщения собраны в упорядоченную последовательность MO=(M1,M2,…, Mk) (кортеж Message Output). Таким образом выходной алфавит A состоит из упорядоченной пары символов (r, MO). Для каждого A существует бесконечный автомат N (N: network). N принимает упорядоченную пару из символов L=[1..∞) (L: Latency) и MO всех A. Nk возвращает символ Mik (message input) который равен кортежу из символов Mk для узла Ak, полученный на шаге n-L. Входящий символ конечного автомата Ak принадлежит алфавиту, представлявшему собой кортеж из трех символов (Mik, qk, ek). Символ q (Q, query) принадлежит алфавиту Q запросов пользователя. Символ e (E: Event) событие которое случилось с нашим актором. Событие принадлежит множеству E состоящему из таких событий как истечение таймаута, перезагрузка информационной системы, изменение настроек узла и т.п. Акторы Ak и Nk можно представить виде единого бесконечного автомата (актора) Gk (G: Grap node) принимающего на вход ленту Tk (tape) из кортежей (qk, ek, Lk) и возвращающего символ R. Информационную систему состоящею из акторов G1, G2, …, Gk, … можно представить в виде бесконечного автомата r=G(s,t) принимающему символ t из алфавита виде кортежа T=(T1, T2, …, Tk) и возражающую кортеж символов r=(R1, R2, …, Rk) и имеющий состояние виде кортежа (S1,S2,..,Sk).
Применив ко множеству всех входных сообщений, актор G находящий в начальном состоянии s0. Мы получим множество состояний S1 достижимых на первом шаге ленты. Мы можем представить их в направленного графа состоящего из дуг (s0, G(s0,t)). Продолжая процесс рекурсивно бесконечное число раз, мы получим направленный слабый граф всех достижимых состояний SR (state, reachable) информационной системы G. Все возращённые в ходе обхода графа ответы являются множеством достижимых ответов RR. Мы будем рассматривать только детерминированные актёры, у которых мощность множества RR меньше или равна мощности Q в квадрате. Используя цепи Маркова и зная вероятность события E мы можем получить вероятность попадания в состояние каждое состояние sr.
Чтобы проанализировать CAP теорему наложим на нашу систему следующие ограничения. Для простоты, число возможных запросов пользователя, то есть мощность множества Q двумя.
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 путь мы будем называть консистентным. Коэффициент консистентной равен суммарной вероятности попадания на консистентные пути по отношению к общей вероятности попадания на CAP путь. Коэффициент устойчивости разделению – это среднее количество узлов, которые были доступны, в путях где сохранилась доступность. Легко проверить численными методами что для любого конечного автомата, у которого операции связаны (результат операций зависит от последовательности их поступления) сумма коэффициентов меньше или равна двум.
Тут наверняка есть куча косяков. Так как люди, которые могу написать такое определение правильно, работают в гугле за много бабок, а не формочки в банке клепают. Но у меня есть железная отмазка. Я писал это доказательство в пятницу вечером
. А последнюю его часть вообще глубокой ночью. Но буду благодарен за указания на эти косяки.PS Из такого определения следует несколько важных выводов. Первый что если запросы пользователя не взаимодействую, или можно сделать чтобы они не взаимодействовали на каком-то отрезке графа, то мы можем получить все три буквы СAP. Кап теорема вообще не применима к системам со случайным поведением. Оба этих свойства очень интересны с точки зрения проектирования криптовалют третьего поколения.
Re[7]: Сервисы, передающие изменения другим сервисам и т.д.
Здравствуйте, Sinclair, Вы писали:
F_>>Но в реальности требуется статически доказать что они действительно 100% CA, так как во всех виденных мной системах была масса не очевидных на первый взгляд путей через граф их состояния, которые приводили к потере либо C либо A. Хотя все такие пути ну очень маловероятны, но их большое количество и склонность корреляции приводили к снижению С и A где-то до 95% от вероятности аварии.
S>Хотелось бы понять, как именно вы придаёте численные значения метрикам С и P.
S>Если с A всё понятно, то что такое C=80%, или P=51%?
Конечно в самой кап теореме этого нет. Поскольку она описывает математическую абстракцию в дискретном мире. Но задачка математически определить эти коэффициенты любопытная. Смог придумать два определения. Одно простое и понятное, но к сожалению, совершенно неправильное и на практике неприменимое. Второе боле-менее правильное и применимое на практике, но немного сложное.
Первое описание: кап теорема описывает абстрактную систему, в которой есть всего одно состояние, и в которой есть всего один тип связи, и которая может сломаться одним единственным способом. Реальная система имеет множество состояний, и много типов связей, которые нарушаются множеством различных способов. Такую систему можно представить, как составленную из множества систем подчиняющихся CAP теореме. Каждая из этих подсистем не обязана вести себя одинаково. Некоторые могут быть AP, некоторые CP, некоторые СА. Так как эти подсистемы взаимодействуют на границе их взаимодействия буду присутствовать системы, имеющие только одну букву. Например, на границе недоступной системы (CP) и некосистентной (АP) будет присутствовать система, которая одновременно недоступна, и некосистентна (только P). Посчитав отношение количества подсистем, которые являются доступными к общему количеству подсистем мы найдем коэффициент A. Также поступим для остальных континентов.
Это совершено неправильно с математической точки зрения, зато понятно.
Вот более правильное объяснение, которое еще и практически применимо. Я постарался обойтись только теорией конечных автоматов. Думаю, все программисты ее хорошо знают:
Представим узел нашей системы Ak виде конечного автомата (A: actor), у которого есть множество возможных состояний Sk (S: state). Акторов в системе k=[1.. ∞). На каждом шаге, n, ленты Ak производит символ rk (r: responce) принадлежащий алфавиту (множеству) R ответов пользователю, зависящее только от входящего символа, и текущего состояния rk=f(Sk,ik). Алфавит R включает пустой элемент (r0), который означает что на этом шаге у A нет ответа пользователю. Поскольку мы имеем дело с распределенной системой, то кроме ответов пользователю, A на каждом шаге производит сообщение для каждого k узла системы mk эти сообщения собраны в упорядоченную последовательность mOk=(m1,m2,…, mk) (кортеж Message Output). Таким образом выходной алфавит A состоит из упорядоченной пары символов (r, mO). Для каждого A существует бесконечный автомат N (N: network). N принимает упорядоченную пару из символов L=[1..∞) (L: Latency) и mO от всех A. Nk возвращает символ mik (message input) который равен кортежу из символов mOk для узла Ak, полученный на шаге n-L. Входящий символ конечного автомата Ak принадлежит алфавиту, представлявшему собой кортеж из трех символов (mik, qk, ek). Символ q (Q, query) принадлежит алфавиту Q запросов пользователя. Символ e (E: Event) событие которое случилось с нашим актором. Событие принадлежит множеству E состоящему из таких событий как истечение таймаута, перезагрузка узла, удаление базы узла, изменение настроек узла и т.п. Акторы Ak и Nk можно представить виде единого бесконечного автомата (актора) Gk (G: Grap node) принимающего на вход ленту Tk (tape) из кортежей (qk, ek, Lk) и возвращающего символ rk. Информационную систему состоящею из акторов G1, G2, …, Gk можно представить в виде бесконечного автомата r=G(s,t) принимающему символ t из алфавита виде кортежа T=(T1, T2, …, Tk) и возражающую кортеж символов r=(R1, R2, …, Rk) и имеющий состояние виде кортежа (S1,S2,..,Sk).
Применив ко множеству всех входных сообщений, актор 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.
Чтобы проанализировать CAP теорему наложим на нашу систему следующие ограничения. Для простоты, число возможных запросов пользователя, то есть мощность множества Q двумя.
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 путь мы будем называть консистентным. Коэффициент консистентной равен суммарной вероятности попадания на консистентные пути по отношению к общей вероятности попадания на CAP путь. Коэффициент устойчивости разделению – это среднее количество узлов, которые были доступны, в путях где сохранилась доступность. Легко проверить численными методами что для любого конечного автомата, у которого операции связаны (результат операций зависит от последовательности их поступления) сумма коэффициентов меньше или равна двум.
Тут наверняка есть куча косяков. Так как люди, которые могу написать такое определение правильно, работают в гугле за много бабок, а не формочки в банке клепают. Но у меня есть железная отмазка. Я писал это доказательство в пятницу вечером. А последнюю его часть вообще глубокой ночью. Но буду благодарен за указания на эти косяки.
PS Из такого определения следует несколько важных выводов. Первый что если запросы пользователя не взаимодействую, или можно сделать чтобы они не взаимодействовали на каком-то отрезке графа, то мы можем получить все три буквы СAP. Кап теорема вообще не применима к системам со случайным поведением. Оба этих свойства очень интересны с точки зрения проектирования криптовалют третьего поколения.
F_>>Но в реальности требуется статически доказать что они действительно 100% CA, так как во всех виденных мной системах была масса не очевидных на первый взгляд путей через граф их состояния, которые приводили к потере либо C либо A. Хотя все такие пути ну очень маловероятны, но их большое количество и склонность корреляции приводили к снижению С и A где-то до 95% от вероятности аварии.
S>Хотелось бы понять, как именно вы придаёте численные значения метрикам С и P.
S>Если с A всё понятно, то что такое C=80%, или P=51%?
Конечно в самой кап теореме этого нет. Поскольку она описывает математическую абстракцию в дискретном мире. Но задачка математически определить эти коэффициенты любопытная. Смог придумать два определения. Одно простое и понятное, но к сожалению, совершенно неправильное и на практике неприменимое. Второе боле-менее правильное и применимое на практике, но немного сложное.
Первое описание: кап теорема описывает абстрактную систему, в которой есть всего одно состояние, и в которой есть всего один тип связи, и которая может сломаться одним единственным способом. Реальная система имеет множество состояний, и много типов связей, которые нарушаются множеством различных способов. Такую систему можно представить, как составленную из множества систем подчиняющихся CAP теореме. Каждая из этих подсистем не обязана вести себя одинаково. Некоторые могут быть AP, некоторые CP, некоторые СА. Так как эти подсистемы взаимодействуют на границе их взаимодействия буду присутствовать системы, имеющие только одну букву. Например, на границе недоступной системы (CP) и некосистентной (АP) будет присутствовать система, которая одновременно недоступна, и некосистентна (только P). Посчитав отношение количества подсистем, которые являются доступными к общему количеству подсистем мы найдем коэффициент A. Также поступим для остальных континентов.
Это совершено неправильно с математической точки зрения, зато понятно.
Вот более правильное объяснение, которое еще и практически применимо. Я постарался обойтись только теорией конечных автоматов. Думаю, все программисты ее хорошо знают:
Представим узел нашей системы Ak виде конечного автомата (A: actor), у которого есть множество возможных состояний Sk (S: state). Акторов в системе k=[1.. ∞). На каждом шаге, n, ленты Ak производит символ rk (r: responce) принадлежащий алфавиту (множеству) R ответов пользователю, зависящее только от входящего символа, и текущего состояния rk=f(Sk,ik). Алфавит R включает пустой элемент (r0), который означает что на этом шаге у A нет ответа пользователю. Поскольку мы имеем дело с распределенной системой, то кроме ответов пользователю, A на каждом шаге производит сообщение для каждого k узла системы mk эти сообщения собраны в упорядоченную последовательность mOk=(m1,m2,…, mk) (кортеж Message Output). Таким образом выходной алфавит A состоит из упорядоченной пары символов (r, mO). Для каждого A существует бесконечный автомат N (N: network). N принимает упорядоченную пару из символов L=[1..∞) (L: Latency) и mO от всех A. Nk возвращает символ mik (message input) который равен кортежу из символов mOk для узла Ak, полученный на шаге n-L. Входящий символ конечного автомата Ak принадлежит алфавиту, представлявшему собой кортеж из трех символов (mik, qk, ek). Символ q (Q, query) принадлежит алфавиту Q запросов пользователя. Символ e (E: Event) событие которое случилось с нашим актором. Событие принадлежит множеству E состоящему из таких событий как истечение таймаута, перезагрузка узла, удаление базы узла, изменение настроек узла и т.п. Акторы Ak и Nk можно представить виде единого бесконечного автомата (актора) Gk (G: Grap node) принимающего на вход ленту Tk (tape) из кортежей (qk, ek, Lk) и возвращающего символ rk. Информационную систему состоящею из акторов G1, G2, …, Gk можно представить в виде бесконечного автомата r=G(s,t) принимающему символ t из алфавита виде кортежа T=(T1, T2, …, Tk) и возражающую кортеж символов r=(R1, R2, …, Rk) и имеющий состояние виде кортежа (S1,S2,..,Sk).
Применив ко множеству всех входных сообщений, актор 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.
Чтобы проанализировать CAP теорему наложим на нашу систему следующие ограничения. Для простоты, число возможных запросов пользователя, то есть мощность множества Q двумя.
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 путь мы будем называть консистентным. Коэффициент консистентной равен суммарной вероятности попадания на консистентные пути по отношению к общей вероятности попадания на CAP путь. Коэффициент устойчивости разделению – это среднее количество узлов, которые были доступны, в путях где сохранилась доступность. Легко проверить численными методами что для любого конечного автомата, у которого операции связаны (результат операций зависит от последовательности их поступления) сумма коэффициентов меньше или равна двум.
Тут наверняка есть куча косяков. Так как люди, которые могу написать такое определение правильно, работают в гугле за много бабок, а не формочки в банке клепают. Но у меня есть железная отмазка. Я писал это доказательство в пятницу вечером
. А последнюю его часть вообще глубокой ночью. Но буду благодарен за указания на эти косяки.PS Из такого определения следует несколько важных выводов. Первый что если запросы пользователя не взаимодействую, или можно сделать чтобы они не взаимодействовали на каком-то отрезке графа, то мы можем получить все три буквы СAP. Кап теорема вообще не применима к системам со случайным поведением. Оба этих свойства очень интересны с точки зрения проектирования криптовалют третьего поколения.