Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не следует путать с децентрализованными вычислениями .
«Распределенное приложение» перенаправляется сюда. Для приложений без доверия см. Децентрализованное приложение .
«Распределенная обработка информации» перенаправляется сюда. Для компьютерной компании см. DIP Research .

Распределенные вычисления - это область информатики , изучающая распределенные системы. Распределенная система представляет собой систему, компоненты которой расположены на разных компьютерах сети , которые взаимодействуют и координируют свои действия, передавая сообщения друг с другом из любой системы. [1] Компоненты взаимодействуют друг с другом для достижения общей цели. Три важных характеристики распределенных систем: параллельность компонентов, отсутствие глобальных часов и независимый отказ компонентов. [1] Примеры распределенных систем варьируются от систем на основе SOA до многопользовательских онлайн-игр.в одноранговые приложения .

Компьютерная программа , которая работает в рамках распределенной системы называется распределенной программой (и распределенное программирование является процессом написания таких программ). [2] Существует множество различных типов реализаций механизма передачи сообщений, включая чистый HTTP, RPC-подобные соединители и очереди сообщений . [3]

Распределенные вычисления также относятся к использованию распределенных систем для решения вычислительных задач. В распределенных вычислениях проблема делится на множество задач, каждая из которых решается одним или несколькими компьютерами [4], которые взаимодействуют друг с другом посредством передачи сообщений. [5]

Введение [ править ]

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

Хотя единого определения распределенной системы не существует, [7] обычно используются следующие определяющие свойства:

  • Существует несколько автономных вычислительных объектов ( компьютеров или узлов ), каждый из которых имеет собственную локальную память . [8]
  • Сущности общаются друг с другом посредством передачи сообщений . [9]

Распределенная система может иметь общую цель, такую ​​как решение большой вычислительной задачи; [10] пользователь затем воспринимает набор автономных процессоров как единое целое. В качестве альтернативы, каждый компьютер может иметь своего пользователя с индивидуальными потребностями, и цель распределенной системы - координировать использование общих ресурсов или предоставлять услуги связи пользователям. [11]

Другие типичные свойства распределенных систем включают следующее:

  • Система должна терпеть отказы отдельных компьютеров. [12]
  • Структура системы (топология сети, задержка в сети, количество компьютеров) заранее не известна, система может состоять из разных типов компьютеров и сетевых каналов, и система может меняться во время выполнения распределенной программы. [13]
  • Каждый компьютер имеет только ограниченное, неполное представление о системе. Каждый компьютер может знать только одну часть ввода. [14]

Параллельные и распределенные вычисления [ править ]

(а), (б): распределенная система.
(c): параллельная система.

Распределенные системы - это группы сетевых компьютеров, которые имеют общую цель в своей работе. Термины « параллельные вычисления », « параллельные вычисления » и «распределенные вычисления» во многом пересекаются, и между ними нет четкого различия. [15] Одна и та же система может быть охарактеризована как «параллельная» и «распределенная»; процессоры в типичной распределенной системе работают одновременно, параллельно. [16] Параллельные вычисления можно рассматривать как особую тесно связанную форму распределенных вычислений, [17] а распределенные вычисления можно рассматривать как слабо связанную форму параллельных вычислений. [7] Тем не менее, можно примерно классифицировать параллельные системы как «параллельные» или «распределенные», используя следующие критерии:

  • При параллельных вычислениях все процессоры могут иметь доступ к общей памяти для обмена информацией между процессорами. [18]
  • В распределенных вычислениях каждый процессор имеет свою собственную частную память ( распределенную память ). Обмен информацией осуществляется путем передачи сообщений между процессорами. [19]

Рисунок справа иллюстрирует разницу между распределенными и параллельными системами. Рисунок (а) представляет собой схематический вид типичной распределенной системы; система представлена ​​как топология сети, в которой каждый узел является компьютером, а каждая линия, соединяющая узлы, является каналом связи. На рисунке (b) показана та же самая распределенная система более подробно: каждый компьютер имеет свою собственную локальную память, а обмен информацией можно осуществлять только путем передачи сообщений от одного узла к другому с использованием доступных каналов связи. На рисунке (c) показана параллельная система, в которой каждый процессор имеет прямой доступ к общей памяти.

Ситуация дополнительно осложняется традиционным использованием терминов параллельный и распределенный алгоритм, которые не совсем соответствуют приведенным выше определениям параллельных и распределенных систем (см. Ниже для более подробного обсуждения). Тем не менее, как показывает практика, высокопроизводительные параллельные вычисления в мультипроцессоре с общей памятью используют параллельные алгоритмы, в то время как координация крупномасштабной распределенной системы использует распределенные алгоритмы. [20]

