Реферат: Распределенные алгоритмы

 Имеются несколько журналов и ежегодных конференций, которые специализируются на результатах распределенных алгоритмов и распределенных вычислений. Некоторые другие журналы и конференции не специализируются исключительно по этому предмету, но тем не менее содержат много публикаций в этой области. Ежегодный симпозиум по Принципам распределенного вычисления (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 модель, которая будет использоваться в большинстве более поздних глав,  представляется. Модель является, и достаточно общей, чтобы быть подходящей для разработки и проверки алгоритмов и достаточно плотной для доказательства результатов невозможности. Это основано на понятии систем перехода, для которых правила доказательства свойств безопасности и живости могут быть даны легко. Понятие причинной связи как частичного порядока на событиях вычисления представляется, и определены логические часы.

  В Главе 3 проблема передачи сообщения между двумя узлами рассматривается. Сначала семейство протоколов для обмена пакетами над одиночной связью обеспечено, и доказательство правильности, по Schoone, дано. Также, протокол по Fletcher и Watson рассматривается, правильность которого полагается на правильное использование таймеров. Обработка этого протокола показывается, как метод проверки может применяться к протоколам, основанным на использовании таймеров. Глава 4 рассматривает проблему маршрутизации в компьютерных сетях. Она сначала представляет некоторую общую теорию относительно маршрутизации и алгоритма Toueg для вычисления маршрутизации таблиц. Также обрабатываемый - Netchange алгоритм Tajibnapis и доказательства правильности для этого алгоритма, данного Lamport. Эта глава заканчивается компактными алгоритмами маршрутизации, включая интервал и префиксную маршрутизацию. Эти алгоритмы названы компактными алгоритмами маршрутизации, потому что они требуют только маленького количества памяти в каждом узле сети. Обсуждение протоколов для компьютерных сетей заканчивается некоторыми стратегиями для ухода от тупиков с промежуточным накоплением в компьютерных сетях с коммутацией пакетов в Главе 5. стратегии основаны при определении свободных от циклов направленных графов на буферах в узлах сети, и показано, как такой граф может быть создан, используя только скромное количество буферов в каждом узле.

Часть 2: Фундаментальные Алгоритмы. Эта часть представляет ряд алгоритмических "строительных блоков", которые используются как процедуры во многих распределенных прикладных программах, и разрабатывает теорию относительно вычислительной мощности различных сетевых предложений. Глава 6 определяет понятие " волновой алгоритм ", который является обобщенной схемой посещения всех узлов сети. Волновые алгоритмы используются, чтобы распространить информацию через сеть, синхронизировать узлы, или вычислять функцию, которая зависит от распространения информации над всеми узлами. Поскольку это соберется в более поздних главах, много проблем распределенного  управления могут быть решены в соответствии с очень общими алгоритмическими схемами, в которых волновой алгоритм используется как компонент. Эта глава также определяет сложность времени распределенных алгоритмов и исследует время и сложность сообщения ряда распределенных алгоритмов поиска в глубину.

Фундаментальная проблема в распределенных системах - выбор: Выбор одиночного процесса, который должен запустить различаемую роль в последующем вычислении. Эта проблема изучается в Главе 7. Сначала проблема изучается для кольцевых сетей, где показано, что сложность сообщения проблемы - O (NlogN) сообщений (на кольце N процессоров). Проблема также изучается для общих сетей, и некоторые конструкции показываются,  к которым алгоритмы выбора могут быть получены из волновых алгоритмов и алгоритмов обхода. Эта глава также обсуждает алгоритм для конструкции охвата дерева Gallager и другие.

 Вторая фундаментальная проблема - обнаружение завершения, распознавание (процессами непосредственно) того, что распределенное вычисление завершено. Эта проблема изучается в Главе 8. Нижняя граница сложности решения этой проблемы доказана, и несколько алгоритмов обсуждены подробно. Глава включает некоторые классические алгоритмы (например.,  Dijkstra, Feijen, и Van Gasteren и Dijkstra и Scholten) и снова конструкция дана для получения алгоритмов для этой проблемы из волновых алгоритмов.

 Глава 9 изучает вычислительную мощность систем, где процессы не различаются уникальными идентификаторами. Как показал Angluin, что в этом случае много вычислений не могут быть выполнены детерминированным алгоритмом. Глава представляет вероятностные алгоритмы, и мы исследуем какие проблемы, могут быть решены этими алгоритмами.

 Глава 10 объясняет, как процессы системы могут вычислять глобальное "изображение", снимок состояния системы. Такой кадр полезен для определения свойств вычисления, типа того, произошел ли тупик, или как далеко вычисление прогрессировало.

 В Главе 11 эффект доступности понятия глобального времени будет изучаться. Несколько степеней синхронизма будут определены, и будет показано, что полностью асинхронные системы могут моделировать полностью синхронные довольно тривиальными алгоритмами. Таким образом замечено, что предположения относительно синхронизма не влияют на совокупность функций, которые являются вычислимыми распределенной системой. Будет впоследствии показываться, однако, что имеется влияние на сложность связи многих проблем: чем лучше синхронизм сети, тем ниже сложность алгоритмов для этих проблем.

Часть 3: Отказоустойчивость. В практических распределенных системах возможность сбоя в компоненте не может игнорироваться, и следовательно важно изучить, как хорошо алгоритм ведет себя, если компоненты терпят неудачу. Этот предмет будет обрабатываться в последней части книги; короткое введение в предмет дано в Главе 12. Отказоустойчивость асинхронных систем изучается в Главе 13. Результат Fischer и других обеспечен; показывается, что детерминированные асинхронные алгоритмы не могут справляться с даже очень скромным типом сбоя, аварийным отказом одиночного процесса. Будет также показано, что с более слабыми типами неисправностей можно иметь дело, и что некоторые задачи являются разрешимыми несмотря на сбой типа аварийного отказа. Алгоритмы Bracha и Toueg будут обеспечены: оказывается, напротив, рандомизированные асинхронные системы,  способны справиться с приемлемо большим количеством сбоев. Таким образом замечено, что имеет место для надежных систем (см. Главу 9), рандомизированные алгоритмы предлагают большее количество возможностей чем детерминированные алгоритмы.

 В Главе 14 отказоустойчивость синхронных алгоритмов будет изучаться. Алгоритмы Lamport и другие показали, что детерминированные синхронные алгоритмы могут допустить нетривиальные сбои. Таким образом замечено, что, в отличие от случая надежных систем (см Главу 11), синхронные системы предлагают большее количество возможностей чем асинхронные системы. Даже большее число неисправностей может допускаться, если процессы способны "подписаться" на связь к другим процессам. Следовательно, выполнение синхронизма в ненадежной системе больше усложнено, чем в надежном случае. И последний раздел Главы 14 будет посвящен этой проблеме.

 Другой подход к надежности, а именно через само-стабилизацию алгоритмов, сопровождается в Главе 15. Алгоритм стабилизируется, если, независимо от начальной конфигурации, он сходится в конечном счете к предназначенному поведению. Некоторая теория относительно стабилизации алгоритмов будет разработана, и ряд алгоритмов стабилизации будет обеспечен. Эти алгоритмы включают протоколы для нескольких алгоритмов графа типа вычисления дерева поиска в глубину (как в Разделе 6.4) и вычисления таблиц маршрутизации (как в Главе 4). Также, стабилизационные алгоритмы для передачи данных (как в Главе 3) были предложены. Это может означать, что все компьютерные сети могут быть выполнены, c использованием стабилизационых алгоритмов.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105