Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 87
Текст из файла (страница 87)
упражнения 9.1 и 9.2.Свод характеристик и параметров. В этой главе все алгоритмы можноклассифицировать согласно следующим четырем критериям; мы коротко отметим, алгоритмы какого типа представляются более привлекательными.1. Известный или неизвестный размер сети. Алгоритмы, не опирающиеся на осведомленность о числе N, более предпочтительны, поскольку они являются более общими.2. Завершение по приему сообщений или по работе процессов.
Алгоритмы, завершающиеся по признаку окончания работы процессов, более предпочтительны, поскольку их завершение явно выражено и процессы могут использоватьвычисленный результат.3. Детерминированный или вероятностный. Детерминированные алгоритмы более предпочтительны, поскольку в них не используется генератор случайных чисел и, кроме того, свойства корректности, которым удовлетворяют такие алгоритмы, являются более сильными, нежели те, которым удовлетворяюталгоритмы типа Лас-Вегас и Монте-Карло.4.
Тип Лас-Вегас или Монте-Карло. Алгоритмы типа Лас-Вегас обычно представляются более привлекательными, поскольку завершение с некоторойвероятностью этих алгоритмов в практических ситуациях почти не отличимо отобычного завершения.9.1.3. Задачи, рассматриваемые в этой главеНаша цель состоит не в том, чтобы дать полное изложение теории вычислений на анонимных сетях, включая многочисленные результаты, которые былиполучены для этих сетей. Мы хотим лишь исследовать вычислительные возможности указанных сетей применительно к задачам избрания и вычисления функций,включая вычисление размера сети.Эти задачи относятся к числу фундаментальных. Если можно избрать лидера, анонимная сеть будет обладать точно такими же вычислительными возможностями, как и сеть с именами, поскольку процессы можно именовать припомощи централизованного алгоритма, как это показано далее.
В § 9.5.3 будетпоказано, что лидер может быть избран при помощи вероятностного алгоритма,если известен размер сети, и это указывает на важность задачи о вычисленииразмера сети. Так как размер сети может быть легко вычислен централизованным алгоритмом (как это будет показано далее), задачи избрания и вычисленияразмера сети эквивалентны. Будет показано, что размер сети нельзя вычислитьвероятностно, а задача о выборах неразрешима, если размер сети неизвестен.Централизованные вычисления. Размер сети может быть легко вычисленпри помощи одного-единственного вычисления алгоритма эха, если в распоряжении имеется единственный стартовый процесс (leader).
Каждое сообщение,330Гл. 9. Анонимные сетиотправляемое назад по остовному дереву, несет информацию о числе процессовв поддереве, корнем которого является процесс-отправитель; см. алгоритм 9.1.var recpfatherpsizep: integer init 0 ; (* Счетчик числа полученных сообщений *):Pinit udef ;: integer init 1 ; (* Размер поддерева с корнем p *)Для инициатора:begin forall q ∈ Neighp do send htok, 0i to q ;while recp < #Neighp dobegin receive htok, si ; recp := recp + 1 ;sizep := sizep + send (* Размер сети равен sizep *)endДля неинициаторов:begin receive htok, si from neighbor q ; fatherp := q ; recp := recp + 1 ;forall r ∈ Neighp , r 6= fatherp do send htok, 0i to r ;while recp < #Neighp dobegin receive htok, si ; recp := recp + 1 ;sizep := sizep + send;send htok, sizep i to fatherpendАлгоритм 9.1.
Централизованное вычисление размера сетиЧтобы назначить процессам уникальные имена, сначала вычисляется размерсети при помощи алгоритма 9.1, после чего отрезок натурального ряда {0, . . . , N−1}разделяется между процессами и каждое поддерево получает свой отрезок, длинакоторого соответствует его размеру.Теорема 9.3.
Существует детерминированный централизованный алгоритм вычисления размера сети, который требует 2|E| обменов сообщениями и имеет сложность по времени, составляющую величину O(N). Существует детерминированный централизованный алгоритм назначенияуникальных имен процессам сети, который требует 2|E| + (N − 1) обменов сообщениями и имеет сложность по времени, составляющую величинуO(N).Существует и более эффективный алгоритм назначения имен; см. упражнение 9.3. Как следует из теоремы 9.3, доступность лидера может со сравнительнонебольшими издержками компенсировать отсутствие уникальных имен. Поэтомупри изучении анонимных сетей предполагается, что наряду с отсутствием именв сети нет и лидера.9.2.
Детерминированные алгоритмы3319.1.4. Синхронный и асинхронный обмен сообщениями.Результаты, связанные c выборами лидера на анонимных кликах, оказываются существенно зависящими от того, какого типа взаимосвязь проводится —с синхронным или асинхронным обменом сообщениями. При синхронном обменесообщениями два процесса совместно участвуют в осуществлении единого перехода системы, и при этом симметрия между этими двумя процессами может бытьразрушена.Теорема 9.4. Для сети, состоящей из двух процессов, взаимодействующих путем синхронного обмена сообщениями, существует детерминированный алгоритм избрания лидера, завершающийся по признаку окончания работы процессов.Д о к а з а т е л ь с т в о. Каждый процесс имеет три состояния, а именно sleep,leader, и lost, причем начальным состоянием является sleep. Каждый процессможет либо отправить сообщение и перейти в заключительное состояние leader,либо принять сообщение и перейти в заключительное состояние lost.В соответствии с этим система имеет девять конфигураций, из которых лишьтри являются достижимыми; из начальной конфигурации (sleep, sleep) системаможет перейти в конфигурации (leader, lost) и (lost, leader).
В каждой из этихдвух конфигураций процессы завершили работу, и при этом в точности один изних пребывает в состоянии leader, в то время как другой пребывает в состоянииlost.Этот алгоритм позаимствован из работы Энглуин [8] ; она также обобщила данный алгоритм для случая клик произвольного размера. Если взаимосвязьосуществляется посредством асинхронного обмена сообщениями, то эта задачане имеет детерминированного алгоритма решения; это может быть установленопутем проведения рассуждений, аналогичнымх тем, которые будут использованыпри доказательстве теоремы 9.5.
Мы не хотим рассматривать решения, в которыхсимметрия разрушается за счет особенностей механизма взаимосвязи; поэтомумы ограничимся рассматрением систем, в которых взаимосвязь осуществляетсяпосредством асинхронного обмена сообщениями.То решение, которое предложила Энглуин, очень существенно зависит от топологии; оно не пригодно, например, для кольцевых сетей.
Результаты о невозможности получения некоторых решений, рассматриваемые в этой главе, будутобобщены для систем с синхронным обменом сообщениями в сетях с произвольной и кольцевой топологией.Симметрия между двумя процессами может быть разрушена детерминированно, если сообщения передаются синхронно. Отсюда следует, что не существуетдетерминированного алгоритма, способного реализовать синхронный обмен сообщениями в анонимных сетях, в которых проводится асинхронный обмен сообщениями.9.2. Детерминированные алгоритмы332Гл. 9.
Анонимные сетиВ этом параграфе представлены некоторые результаты, касающиеся детерминированных алгоритмов. Наиболее важным является следующий отрицательныйрезультат: избрать лидера детерминированно невозможно даже в том случае, когда речь идет о кольцевой сети, размер которой заранее известен. Будет такжепоказано, что вычислять функции можно при условии, что размер кольца известен, и невозможно, если размер кольца неизвестен заранее.9.2.1. Детерминированные выборы: отрицательныерезультатыВ этом параграфе будет показано, что провести детерминированные выборылидера в анонимных сетях невозможно. Доказательство проводится с использованием понятия симметрической конфигурации.
Показано, что существуетвычисление, которое берет начало в симметрической конфигурации и достигаетсимметрической конфигурации через каждые N шагов. Невозможность получения детерминированного решения следует из того, что корректный алгоритм незавершает работу в симметрической конфигурации.Теорема 9.5. Не существует детерминированного алгоритма избрания лидера в анонимном кольце, размер которого заранее неизвестен.Д о к а з а т е л ь с т в о.
Мы приведем доказательство этого утверждения дляслучая однонаправленных колец, но если идея этого доказательства станет ясна,то распространить обоснование на случай двунаправленных колец не составиттруда. Предположим, что ряд процессов, начинающийся процессом p 0 и оканчивающийся процессом pN−1 , образует кольцо так, что для каждого i < N − 1процесс pi может отправлять сообщения процессу pi+1 и процесс pN−1 можетотправлять сообщения процессу p0 .
В конфигурации данного кольца обозначимсимволом ci состояние процесса pi , а символом Mi — совокупность сообщений,адресованных процессу pi .Конфигурацию будем называть симметрической, если состояния всех процессов одинаковы и также одинаковы множества сообщений, адресованных каждому процессу и пребывающих на этапе пересылки, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