История [ править ]

Использование параллельных процессов, которые обмениваются данными посредством передачи сообщений, уходит корнями в архитектуры операционных систем, изучаемые в 1960-х годах. [21] Первыми широко распространенными распределенными системами были локальные сети, такие как Ethernet , изобретенный в 1970-х годах. [22]

ARPANET , один из предшественников Интернета , был представлен в конце 1960-х годов, а электронная почта ARPANET была изобретена в начале 1970-х годов. Электронная почта стала наиболее успешным приложением ARPANET [23] и, вероятно, первым примером крупномасштабного распределенного приложения . Помимо ARPANET (и его преемника, глобального Интернета), другие ранние всемирные компьютерные сети включали Usenet и FidoNet с 1980-х годов, которые использовались для поддержки распределенных дискуссионных систем. [24]

Изучение распределенных вычислений стало отдельной отраслью компьютерных наук в конце 1970-х - начале 1980-х годов. Первая конференция в этой области, Симпозиум по принципам распределенных вычислений (PODC), датируется 1982 годом, а аналогичный ей Международный симпозиум по распределенным вычислениям (DISC) впервые был проведен в Оттаве в 1985 году как Международный семинар по распределенным алгоритмам на графах. [25]

Архитектура [ править ]

Для распределенных вычислений используются различные аппаратные и программные архитектуры. На более низком уровне необходимо соединить несколько процессоров с помощью какой-либо сети, независимо от того, напечатана ли эта сеть на печатной плате или состоит из слабо связанных устройств и кабелей. На более высоком уровне необходимо связать процессы, выполняющиеся на этих процессорах, с помощью какой-то системы связи . [26]

Распределенное программирование обычно относится к одной из нескольких базовых архитектур: клиент-серверная , трехуровневая , n- ступенчатая или одноранговая ; или категории: слабая связь или сильная связь . [27]

  • Клиент – сервер : архитектуры, в которых интеллектуальные клиенты связываются с сервером для получения данных, затем форматируют и отображают их для пользователей. Ввод на клиенте передается обратно на сервер, когда он представляет собой постоянное изменение.
  • Трехуровневый : архитектуры, которые перемещают клиентский интеллект на средний уровень, чтобы можно было использовать клиентов без сохранения состояния. Это упрощает развертывание приложений. Большинство веб-приложений являются трехуровневыми.
  • n -tier : архитектуры, которые обычно относятся к веб-приложениям, которые направляют свои запросы в другие корпоративные службы. Этот тип приложений является наиболее ответственным за успех серверов приложений .
  • Одноранговая сеть: архитектуры, в которых нет специальных машин, которые предоставляют услуги или управляют сетевыми ресурсами. [28] : 227 Вместо этого все обязанности равномерно разделены между всеми машинами, известными как одноранговые узлы. Пиры могут служить как клиентами, так и серверами. [29] Примеры этой архитектуры включают BitTorrent и сеть биткойнов .

Другой базовый аспект архитектуры распределенных вычислений - это способ взаимодействия и координации работы между параллельными процессами. Посредством различных протоколов передачи сообщений процессы могут напрямую связываться друг с другом, как правило, во взаимоотношениях главный / подчиненный . В качестве альтернативы, архитектура, ориентированная на базу данных, может позволить выполнять распределенные вычисления без какой-либо формы прямого межпроцессного взаимодействия , используя общую базу данных . [30]Архитектура, ориентированная на базы данных, в частности, обеспечивает аналитику реляционной обработки в схематической архитектуре, позволяя ретранслировать живую среду. Это позволяет выполнять функции распределенных вычислений как внутри, так и за пределами параметров сетевой базы данных. [31]

Приложения [ править ]

Причины использования распределенных систем и распределенных вычислений могут включать:

  1. Сама природа приложения может потребовать использования сети связи, которая соединяет несколько компьютеров: например, данные, производимые в одном физическом месте и требуемые в другом месте.
  2. Во многих случаях использование одного компьютера в принципе возможно, но использование распределенной системы выгодно по практическим причинам. Например, может быть более рентабельным получить желаемый уровень производительности при использовании кластера из нескольких компьютеров низкого уровня по сравнению с одним компьютером высокого класса. Распределенная система может обеспечить большую надежность, чем нераспределенная система, поскольку в ней нет единой точки отказа . Более того, распределенную систему легче расширять и управлять ею, чем монолитную однопроцессорную систему. [32]

Примеры [ править ]

Примеры распределенных систем и приложений распределенных вычислений включают следующее: [33]

  • телекоммуникационные сети:
    • телефонные сети и сотовые сети ,
    • компьютерные сети, такие как Интернет ,
    • беспроводные сенсорные сети ,
    • алгоритмы маршрутизации ;
  • сетевые приложения:
    • Всемирная паутина и одноранговые сети ,
    • массовые многопользовательские онлайн-игры и сообщества виртуальной реальности ,
    • распределенные базы данных и системы управления распределенными базами данных ,
    • сетевые файловые системы ,
    • распределенный кеш, такой как пакетные буферы ,
    • системы распределенной обработки информации, такие как банковские системы и системы бронирования авиабилетов;
  • управление процессом в реальном времени:
    • системы управления самолетом ,
    • системы промышленного управления ;
  • параллельное вычисление :
    • научных вычислений , в том числе кластерных вычислений , распределенных вычислений , облачных вычислений , [34] и различные волонтерские вычислительные проекты (см список распределенных вычислительных проектов ),
    • распределенный рендеринг в компьютерной графике.

Теоретические основы [ править ]

Основная статья: Распределенный алгоритм

Модели [ править ]

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

Теоретическая информатика стремится понять, какие вычислительные проблемы можно решить с помощью компьютера ( теория вычислимости ) и насколько эффективно ( теория сложности вычислений ). Традиционно говорят, что проблема может быть решена с помощью компьютера, если мы можем разработать алгоритм, который дает правильное решение для любого конкретного случая. Такой алгоритм может быть реализован в виде компьютерной программы, которая запускается на универсальном компьютере: программа считывает экземпляр проблемы с ввода , выполняет некоторые вычисления и выдает решение на выходе . Формализмы, такие как машины с произвольным доступом или универсальные машины Тьюринга.могут использоваться как абстрактные модели последовательного компьютера общего назначения, выполняющего такой алгоритм. [35] [36]

Область параллельных и распределенных вычислений изучает аналогичные вопросы в случае нескольких компьютеров или компьютера, который выполняет сеть взаимодействующих процессов: какие вычислительные задачи могут быть решены в такой сети и насколько эффективно? Однако совсем не очевидно, что подразумевается под «решением проблемы» в случае параллельной или распределенной системы: например, какова задача разработчика алгоритма и что является параллельным или распределенным эквивалентом последовательного универсальный компьютер? [ необходима цитата ]

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

Обычно используются три точки зрения:

Параллельные алгоритмы в модели с общей памятью
  • Все процессоры имеют доступ к общей памяти. Разработчик алгоритма выбирает программу, выполняемую каждым процессором.
  • Одна из теоретических моделей - это используемые параллельные машины с произвольным доступом (PRAM). [37] Однако классическая модель PRAM предполагает синхронный доступ к разделяемой памяти.
  • Программы с общей памятью могут быть расширены до распределенных систем, если базовая операционная система инкапсулирует связь между узлами и виртуально объединяет память во всех отдельных системах.
  • Модель, которая ближе к поведению реальных многопроцессорных машин и учитывает использование машинных инструкций, таких как сравнение и замена (CAS), - это модель асинхронной общей памяти . По этой модели проведено большое количество работ, краткое изложение которых можно найти в литературе. [38] [39]
Параллельные алгоритмы в модели передачи сообщений
  • Разработчик алгоритма выбирает структуру сети, а также программу, выполняемую каждым компьютером.
  • Используются такие модели, как логические схемы и сортировочные сети . [40] Логическую схему можно рассматривать как компьютерную сеть: каждый вентиль - это компьютер, на котором выполняется чрезвычайно простая компьютерная программа. Точно так же сортировочную сеть можно рассматривать как компьютерную сеть: каждый компаратор - это компьютер.
Распределенные алгоритмы в модели передачи сообщений
  • Разработчик алгоритма выбирает только компьютерную программу. На всех компьютерах запущена одна и та же программа. Система должна корректно работать независимо от структуры сети.
  • Обычно используемой моделью является граф с одним конечным автоматом на узел.

В случае распределенных алгоритмов вычислительные проблемы обычно связаны с графами. Часто график , который описывает структуру компьютерной сети является экземпляром проблемы. Это показано в следующем примере. [ необходима цитата ]

Пример [ править ]

Рассмотрим вычислительную задачу нахождения расцветку данного графа G . В разных полях могут использоваться следующие подходы:

