Синхронизация и асинхронность

В рассмотренных выше задачах содержался не­который обман. Описанные модели решают задачу синхронизации, но используют при этом некий внут­ренний такт, который неизвестно откуда берется. И лишь в задаче о взаимной синхронизации через канал с неизвестной задержкой мы упомянули о воз­можности существования механизма, согласующего длительности внутренних тактов.

Задачу исключения понятия внутреннего такта нельзя решить в рамках используемой для описания алгоритмов локального поведения формальной мо­дели конечного автомата, так как она игнорирует реальное физическое время. Но как только мы на­чинаем рассматривать автомат как реальное физи­ческое устройство, он становится динамической системой, переходные процессы в которой не адек­ватны процессам смены состояний в модели конеч­ного автомата.

Преодоление указанных трудностей обеспечи­вается теорией согласованных самосинхронизующихся схем, которые обеспечивают инвариантность по­ведения автоматов по отношению к длительности внутреннего такта. Однако изложение идей и ре­зультатов этой теории выходит далеко за рамки настоящей книги. Мы опишем все же модель, в ко­торой синхронизация осуществляется без привлече­ния понятия жесткого такта.

На рис. 5.4 «стрелки» образовывали шеренгу, что соответствовало жесткой структурной организации.

160

Теперь мы рассмотрим возможность синхронизации «толпы». Пусть автоматы блуждают в некотором ограниченном пространстве и в какие-то моменты времени сталкиваются друг с другом. В отличие от моделей случайного парного взаимодействия, мы не предполагаем, что эти столкновения одновременны, и тем самым исключаем необходимость тактовой синхронизации. Для нашей модели, вернее для ее формального изучения, необходимо, чтобы в нашей толпе осуществлялось достаточно хорошее перемешивание, т. е. чтобы в идеале все столкновения были равновероятными. Перемешивание, порож­даемое процессами типа броуновского движения, несколько искажает получающиеся результаты. Столкнувшись, два автомата осуществляют акт взаимо­действия и расстаются. Возникает вопрос о существовании правил взаимодействия, обеспечивающих синхронизацию такой совокупности автоматов, пра­вил, не зависящих от числа автоматов.

Прежде всего уточним, что мы в этом случае понимаем под процессом синхронизации. В началь­ный момент времени все автоматы находятся в некотором состоянии 5о и при столкновении двух авто­матов, находящихся в этом состоянии, оно сохраняется у обоих автоматов. Внешний сигнал, иници­ирующий процесс синхронизации, поступает на один из автоматов и выводит его из начального состояния. Естественно, мы не можем требовать, чтобы через какое-то время все автоматы перешли в синхронное состояние, так как при случайном взаимодействии всегда существует ненулевая вероятность того, что информация об инициации процесса за любое конеч­ное время не выйдет за пределы ограниченной части автоматов. Поэтому при случайном взаимодействии можно говорить лишь о вероятности того, что значи­тельная доля автоматов одновременно или в течение относительно короткого отрезка времени будет на­ходиться в синхронном состоянии. Длительность этого отрезка времени определяется частотой столк­новений. Поскольку смена состояний автоматов есть результат взаимодействия, то по крайней мере все перешедшие в синхронное состояние автоматы долж­ны в течение этого интервала времени вступить во взаимодействие.

161

 

Качество, или точность, синхронизации мы будем оценивать математическим ожиданием доли автома­тов, находящихся в синхронном состоянии. Пусть у нас задано некоторое число e (0<e<1) и мы мо­жем определить интервал времени t_e, в течение кото­рого доля автоматов, превышающая 1—e, заведомо вступит во взаимодействие. Мы будем говорить о синхронизации совокупности автоматов с точностью до е, если один из автоматов совокупности иницииро­ван в момент времени t₀ и существует такой момент времени t_c, что до этого момента математическое ожидание доли автоматов, перешедших в синхронное состояние, не превышает е, а математическое ожида­ние доли автоматов, перешедших в синхронное со­стояние после момента времени t_c+t_e, превышает (1-e).

Теперь можно рассмотреть алгоритм локального взаимодействия, обеспечивающий решение зада­чи синхронизации. Автомат имеет (k—1) внутрен­нее состояние. Состояние с номером 0 будем назы­вать начальным, а состояние с номером k — синх­ронным. Взаимодействие определяется следующими правилами:

1. Если оба взаимодействующих автомата нахо­дятся в состоянии 0, то они оба сохраняют это состояние.

2. Внешний инициирующий сигнал переводит автомат из состояния 0 в состояние 1.

3. Если по крайней мере один из взаимодейст­вующих автоматов имеет состояние, отличное от 0, то номер нового состояния для обоих автоматов равен увеличенному на единицу минимальному но­меру состояний взаимодействующих автоматов.

Попытаемся содержательно рассмотреть процесс синхронизации. Первый из инициированных извне автоматов переходит в состояние 1 и, сталкиваясь с автоматами, находящимися в состоянии 0, будет переводить их в состояние 1. Этот процесс обеспечит лавинообразное распространение переходов в со­стояние 1 в совокупности автоматов. Автомат в со­стоянии 1 сменит его на состояние 2, если он встре­тит автомат, находящийся также в состоянии 1, и вероятность этого события равна доле автоматов в состоянии 1. Если же автомат, в состоянии 2, встре­тится с автоматом в состоянии 0, то он возвратится

162

в состояние 1. Таким образом, если скорость пере­хода автоматов из состояния 0 в состояние 1 линей­но нарастает с ростом доли автоматов, находящихся в состоянии 1, то скорость перехода из состояния 1 в состояние 2, грубо говоря, возрастает, как корень квадратный от этой доли. И вообще, если в сово­купности имеется некоторое распределение автома­тов по номерам состояний, то доля автоматов с ма­лыми номерами состояний уменьшается с гораздо большей скоростью, чем увеличивается доля автома­тов с большими номерами состояний. Можно ожи­дать, что по мере продвижения этого распределения по номерам, его разброс будет возрастать. Иными словами, распределение автоматов по номерам будет «сгущаться» относительно номера текущего среднего состояния.

Это предположение подтверждается как матема­тическим анализом, так и результатами моделирова­ния поведения такой совокупности на ЭВМ. При моделировании в качестве одного такта выбиралось время, в течение которого все автоматы по одному разу вступают во взаимодействие. Тогда, например, в совокупности из 1024 автоматов при числе состоя­ний каждого автомата, равном 15, в 400 эксперимен­тах все автоматы переходили в синхронное состояние. Существенно здесь математическое доказательство независимости требуемого при данном е числа со­стояний автомата от общего числа автоматов в со­вокупности. Этот факт доказан для достаточно боль­ших размеров совокупности и достаточно малых e. Однако это отнюдь не умаляет содержательного значения полученных результатов.

Результаты настоящего параграфа кажутся уди­вительными. Казалось бы, с ростом размера сово­купности задача согласования поведения должна усложняться, однако существуют весьма простые правила случайного взаимодействия, которые обес­печивают синхронизацию реакции совокупности на информацию, поступившую только одному индивиду­уму. Обеспечивающие этот эффект процессы, в ко­торых отстающие подтягиваются, а убежавшие впе­ред тормозятся, можно назвать процессами синхрофазировки . Возможно, что аналоги синхрофазировки встречаются и в эволюционных процессах. Случай­ные изменения, возникающие у отдельных индивиду-

                                            163

 

умов вследствие случайных парных взаимодействий, распространяются по всей популяции и синхронно проявляются при возникновении соответствующих условий.

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться: