Формат представления распределенных систем. Отображение бинарных связей
Хабы: Peer-to-PeerРассмотрим полносвязный ориентированный граф. Каждый узел связан со всеми.
Матрица графа будет заполнена единицами. В том числе и главная диагональ, так как каждый узел связан и собой тоже.
Если в определеный момент какая-то связь разрывается, то граф превращается в подграф полносвязного. У каждого узла есть программа, по которой он работает: двоичная память, адрес соответствует входящим связям, значение по адресу — исходящим. Для каждого узла программа своя.
Это представление эквивалентно машине Тьюринга, так легко может быть получено на клеточном автомате, у которого все элементы друг другу соседи. Для этого нужно состояние элемента сделать составным, каждую часть отнести к одной из исходящих связей. Таким образом, каждое из состояний зависит от входящих связей и соответствует какому-то подмножеству исходящих.
Можно также через отображение бинарных связей выразить бинарный клеточный автомат. Достаточно, чтобы все выходные связи были равны.
Также можно выразить и работающие параллельно n элементарных процессоров следующего вида: М — двоичная n-разрядная память, X — адрес, Y — значение по адресу. Начальное состояние X0. Первый шаг: X := X0; Y := M[X]. Следующие шаги: X := Y; Y := M[X]. Итак, чтобы выразить, нужно чтобы каждое второе отображение каждого элемента было эквивалентным. На одном шаге, будет получаться следующее состояние элементарного процессора в качестве исходного подмножества, на втором шаге это же множество без изменений отобразиться обратно в качестве входящего подмножества.
Эквивалентность параллельным невзаимодействующим процессорам, означает что если заменить эквивалентное отображение на другое, получим модель синхронно попеременно работающих автономно и взаимодействующих процессоров. А поскольку мы рассматриваем половину шагов как автономную, а вторую как синхронизирующую, можно видеть двойственность подобного представления в зависимости от того, какую из половин шагов как рассматривать. Другими словами, целая система может противоречить одному узлу, на каждом шаге изменяя его программу на противоположную. Значит, система допускает диалектичность поведения.
Читать дальше →
Полный текст статьи читайте на Habrahabr.ru