Централизованные алгоритмы [ необходима ссылка ]
  • Граф G кодируется как строка, и строка передается в качестве входных данных для компьютера. Компьютерная программа находит раскраску графа, кодирует раскраску в виде строки и выводит результат.
Параллельные алгоритмы
  • Опять же, граф G кодируется как строка. Однако несколько компьютеров могут обращаться к одной и той же строке параллельно. Каждый компьютер может сосредоточиться на одной части графика и раскрасить эту часть.
  • Основное внимание уделяется высокопроизводительным вычислениям, использующим вычислительную мощность нескольких компьютеров параллельно.
Распределенные алгоритмы
  • Граф G - это структура компьютерной сети. Существует один компьютер для каждого узла G и одной линии связи для каждого ребра G . Первоначально каждый компьютер знает только о своих ближайших соседях в графе G ; компьютеры должны обмениваться сообщениями друг с другом , чтобы узнать больше о структуре G . Каждый компьютер должен выдавать свой собственный цвет.
  • Основное внимание уделяется координации работы произвольной распределенной системы. [ необходима цитата ]

Хотя область параллельных алгоритмов имеет другую направленность, чем область распределенных алгоритмов, между этими двумя областями существует много взаимодействия. Например, алгоритм Коула – Вишкина для раскраски графов [41] изначально был представлен как параллельный алгоритм, но тот же метод можно использовать непосредственно как распределенный алгоритм.

Более того, параллельный алгоритм может быть реализован либо в параллельной системе (с использованием общей памяти), либо в распределенной системе (с использованием передачи сообщений). [42] Традиционная граница между параллельными и распределенными алгоритмами (выбрать подходящую сеть или запускать в любой данной сети) не находится в том же месте, что и граница между параллельными и распределенными системами (общая память или передача сообщений).

Меры сложности [ править ]

В параллельных алгоритмах еще одним ресурсом, помимо времени и пространства, является количество компьютеров. Действительно, часто существует компромисс между временем работы и количеством компьютеров: проблему можно решить быстрее, если параллельно работает больше компьютеров (см. Ускорение ). Если проблема решения может быть решена за полилогарифмическое время с использованием полиномиального числа процессоров, то говорят, что проблема относится к классу NC . [43] Класс NC может быть определен одинаково хорошо, используя формализм PRAM или логические схемы - машины PRAM могут эффективно моделировать логические схемы и наоборот. [44]

При анализе распределенных алгоритмов обычно больше внимания уделяется коммуникационным операциям, чем вычислительным шагам. Возможно, самая простая модель распределенных вычислений - это синхронная система, в которой все узлы работают синхронно. Эта модель широко известна как ЛОКАЛЬНАЯ модель. Во время каждого цикла связи все узлы параллельно (1) получают последние сообщения от своих соседей, (2) выполняют произвольные локальные вычисления и (3) отправляют новые сообщения своим соседям. В таких системах основной мерой сложности является количество циклов синхронной связи, необходимых для выполнения задачи. [45]

Эта мера сложности тесно связана с диаметром сети. Пусть D - диаметр сети. С одной стороны, любая вычислимая проблема может быть тривиально решена в синхронной распределенной системе примерно за 2 D раунда связи: просто соберите всю информацию в одном месте ( D раундов), решите проблему и проинформируйте каждый узел о решении ( D раундов) ).

С другой стороны, если время работы алгоритма намного меньше, чем D раундов связи, то узлы в сети должны производить свои выходные данные, не имея возможности получить информацию об удаленных частях сети. Другими словами, узлы должны принимать глобально согласованные решения на основе информации, доступной в их локальной D-окрестности . Известно, что многие распределенные алгоритмы имеют время выполнения, намного меньшее, чем раунды D , и понимание того, какие проблемы могут быть решены с помощью таких алгоритмов, является одним из центральных вопросов исследования в этой области. [46] Обычно алгоритм, который решает задачу за полилогарифмическое время в размере сети, считается эффективным в этой модели.

Другой часто используемый показатель - это общее количество битов, переданных в сети (см. Сложность связи ). [47] Особенности этой концепции обычно фиксируются с помощью модели CONGEST (B), которая аналогична модели LOCAL, но в которой отдельные сообщения могут содержать только B битов.

Другие проблемы [ править ]

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

Существуют также фундаментальные проблемы, которые присущи только распределенным вычислениям, например, связанные с отказоустойчивостью . Примеры связанных проблем включают проблемы консенсуса , [48] византийскую отказоустойчивость , [49] и самостабилизацию . [50]

