Распределенные алгоритмы
Категория реферата: Рефераты по информатике, программированию
Теги реферата: налоги и налогообложение, план дипломной работы
Добавил(а) на сайт: Ноздрин.
Предыдущая страница реферата | 7 8 9 10 11 12 13 14 15 16 17 | Следующая страница реферата
2. NCP A timeout, retransmit ( data, m, x)
3. NCP B receive ( data, m, a:) (sent in step 2), send (ack, x,y1 )
4. NCP A receive ( ack, x, y1 ), notify, send { close, x, y1 ), close
5. NCP B receive (close, x, yi ), deliver m, close
6. NCP B receive (data, m, x ) (sent in step 1), send ( ack, x, у2)
7. NCP A receive ( ack, x, y2), reply { nocon, x, y2)
8. NCP B receive ( nocon, x,y2) in reply to ( ack, x, y2 ), deliver m, close
Сеанс связи с четырьмя сообщениями. Доставки информации из старых сеансов связи можно избегать при наличии NCPs, взаимно согласующих их числа идентификации сеанса связи прежде, чем любые данные будут поставлены, как в следующем сеансе связи.
1. NCP A send ( data, m, x )
2. NCP B receive ( data, m, x ), send ( open, x, у )
3. NCP A receive ( open, x, у ), send ( agree, x, у )
4. NCP B receive (agree, x, y), deliver m, send (ack, x, y), close
5. NCP A receive (ack, x, y), notify, close
Возможность аварийного отказа NCP В вынуждает обработку ошибок быть
такой, что дубликат может все еще происходить, даже, когда никакой NCP
фактически не терпит крах. Сообщение об ошибках (nocon, x, y) послано NCP В
когда сообщение (agree, x, y) получено, и никакой сеанс связи не открыт.
Предположим, что NCP A не получает сообщение (ack, x, y), даже после
несколько перепередач {agree, x, y) ; только сообщения (nocon, x, y)
получены. Так как возможно, что NCP В потерпел крах прежде, чем он получил
(agree, x, y), NCP вынужден запустить новый сеанс связи (посылая {data, m, x}) чтобы предотвратить потерю m! Но также возможно, что NCP В уже доставил
m, и сообщение (ack, x, y) было потеряно, тогда появляется дубликат.
Возможно изменить протокол таким образом, что NCP A уведомляет и
закрывается после получения сообщения {nocon, x, y); это предотвращает
дубликаты, но может представлять потерю, которая рассматривается даже менее
желательной.
Сеанс связи c пятью сообщениями и сравнение. Beisnes [Bel76] дает
протокол с пятью сообщениями, который не теряет информацию, и это
представляет дубликаты только, если NCP фактически терпит крах.
Следовательно, это - самый лучший возможный протокол, рассматриваемый в
свете того наблюдения, что никакая надежная связь не является возможной, ранее в этом подразделе. Из-за чрезмерных накладных расходов (пять
сообщений проходят через NCPs, чтобы передать один информационный модуль), должно быть подвергнуто сомнению, должен ли протокол с пятью сообщениями
действительно быть предпочтен намного более простому протоколу с двумя
сообщениями. Действительно, потому что даже протокол с пятью сообщениями
может представлять дубликаты (когда сбоят NCP), уровень процесса должны
иметь дело с ними так или иначе. Так получается, что протокол c двумя
сообщениями, который может представлять дубликаты, но может быть сделан
свободным от потерь, если идентификации сеанса связи добавлены, как мы
делали для протокола с тремя сообщениями, можем также использоваться.
1.3.3 Область исследования
Имелось продолжающееся исследование в распределенных алгоритмах в
течение последнего двух десятилетий, и значительный прогресс был сделаны
особенно в течение 80-x. В предыдущих разделах мы указали на некоторые
технические достижения, которые стимулировали исследование в распределенных
алгоритмах, а именно, разработка компьютерных сетей (и глобальных и
локальных) и многопроцессорные компьютеры. Первоначально исследование было
очень нацелено к прикладному применению алгоритмов в глобальных сетях, но в
настоящее время разработаны четкие математические модели, позволяющие
прикладное применение результатов и методов к более широким классам
распределенных сред. Однако, исследование поддерживает плотные связи с
достижениями техники в методах связи, потому что результаты в алгоритмах
часто чувствительны к изменениям в сетевой модели. Например, доступность
дешевых микропроцессоров сделала возможным создать системы с многими
идентичными процессорами, которые стимулировали изучение " анонимных сети "
(см. Главу 9).
Имеются несколько журналов и ежегодных конференций, которые
специализируются на результатах распределенных алгоритмов и распределенных
вычислений. Некоторые другие журналы и конференции не специализируются
исключительно по этому предмету, но тем не менее содержат много публикаций
в этой области. Ежегодный симпозиум по Принципам распределенного вычисления
(PoDC) организовывался каждый год начиная с 1982 до времени записи в
Северной Америке, и слушания изданы Ассоциацией для Вычисления Машин.
Международные Симпозиумы по распределенным алгоритмам (WDAG) были проведены
в Оттаве (1985), Амстердаме (1987), Ницце (1989), Bari (1990), Delphi
(1991), Хайфе (1992), Lausanne (1993), и Terschelling (1994). С 1989, симпозиумы проводились ежегодно и слушания были изданы Springer-Verlag в
сериях Примечания по лекциям по информатике. Ежегодные симпозиумы на теории
вычисления (SToC) и основ информатики (FoCS) покрывают все фундаментальные
области информатики, и часто несут статьи об распределенном вычислении.
Слушания SToC встреч изданы Ассоциацией для Вычисления Машин, и таковых
FoCS встреч институтом IEEE. Журнал Параллельного и Распределенного
Вычисления (JPDC) и Распределенного Вычисления издает распределенные
алгоритмы регулярно, и делает Письма по обработке информации (IPL).
1.3.4 Иерархическая структура книги
Эта книга была написана со следующими тремя целями в памяти.
(1) Сделать читателя знакомым с методами, которые могут использоваться, чтобы исследовать свойства данного распределенного алгоритма, анализировать и решать проблему которая возникает в контексте распределенных систем, или оценивать качества специфической сетевой модели.
(2) чтобы обеспечить понимание в свойственных возможностях и
невозможности нескольких моделей системы. Воздействие доступности
глобального кадра времени изучается в Разделе 3.2 и в Главах 11 и 14.
Воздействие знания процессами их идентичности изучается в Главе 9.
Воздействие требования завершения процесса изучается в Главе 8. Воздействие
сбоев процесса изучается в части 3.
(3) Представлять совокупность недавнего современного состояния распределенных алгоритмов, вместе с их проверкой и анализом их сложности.
Где предмет не может обрабатываться в полных подробностях, ссылки к релевантной научной литературе даны. Материал, собранный в книге разделен в три части: Протоколы, Фундаментальные Алгоритмы, и Отказоустойчивость.
Часть 1: Протоколы. Эта часть имеет дело с протоколами связи, используемыми в реализации компьютерных сетей связи и также представляет
методы, используемые в более поздних частях. В Главе 2 модель, которая
будет использоваться в большинстве более поздних глав, представляется.
Модель является, и достаточно общей, чтобы быть подходящей для разработки и
проверки алгоритмов и достаточно плотной для доказательства результатов
невозможности. Это основано на понятии систем перехода, для которых правила
доказательства свойств безопасности и живости могут быть даны легко.
Понятие причинной связи как частичного порядока на событиях вычисления
представляется, и определены логические часы.
Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини.
Предыдущая страница реферата | 7 8 9 10 11 12 13 14 15 16 17 | Следующая страница реферата