Топологический подход в распределенных вычислениях: различия между версиями

Между топологическими моделями и вычислениями имеется следующая связь. Начальное локальное состояние процесса P моделируется как вершина <math>\vec{v} = \langle P, v \rangle</math>, помеченная идентификатором процесса P и начальным значением v. Начальное глобальное состояние моделируется как n-симплекс <math>S^n = ( \langle P_0, v_0 \rangle , ..., \langle P_n, v_n \rangle )</math>, где все <math>P_i</math> различны. Терм <math>ids(S^n)</math> обозначает множество идентификаторов процессов, связанных с <math>S^n</math>, а <math>vals(S^n)</math> – множество значений. Множество всех возможных начальных глобальных состояний образует комплекс, называемый ''входным комплексом''.

Любой протокол имеет связанный с ним ''протокольный комплекс'' <math>\mathcal{P}</math>, определяемый следующим образом. Каждая вершина помечена идентификатором процесса и возможным локальным состоянием этого процесса. Множество вершин <math>\langle P_0, v_0 \rangle , ..., \langle P_d, v_d \rangle</math> охватывает симплекс <math>\mathcal{P}</math> тогда и только тогда, когда существует некоторое выполнение протокола, при котором <math>P_0, ..., P_d</math> завершают его с соответствующими локальными состояниями <math>v_0, ..., v_d</math>. Таким образом, каждый симплекс соответствует классу эквивалентности выполнений, которые «выглядят одинаково» для процессов в его вершинах. Терм <math>\mathcal{P}(S^m)</math> обозначает подкомплекс <math>\mathcal{P}</math>, соответствующий исполнениям, в которых участвуют только процессы из <math>ids(S^n)</math> (остальные завершаются сбоями, не отправив ни одного сообщения). Если m < n - f, то таких исполнений не существует, и подкомплекс <math>\mathcal{P}(S^m)</math> пуст. Структура протокольного комплекса <math>\mathcal{P}</math> зависит как от протокола, так и от временных характеристик и характеристик отказов модели. Часто <math>\mathcal{P}</math> обозначает и протокол, и его комплекс; различие между ними проводится, исходя из контекста.