Многие исследования также сосредоточены на понимании асинхронной природы распределенных систем:

  • Синхронизаторы могут использоваться для запуска синхронных алгоритмов в асинхронных системах. [51]
  • Логические часы обеспечивают порядок событий до того, как произошло . [52]
  • Алгоритмы синхронизации часов обеспечивают глобально согласованные метки физического времени. [53]

Выборы [ править ]

Выборы координатора (или выборы лидера ) - это процесс обозначения единого процесса в качестве организатора некоторой задачи, распределенной между несколькими компьютерами (узлами). Перед тем, как задача будет запущена, все сетевые узлы либо не знают, какой из узлов будет служить «координатором» (или лидером) задачи, либо не могут связаться с текущим координатором. Однако после запуска алгоритма выбора координатора каждый узел сети распознает конкретный уникальный узел в качестве координатора задачи. [54]

Узлы сети обмениваются данными между собой, чтобы решить, кто из них перейдет в состояние «координатора». Для этого им нужен какой-то метод, чтобы нарушить симметрию между ними. Например, если каждый узел имеет уникальные и сопоставимые идентификаторы, тогда узлы могут сравнить свои идентификаторы и решить, что узел с наивысшим идентификатором является координатором. [54]

Определение этой проблемы часто приписывается ЛеЛанну, который формализовал ее как метод создания нового токена в сети Token Ring, в которой токен был утерян. [55]

Алгоритмы выбора координатора спроектированы так, чтобы быть экономными с точки зрения общего количества переданных байтов и времени. Алгоритм, предложенный Галлагером, Хамблетом и Спирой [56] для общих неориентированных графов, оказал сильное влияние на дизайн распределенных алгоритмов в целом и получил премию Дейкстры за влиятельную статью по распределенным вычислениям.

Многие другие алгоритмы были предложены для различных типов сетевых графов , таких как неориентированные кольца, однонаправленные кольца, полные графы, сетки, ориентированные графы Эйлера и другие. Общий метод, который отделяет проблему семейства графов от разработки алгоритма выбора координатора, был предложен Корах, Куттен и Моран. [57]

Для координации в распределенных системах используется концепция координаторов. Проблема выбора координатора состоит в том, чтобы выбрать процесс из группы процессов на разных процессорах в распределенной системе, который будет выступать в качестве центрального координатора. Существует несколько алгоритмов выбора центрального координатора. [58]

Свойства распределенных систем [ править ]

До сих пор основное внимание уделялось разработке распределенной системы, которая решает данную проблему. Дополнительная проблема исследования - изучение свойств данной распределенной системы. [59] [60]

Проблема остановки - аналогичный пример из области централизованных вычислений: нам дается компьютерная программа, и задача состоит в том, чтобы решить, останавливается она или работает навсегда. Проблема остановки в общем случае неразрешима , и, естественно, понять поведение компьютерной сети так же сложно, как понять поведение одного компьютера. [61]

Однако есть много разрешимых интересных частных случаев. В частности, можно рассуждать о поведении сети конечных автоматов. Один из примеров показывает, может ли данная сеть взаимодействующих (асинхронных и недетерминированных) конечных автоматов зайти в тупик. Эта проблема PSPACE-полный , [62] то есть, она разрешима, но маловероятно , что существует эффективный (централизованный, параллельный или распределенный) алгоритм , который решает проблему в случае больших сетей.

См. Также [ править ]

  • Распределенная сеть
  • Децентрализованные вычисления
  • Федерация (информационные технологии)
  • AppScale
  • BOINC
  • Мобильность кода
  • Распределенный алгоритм
  • Построение распределенного алгоритмического механизма
  • Распределенный кеш
  • Распределенная операционная система
  • Премия Эдсгера В. Дейкстры в области распределенных вычислений
  • Туманные вычисления
  • Складной @ дома
  • Грид-вычисления
  • Inferno
  • Вычисления в джунглях
  • Многоуровневая сеть массового обслуживания
  • Библиотечно-ориентированная архитектура (LOA)
  • Список конференций по распределенным вычислениям
  • Список проектов распределенных вычислений
  • Список важных публикаций по параллельным, параллельным и распределенным вычислениям
  • Проверка модели
  • Параллельная распределенная обработка
  • Модель параллельного программирования
  • План 9 от Bell Labs
  • Общая архитектура

