Книги, научные публикации
ИСПОЛЬЗОВАНИЕ ИГР КЛЕТОЧНЫХ АВТОМАТОВ ДЛЯ СИНХРОНИЗАЦИИ В РАСПРЕДЕЛЁННЫХ СИСТЕМАХ М.В. Поникаров, руководитель проекта, ЗАО Датавижн СНГ, Нижний Новгород ponikarov Рассмотрена игра клеточных
автоматов FireSquad с точки зрения применения в качестве формальной модели синхронизации действий в распределённых программных системах. Описаны эвристики, позволяющие сократить пространство вариантов при поиске минимального локального правила.
История развития теории клеточных автоматов Клеточные автоматы в силу своей дискретности сравнительно просто моделируются при помощи ермин клеточные автоматы стал приме ЭВМ и благодаря этому, в 50Ц70 е гг. XX в. приоб няться в середине XX в. для обозначения ретают популярность. Исследователи различных Тсовокупности зависимых элементов с задан научных областей изучают и используют клеточные ными состояниями и правил, в соответствии с ко автоматы с разнообразными свойствами для раз торыми состояния этих элементов и зависимости личных целей. В это время выходят основные тру между ними изменяются во времени. Время и со ды, заложившие базис для общей теории клеточных стояния при этом дискретны. Использование опи автоматов.
санной выше модели для формального моделирова В 1970 г. Bruks [2] в книге Essays on Cellular Auto ния самовоспроизводящихся организмов впервые mata изложил основные термины и положения по предложено в работе Фон Неймана [1]. Элементы этой теме, обобщив множественные теоретические клеточных автоматов предложено выстроить в од исследования на тот период. В дальнейшем теория номерные или двухмерные бесконечные прямоу разносторонне изучена и расширена Аладьевым [3] гольные таблицы. Состояние элемента изменяется (1974 г.), Smith [4] (1976 г.), Vollmar [5] (1977 г.). В этих в зависимости от его состояния и от состояния двух и других работах изложена классическая теория (или четырех - для двухмерного случая) ближай клеточных автоматов - общие положения, теоремы ших соседей (см. рис. 1). и закономерности, верные для всех направлений ис следований на тот период.
Примерно в то же время появились игры для клеточных автоматов - математические модели, имеющие в основе игровое описание. Например, игра Firing Squad - задача об одновременном зал пе всего орудийного расчёта имеет в основе важную задачу синхронизации [6], а игра Game of Life со держит в себе модель поведения популяции в одно родной среде [7].
Благодаря своей гибкости и универсальности, клеточные автоматы нашли признание в теории искусственного интеллекта, в самовоспроизводя. 1. Схема двухмерного расположения элементов щихся моделях, микро и макробиологии, вычи клеточного автомата слениях в среде с возможностью сбоев, в системах БИЗНЕС ИНФОРМАТИКА №3(05)Ц2008 г. распознавания языка и изображений, в распреде вычисляется из состояния самого элемента лённых системах в условиях линформационного и его соседей. Соседство в большой степени голодания. определяется геометрией клеточного автомата.
Начиная с 80 х гг. XX в. изучение клеточных Для различных целей возможно изменение чи автоматов приняло более специализированный сла входных состояний элемента. Если для оттенок. На базе общей теории создаются и изуча каждого элемента клеточного автомата число ются различные конфигурации клеточных автома входов и выходов одинаковое, такой клеточ тов для конкретных исследовательских областей. ный автомат называется сбалансированным;
Благодаря разносторонним исследованиям, уда локальное правило. В соответствии с локаль лось создать мощную математическую теорию, на ным правилом изменяется состояние элемента правленную на классификацию и изучение свойств клеточного автомата в течение времени. Кле различных моделей. точный автомат, в котором локальные правила В 1983 г. Wolfram издал свою первую работу [8] различны для различных элементов, называет по статистическим параметрам клеточных автома ся разнородным. Локальное правило может тов. В дальнейшем Wolfram развил математические быть недетерминированным, т.е. изменяться аспекты этой теории [9], что позволило ему и дру во времени или иметь случайную природу.
гим исследователям подробно классифицировать и изучить практически всё множество клеточных Варьируя заданные параметры, можно получить автоматов. клеточные автоматы необходимой конфигурации.
Гибкость конфигурации и универсальность вычисле Классификация и свойства клеточных автоматов ния обеспечили высокую популяризацию клеточных Для получения различных конфигураций кле автоматов в различных сферах. Произвольность в вы точных автоматов, принято варьировать следующи боре параметров конфигурации очень удобна для ис ми параметрами: пользования, но это придаёт дополнительную слож состояния элементов. В каждый момент време ность в классификации и систематизации знаний ни каждый элемент клеточного автомата имеет теории клеточных автоматов. Тем не менее, наиболее одно из конечного набора состояний. В зависи используемо на практике лишь небольшое семейство мости от этих состояний в следующий момент конфигураций клеточных автоматов. Как правило, времени набор элементов может принять новое каждый из них имеет своё название. Здесь приведён состояние. Если для элементов клеточного лишь небольшой список наиболее используемых автомата множества возможных состояний раз вариантов конфигураций:
личны, такой клеточный автомат называется мозаичный автомат [10]. Клеточный автомат, полигенным. Но на практике используются использующий в локальном правиле каждого ячейки с эквивалентными множествами воз элемента не только состояние элемента и его можных состояний с алгебраической структу соседей, но и значение общего входного пара рой - линейные клеточные автоматы;
метра, который может изменяться со време геометрия. Элементы могут быть геометриче нем. Изменение этого параметра ведёт к сме ски расположены различным образом. Размер не набора правил смены состояний во всём ность пространства может быть произвольной, пространстве элементов клеточного автомата.
а число элементов - как бесконечным, так Если из какого либо начального состояния и конечным. В последнем случае возникает до можно привести клеточный автомат в любую полнительная степень свободы в граничных заданную конфигурацию путём варьирования условиях. Они могут быть различными, но на значением общего входного параметра, кле практике используются постоянные во време точный автомат называют полным;
ни (чаще всего - нулевые) или периодические итеративный автомат [11]. Клеточный авто граничные условия. В динамических клеточных мат, в котором лишь один элемент использует автоматах геометрия может изменяться со вре для изменения своего состояния значение менем, а если геометрия различна на различ входного параметра;
ных участках пространства, такие клеточные односторонний клеточный автомат [12]. Та автоматы называют неоднородными;
кой автомат допускает лишь одностороннее соседство. Соседи - это элементы, от которых взаимодействие элементов. Например, в од зависит элемент клеточного автомата. Состоя номерном массиве элементов значение каж ние элемента в следующий момент времени дого элемента зависит лишь от его состояния 32 БИЗНЕС ИНФОРМАТИКА №3(05)Ц2008 г.
и от состояния левого (или правого) соседа. моделирующая макроскопическое поведение попу Несмотря на кажущееся вырождение обычно ляции в однородной среде.
го клеточного автомата, односторонние кле Наше внимание привлекла игра Fire squad.
точные автоматы достаточно универсальны Это задача, требующая составить локальное прави и используются для распознавания языковых ло, одинаковое для каждого элемента одномерного форм;
клеточного автомата, удовлетворяющее условиям Л система [13]. Этот тип клеточных автоматов игры.
используется для моделирования биологиче В оригинальном описании игры n солдат (один ских систем. Это динамические клеточные из них - генерал) становятся в одну шеренгу. Каж автоматы (как правило, одномерные или дву дый солдат может общаться лишь с правым или ле мерные), в которых с течением времени один вым соседом. Генерал даёт команду старт. Через элемент может заменяться несколькими или некоторое время каждый солдат и генерал должны может быть удалённым из системы в соответ выстрелить одновременно и при этом каждый - ствии с заданными правилами;
в первый раз.
отказоустойчивая система [14]. В таких систе В терминах теории клеточных автоматов, для n мах моделируется работа клеточных автоматов элементов, расставленных в ряд и имеющих в каче в реальных условиях: с некоторой вероятно стве соседа лишь правый и левый ближайший эл стью каждый элемент клеточного автомата емент, определить общее локальное правило (не за может перейти в состояние, не соответствую висящее от n), в результате которого клеточный ав щее локальному правилу. Задачей является томат придёт из заданной начальной конфигурации создать алгоритмы, для которых работа кле в требуемую. Начальная конфигурация: все элемен точного автомата будет верной вне зависимо ты имеют выключенное состояние (например, сти от допущенных ошибок. л0), кроме одного - в состоянии старт (напри мер, л1). Требуемая конфигурация: все элементы Существуют вспомогательные свойства клеточ в состоянии логонь (например, - л2). При этом ных автоматов, описывающие важные характери ни один элемент в промежуточных конфигурациях стики таких систем. Эти свойства позволяют ввести не должен принимать состояния л2 (см. рис. 2).
более детальную классификацию множества кле точных автоматов.
Клеточный автомат называют инвертируемым, 1 0 0 0 если существует набор локальных правил, позво ляющий однозначно привести клеточный автомат из любого состояния в предыдущее. То есть, если по текущему состоянию всех элементов клеточного ав 2 2 2 2 томата можно определить его состояние в предыду F щий момент времени.
Состояние всех элементов клеточного автомата (конфигурация клеточного автомата) называется. 2. Игра Fire squad. Начальное и требуемое состояние Райским садом, если такая конфигурация может возникнуть только лишь как начальное значение в любой эволюции клеточного автомата. Отсутствие Как видно, данная задача - это задача синхро такой конфигурации означает, что данный клеточ низации. Она может быть применена в различных ный автомат - эпиморфный. прикладных областях. Основная сложность - в неопределённости числа элементов клеточного ав Игры для клеточных автоматов томата - солдат.
Наряду с практическими моделями, клеточные В общем случае задача многомерная, и генера автоматы могут быть использованы для создания лом может быть любой элемент. Обычно генерал - игровых моделей. Игры в большинстве своем пред это один из крайних элементов клеточного автома ставляют лишь более наглядное представление та. Граничные условия могут быть различны, но серьёзных практических задач, а изучение игровых принято использовать нулевые граничные условия:
проблем позволяет получить более разностороннее крайние элементы используют неизменные ну и глубокое понимание теории клеточных автоматов левые значения состояний несуществующих эле в целом. Широко известна игра Game of Life, ментов.
БИЗНЕС ИНФОРМАТИКА №3(05)Ц2008 г. Для двухмерной задачи в начальном состоянии коллективных решений и т.д. В независимости от л0 находится nmЦ1 элементов, образующие n физического размещения отдельных компонентов, строк и m столбцов, при этом в общем случае nm. их программной реализации разработчик должен Генерал может располагаться в произвольном ме быть уверен, что их совместное поведение приведёт сте. Каждый элемент имеет по 4 соседа. Наиболее к требуемым результатам.
популярное решение этой задачи нашёл Minsky [18] Нами исследована возможность использования - данное решение содержит достаточно много воз формальной модели игры FireSquad в качестве та можных состояний элементов клеточного автомата кого строгого формального метода координации (99), но обладает важным свойством - такой кле поведения большого числа независимых програм точный автомат инвертированный. Количество мных сущностей.
шагов, за которое клеточный автомат приходит к состоянию залпа равно 3n. Подходы к ограничению сложности задачи Решение для d мерной задачи долгое время изу нахождения требуемого локального правила чал Szwerinski [19]. Он нашёл решение задачи в игре FireSquad Firing squad с 25 возможными состояниями На практике получение локального правила, элементов клеточного автомата. необходимого для требуемого поведения клеточно Практический интерес заключается в минимиза го автомата нетривиально. Производительность ции количества временных шагов, предшествующих современных вычислительных машин позволяет залпу и (или) минимизации возможных состояний составлять программы, которые перебором конеч элементов в зависимости от конфигурации клеточ ного числа вариантов находят локальные правила, ных автоматов. удовлетворяющие поставленным критериям.
Рассмотрим основные приемы оптимизации пе Возможности прикладного применения теории реборной стратегии для игры Firing squad. Интерес клеточных автоматов представляет минимизация числа возможных со Требование динамической интеграции разнород стояний элементов, числа возможных ситуаций для ных компонент в составе единого вычислительного элемента (состояние самого элемента и его соседей) комплекса заставляет вести разработку открытых и количества временных интервалов до залпа.
программных архитектур, включающих большое ко Данная проблема исследуется около 50 лет.
личество распределённых программных подсистем. В 1957 г. эта задача сформулирована Myhill, а впер Наиболее известными практическими примерами вые упомянута в изданиях Moore [15]. Очевидно, таких архитектур являются многоагентные системы что минимальный период до залпа равен T = 2nЦ1:
[20, 21] и сети с равноправным правом на хранение сигнал должен дойти от генерала до конечного информации [22] (peer to peer, P2P). элемента клеточного автомата и обратно, иначе ал Среди современных теоретических разработок горитм не сможет определить число элементов в можно указать на направление аморфных вычисле клеточном автомате. Простые, но в тоже время мед ний. По мнению авторов [23], в течение ближайших ленные алгоритмы производят залп за T = 3n шага.
десятилетий две основные нанотехнологии: микро Минимизация возможных состояний - более производство (microfabrication) и клеточная инжене сложная задача - решается на протяжении всего рия - сделают возможным создание систем, вклю времени существования этой задачи. В 1966 г. Waks чающих мириады очень дешёвых устройств, способ man [16] опубликовал решение одномерной задачи ных вести обработку различной информации. При для 16 состояний элементов. В 1967 г. Balzer умень чем не обязательно от всех таких устройств требовать шил зто число до 8. В 1987 году Mazoyer [17] нашёл гарантии безошибочной работы и определения их решение этой задачи для 6 используемых состоя точного взаиморасположения в пространстве. Такое ний. Оценку снизу получил Balzer. Он доказал, что изменение технологии приведёт к фундаментально решение поставленной задачи невозможно для кле му изменению методов создания и программирова точных автоматов с 4 и менее используемыми со ния компьютеров, а также само наше представление стояниями.
о вычислениях. Сложность получения минимального набора со Реализация когерентного поведения большого стояний объясняется большой вычислительной числа независимых вычислительных сущностей, сложностью. Для однозначного определения локаль будь то агенты в многоагентной системе или узлы ного правила для клеточного автомата с k используе сети P2P, требует разработки строгих формальных мыми состояниями необходимо определить kk3пове методов для управления транзакциями, принятия дения элементов (новое состояние в зависимости 34 БИЗНЕС ИНФОРМАТИКА №3(05)Ц2008 г.
от текущего состояния элемента и его соседей). Для 1 0 0 0 k = 3 это число превосходит 1012. При этом каждый из полученных вариантов необходимо проверить на клеточном автомате, что потребует как минимум Tn a b 0 0 операций. Такая задача посильна лишь супер ЭВМ.
В ходе работы нами определён ряд эвристик, по зволяющих сократить рассматриваемое количество c d e 0 вариантов.
F Пусть требуется найти локальное правило, удо влетворяющее задачу Fired squad для заданного числа элементов n и числа используемых состояний. 3. Изменение конфигурации клеточного автомата k. Пусть генерал стоит первым в строю. Локальное с течением времени правило описывается функцией F(x, y, z), которая возвращает значение нового состояния элемента Благодаря описанным оптимизациям макси (0,1,..., kЦ1) в зависимости от текущих состояний мальное число вариантов можно определить как элемента (x = 0,1,..., kЦ1) и состояний его соседей (y = 0,1,..., kЦ1 и z = 0,1,..., kЦ1). Известно, что (kЦ1)40 + A, F(0, 0, 0) = 0. Значение функции в других точках необходимо подобрать. В начальном состоянии где А - число перебираемых вариантов для других n необходимо определить лишь два значения функ с уже известным неполным набором правил.
ции для перехода в следующее состояние:
Для n > 3 число перебираемых вариантов все F(1, 0, 0) = a, F(0, 1, 0) = b. ещё остается значительным. Существует ряд опти мизаций, существенно влияющих на скорость на Для следующего шага - (см. рис. 3): хождения искомого локального правила:
1. Нет смысла определять значение функции F(a, 0, b) = c, F(b, a, 0) = d, F(b, a, 0) = e. F(x, y, z) > p, если все предыдущие определённые значения этой функции в других точках не превос И так далее. Для определения всего множества ходят p более чем на 1 (например, для рисунка 3:
конфигураций клеточного автомата до залпа a 2, b a и т.д.).
необходимо определить лишь требуемую часть зна 2. Можно обрывать перебор значений функции чений функции. На каждом шаге необходимо опре на шаге 2n в случае если к этому моменту времени делить лишь 1Ц4 значений (с течением времени это крайне правый элемент ни разу не изменил своего число уменьшается). Определив, что число шагов до состояния: в этом случае полученный алгоритм не залпа не должно превышать 3n, получаем снижение зависит от числа n: крайне левый элемент не успеет числа перебираемых локальных правил порядка k8n. получить информацию от крайне правого элемента.
Также получается выгода: можно найти все воз 3. Можно ограничить число определённых зна можные локальные правила для заданного n и затем чений функции F(x, y, z), если это не противоречит проверять и дополнять полученный набор на n+1 и поставленной задаче.
так далее. Начав с небольшого n (например, n = 5) Подавляющее число перебираемых вариантов можно существенно снизить объём вычислений, а практически сразу ведёт к затуханию активности также упростить распределение задачи для парал клеточного автомата, что приводит к качественно лельного вычисления на нескольких машинах, за му снижению объёма вычислений. Например, при писывая промежуточный набор локальных правил использовании предложенных оптимизаций итого в файл и считывая его (или часть) на других ЭВМ. вое число перебираемых вариантов для n = 4 полу Состояние л2 можно не использовать вовсе. Так чилось порядка 10 миллиардов, что удовлетворяет как все солдаты должны выстрелить одновременно, производительности современного персонального можно отслеживать благоприятный момент для компьютера. Оценка каждого варианта занимает залпа: если в определённый момент времени для порядка 10000 элементарных операций процессора.
определения состояния каждого элемента в сле Таким образом, время перебора с использованием дующий момент времени необходимо определить одного персонального компьютера (процессор новое значение функции, все эти значения можно Athlon, 1000 мегагерц) для данного варианта зани определить как л2. мает около 30 часов.
БИЗНЕС ИНФОРМАТИКА №3(05)Ц2008 г. Таким образом, с появлением высокопроизво задачи прямого поиска минимальных локальных дительных ЭВМ появилась реальная возможность наборов правил, применение эвристик, получен создавать клеточные автоматы с необходимой кон ных в данной работе, позволяет решать задачу для фигурацией, обладающие параметрами, оптимизи простейших конфигураций за практически прие рованными для практической реализации в соот млемое время.
ветствии с поставленной задачей. Однако для использования модели игры Fi reSquad в качестве базового алгоритма координа Выводы ции в распределённых системах требуется решение В современных распределённых программных большого числа проблем. Среди таких проблем ука системах требуется использование формальных жем лишь на необходимость обобщения игры на подходов к выработке единого коллективного ре случай случайного расположения клеток автомата шения среди большого количества независимых на плоскости. При этом соседями каждой клетки программных сущностей. В данной работе исследо становятся те, которые находятся в круге некоторо ваны возможности теории клеточных автоматов и го радиуса r. Такая конфигурация типична для их приложений для разработки таких формальных аморфных вычислений, однако непосредственное методов. Модель игры FireSquad может служить применение известных решений для одномерного и основой для исследований в этом направлении. двумерного случая игры FireSquad здесь невоз Несмотря на большую вычислительную сложность можно.
Литература 1. Von Neumann, J. and Burks, A. W., Eds, 1966. Theory of Self Reproducing automata. University of Illinois Press, Champaign, IL.
2. Burks, A., Ed. 1970. Essays on Celluar Automata. University of Illinois Press, Champaign, IL.
3. Aladyev, V. 1974. Survey of research in the theory of homogeneous structures and their applictions. Math. Biosci. 15, 121Ц154.
4. Smith III, A. 1976. Introduction to and survey of polyautomata theory. In Automata, Languages, Development. North Holland Pu blishing Co., Amsterdam, The Netherlands.
5. Vollmar, T. 1977. Cellular spaces and parallel algorithms, and introductory survey. In Parallel Computation Parallel Mathematics, M.
Feilmeier, Ed. North Holland Publishing Co., Amsterdam, The Netherlands. 49Ц58.
6. Moore, E., Ed. 1964. Sequential Machines. Selected Papers. Addison Wesley Publishing Co., Inc., Redwood City, CA.
7. Gardner, M. 1970. The Fantastic combinations of John ConvayТs new solitaire game of Life. Sci. Am. 223, 120Ц123.
8. Wolfram, S. 1983. Statistical mechanics of cellular automata. Rev. Modern Phys. 55, 601Ц644.
9. Wolfram, S. 1986. Theory and Applications of Cellular Automata: Including Selected Papers 1983Ц1986. World Scientific Publishing Co., Inc., River Edge, NJ.
10. Yamada, H. and Amoroso, S. 1969. Tesselation Automata. Inf. Control 14, 299Ц317.
11. Seiferas, J. 1982. Observations of nondeterministics multidimensional iterative arrays In Proceedings of the ACM Symposium of the Theory of Computing, ACM Press, New York, NY, 276Ц289.
12. Chang, J. H., Ibarra, O. H., and Vergis, A. 1988. On the power of one way communication. J. ACM 35, 3 (July 1988), 697Ц726.
13. Lindenmayer, A. 1968. Mathematical models for cellular automata and algebraic series.Theor. Comput. Sci. 119, 2 (Oct. 25, 1993), 345Ц354.
14. Nishio, H. and Kobuchi, Y. 1975. Fault tolerant cellular spaces. J. Comput. Syst. Sci. 11, 150Ц170.
15. Moore, E. and Langdon, G. 1968. A generalized firing squad problem. Inf. Control 12, 212Ц220.
16. Waksman, A. 1966. An optimum solution to the firing squad synchronization problem. Inf. Control 9, 67Ц78.
17. Mazoyer, J. 1987. A six state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci. 50, 2 (Sept.
1987), 183Ц238.
18. Minsky, M. 1972. Computation: Finite and Infinite Mashines. Prentice Hall.
19. Szwerinski, H. 1982. Time optimal solution of the firing squad synchronization problem for n dimensional rectangles with the general at arbitrary position. Theoretical Computer Science, 19, 305Ц320.
20. Cockayne W.T., Zyda M. Mobile Agents. - Manning Publ.Co, 1998. Ц312 pp.
21. Трахтенгерц Э.А. Компьютерная поддержка принятия решений. - М: Синтег, 1998. - 376 c.
22. Parameswan M., Susarla A., Whinston A.B. P2P Networking: An Information Sharing Alternative // Computer, №7, 2001. - pp. 31Ц38.
23. Abelson H., Allen D., Coore D. et all., Amorphous Computing // Communications of the ACM, May 2000 volume 43, №5. - pp.74Ц82.
36 БИЗНЕС ИНФОРМАТИКА №3(05)Ц2008 г.