Примечания [ править ]

  1. ^ a b Таненбаум, Эндрю С .; Стин, Маартен ван (2002). Распределенные системы: принципы и парадигмы . Река Аппер Сэдл, Нью-Джерси: Пирсон Прентис Холл. ISBN 0-13-088893-1.
  2. ^ Эндрюс (2000) . Долев (2000) . Гош (2007) , стр. 10.
  3. ^ Magnoni, Л. (2015). «Современный обмен сообщениями для распределенных систем (sic)» . Журнал физики: Серия конференций . 608 (1): 012038. DOI : 10,1088 / 1742-6596 / 608/1/012038 . ISSN 1742-6596 . 
  4. ^ Годфри (2002) .
  5. ^ а б Эндрюс (2000) , стр. 291–292. Долев (2000) , стр. 5.
  6. ↑ Линч (1996) , стр. 1.
  7. ^ a b Ghosh (2007) , стр. 10.
  8. ↑ Andrews (2000) , стр. 8–9, 291. Dolev (2000) , стр. 5. Ghosh (2007) , стр. 3. Линч (1996) , стр. xix, 1. Peleg (2000) , p. XV.
  9. ^ Эндрюс (2000) , стр. 291. Ghosh (2007) , стр. 3. Пелег (2000) , стр. 4.
  10. Перейти ↑ Ghosh (2007) , p. 3–4. Пелег (2000) , стр. 1.
  11. Перейти ↑ Ghosh (2007) , p. 4. Пелег (2000) , стр. 2.
  12. Перейти ↑ Ghosh (2007) , p. 4, 8. Lynch (1996) , стр. 2–3. Пелег (2000) , стр. 4.
  13. ↑ Линч (1996) , стр. 2. Пелег (2000) , стр. 1.
  14. Перейти ↑ Ghosh (2007) , p. 7. Линч (1996) , стр. xix, 2. Peleg (2000) , p. 4.
  15. Перейти ↑ Ghosh (2007) , p. 10. Кейдар (2008) .
  16. ↑ Линч (1996) , стр. XIX, 1-2. Пелег (2000) , стр. 1.
  17. ^ Пелегом (2000) стр. 1.
  18. ^ Papadimitriou (1994) , Глава 15. Keidar (2008) .
  19. ^ См. Ссылки во введении .
  20. ^ Bentaleb, A .; Ифань, л .; Xin, J .; и другие. (2016). «Параллельные и распределенные алгоритмы» (PDF) . Национальный университет Сингапура . Проверено 20 июля 2018 года .
  21. ^ Эндрюс (2000) , стр. 348.
  22. ^ Эндрюс (2000) , стр. 32.
  23. ^ Питер (2004) , История электронной почты .
  24. ^ Бэнкс, М. (2012). На пути к Интернету: Тайная история Интернета и его основателей . Апресс. С. 44–5. ISBN 9781430250746.
  25. ^ Тел, Г. (2000). Введение в распределенные алгоритмы . Издательство Кембриджского университета. С. 35–36. ISBN 9780521794831.
  26. ^ Ohlídal, M .; Jaroš, J .; Schwarz, J .; и другие. (2006). «Эволюционный дизайн графиков связи OAB и AAB для межсетевых соединений». In Rothlauf, F .; Branke, J .; Cagnoni, S. (ред.). Приложения эволюционных вычислений . Springer Science & Business Media. С. 267–78. ISBN 9783540332374.
  27. ^ «Системы реального времени и распределенные вычислительные системы» (PDF) . ISSN 2278-0661 . Проверено 9 января 2017 .   Цитировать журнал требует |journal=( помощь )
  28. Перейти ↑ Vigna P, Casey MJ. Эпоха криптовалюты: как биткойн и блокчейн бросают вызов мировому экономическому порядку, St. Martin's Press, 27 января 2015 г. ISBN 9781250065636 
  29. ^ Хьеу., Vu, Куанг (2010). Одноранговые вычисления: принципы и приложения . Lupu, Mihai., Ooi, Beng Chin, 1961–. Гейдельберг: Springer. п. 16. ISBN 9783642035135. OCLC  663093862 .
  30. ^ Lind Р, М Альм (2006), "База данных-ориентированной системы виртуальной химии", J , Chem Inf модель , 46 (3): 1034-9, DOI : 10.1021 / ci050360b , PMID 16711722 . 
  31. Перейти ↑ Chiu, G (1990). «Модель оптимального размещения базы данных в распределенных вычислительных системах». Ход работы. IEEE INFOCOM'90: Девятая ежегодная совместная конференция компьютерных и коммуникационных сообществ IEEE .
  32. ^ Elmasri & Navathe (2000) , раздел 24.1.2.
  33. ^ Эндрюс (2000) , стр. 10–11. Гош (2007) , стр. 4–6. Линч (1996) , стр. xix, 1. Peleg (2000) , p. XV. Эльмасри и Нават (2000) , Раздел 24.
  34. Перейти ↑ Haussmann, J. (2019). «Экономичная параллельная обработка нерегулярно структурированных задач в средах облачных вычислений». Журнал кластерных вычислений . 22 (3): 887–909. DOI : 10.1007 / s10586-018-2879-3 .
  35. ^ Тоомарян, NB; Barhen, J .; Гулати, С. (1992). «Нейронные сети для робототехнических приложений в реальном времени» . В Фиджани, А .; Бейчи, А. (ред.). Системы параллельных вычислений для робототехники: алгоритмы и архитектуры . World Scientific. п. 214. ISBN 9789814506175.
  36. Перейти ↑ Savage, JE (1998). Модели вычислений: изучение мощности вычислений . Эддисон Уэсли. п. 209. ISBN 9780201895391.
  37. ^ Кормена, Лейзерсон & Ривест (1990) , раздел 30.
  38. ^ Herlihy & Шавит (2008) , главы 2-6.
  39. ^ Линч (1996)
  40. ^ Кормена, Лейзерсон & Ривест (1990) , разделы 28 и 29.
  41. ^ Коул и Вишкин (1986) . Кормен, Лейзерсон и Ривест (1990) , раздел 30.5.
  42. ^ Эндрюс (2000) , стр. ix.
  43. Перейти ↑ Arora & Barak (2009) , раздел 6.7. Пападимитриу (1994) , раздел 15.3.
  44. ^ Papadimitriou (1994) , раздел 15.2.
  45. ↑ Линч (1996) , стр. 17–23.
  46. ^ Пелегом (2000) , разделы 2.3 и 7. Linial (1992) . Наор и Стокмейер (1995) .
  47. ^ Шнайдер, J .; Ваттенхофер Р. (2011). «Торговая битовая, информационная и временная сложность распределенных алгоритмов» . В Пелег, Д. (ред.). Распределенные вычисления . Springer Science & Business Media. С. 51–65. ISBN 9783642240997.
  48. Перейти ↑ Lynch (1996) , разделы 5–7. Гош (2007) , Глава 13.
  49. ↑ Линч (1996) , стр. 99–102. Гош (2007) , стр. 192–193.
  50. ^ Dolev (2000) . Ghosh (2007) , Глава 17.
  51. Перейти ↑ Lynch (1996) , Раздел 16. Пелег (2000) , Раздел 6.
  52. ↑ Lynch (1996) , раздел 18. Ghosh (2007) , разделы 6.2–6.3.
  53. ↑ Ghosh (2007) , раздел 6.4.
  54. ^ а б Haloi, S. (2015). Основы Apache ZooKeeper . Пакт Паблишинг Лтд., Стр. 100–101. ISBN 9781784398323.
  55. ^ LeLann, G. (1977). «Распределенные системы - к формальному подходу». Обработка информации . 77 : 155 · 160 - через Elsevier.
  56. ^ RG Галлагер , PA Humblet и PM Спир (январь 1983). «Распределенный алгоритм для минимально-весовых остовных деревьев» (PDF) . Транзакции ACM по языкам и системам программирования . 5 (1): 66–77. DOI : 10.1145 / 357195.357200 . CS1 maint: несколько имен: список авторов ( ссылка )
  57. ↑ Корах, Ефрем; Куттен, Шай ; Моран, Шломо (1990). «Модульный метод разработки эффективных распределенных алгоритмов поиска лидера» (PDF) . Транзакции ACM по языкам и системам программирования . 12 (1): 84–101. CiteSeerX 10.1.1.139.7342 . DOI : 10.1145 / 77606.77610 .  
  58. ^ Гамильтон, Ховард. «Распределенные алгоритмы» . Проверено 3 марта 2013 .
  59. ^ "Основные нерешенные проблемы в распределенных системах?" . cstheory.stackexchange.com . Проверено 16 марта 2018 .
  60. ^ «Как большие данные и распределенные системы решают традиционные проблемы масштабируемости» . theserverside.com . Проверено 16 марта 2018 .
  61. ^ Svozil, К. (2011). «Индетерминизм и случайность через физику» . В Гектор, З. (ред.). Случайность посредством вычислений: некоторые ответы, еще вопросы . World Scientific. С. 112–3. ISBN 9789814462631.
  62. ^ Papadimitriou (1994) , раздел 19,3.

Ссылки [ править ]

Книги
  • Эндрюс, Грегори Р. (2000), Основы многопоточного, параллельного и распределенного программирования , Аддисон-Уэсли , ISBN 978-0-201-35752-3.
  • Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность - современный подход , Кембридж , ISBN 978-0-521-42426-4.
  • Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990), Введение в алгоритмы (1-е изд.), MIT Press , ISBN 978-0-262-03141-7.
  • Долев, Шломи (2000), Самостабилизация , MIT Press , ISBN 978-0-262-04178-2.
  • Эльмасри, Рамез; Нават, Шамкант Б. (2000), Основы систем баз данных (3-е изд.), Аддисон – Уэсли , ISBN 978-0-201-54263-9.
  • Гош, Сукумар (2007), Распределенные системы - алгоритмический подход , Chapman & Hall / CRC, ISBN 978-1-58488-564-1.
  • Линч, Нэнси А. (1996), Распределенные алгоритмы , Морган Кауфманн , ISBN 978-1-55860-348-6.
  • Херлихи, Морис П .; Шавит, Нир Н. (2008), Искусство многопроцессорного программирования , Морган Кауфманн , ISBN 978-0-12-370591-4.
  • Пападимитриу, Христос Х. (1994), Вычислительная сложность , Аддисон – Уэсли , ISBN 978-0-201-53082-7.
  • Пелег, Дэвид (2000), Распределенные вычисления: подход с учетом местоположения , SIAM , ISBN 978-0-89871-464-7, заархивировано из оригинала 06.08.2009 , получено 16.07.2009.
Статьи
  • Коул, Ричард; Vishkin, Узи (1986), "Детерминированная монета бросание с приложениями к оптимальному списку параллельного рейтинга", информация и управление , 70 (1): 32-53, DOI : 10.1016 / S0019-9958 (86) 80023-7.
  • Keidar, Idit (2008), "Распределенные вычисления столбец 32 - год в обзоре" , ACM SIGACT News , 39 (4): 53-54, CiteSeerX  10.1.1.116.1285 , DOI : 10,1145 / 1466390,1466402.
  • Linial, Натан (1992), "Местность в распределенных алгоритмов графа", SIAM журнал по вычислениям , 21 (1): 193-201, CiteSeerX  10.1.1.471.6378 , DOI : 10,1137 / 0221015.
  • Наор, Мони ; Стокмейер, Ларри (1995), "Что можно вычислить локально?" (PDF) , SIAM журнал по вычислениям , 24 (6): 1259-1277, CiteSeerX  10.1.1.29.669 , DOI : 10,1137 / S0097539793254571.
Веб-сайты
  • Годфри, Билл (2002). «Букварь по распределенным вычислениям» .
  • Питер, Ян (2004). "История Интернета Яна Питера" . Проверено 4 августа 2009 .

Дальнейшее чтение [ править ]

Книги
  • Аттия, Хагит и Дженнифер Велч (2004), Распределенные вычисления: основы, моделирование и дополнительные темы , Wiley-Interscience ISBN  0-471-45324-2 .
  • Кристиан Качин; Рашид Геррауи; Луис Родригес (2011), Введение в надежное и безопасное распределенное программирование (2-е изд.), Springer, Bibcode : 2011itra.book ..... C , ISBN 978-3-642-15259-7
  • Кулурис, Джордж; и другие. (2011), Распределенные системы: концепции и дизайн (5-е издание) , Аддисон-Уэсли ISBN  0-132-14301-1 .
  • Фабер, Джим (1998), Java Distributed Computing , O'Reilly: Распределенные вычисления Java, Джим Фабер, 1998 г.
  • Гарг, Виджай К. (2002), Элементы распределенных вычислений , Wiley-IEEE Press ISBN  0-471-03600-5 .
  • Тел, Джерард (1994), Введение в распределенные алгоритмы , Cambridge University Press
  • Чанди, Мани ; и др., Разработка параллельных программ
Статьи
  • Кейдар, Идит; Раджсбаум, Серджио, ред. (2000–2009), «Колонка распределенных вычислений» , Новости ACM SIGACT.
  • Birrell, AD; Левин, Р .; Schroeder, MD; Нидхэм, Р.М. (апрель 1982 г.). «Grapevine: упражнение в распределенных вычислениях» (PDF) . Коммуникации ACM . 25 (4): 260–274. DOI : 10.1145 / 358468.358487 .
Материалы конференции
  • К. Родригес, М. Вильягра и Б. Баран, Асинхронные командные алгоритмы для логической выполнимости, Bionetics2007, стр. 66–69, 2007.

Внешние ссылки [ править ]

  • Распределенные вычисления в Curlie
  • Журналы распределенных вычислений в Curlie