Распределенных вычислений - Distributed computing

Не путать с Децентрализованные вычисления.
«Распределенное приложение» перенаправляется сюда. Для ненадежных приложений см. Децентрализованное приложение.
«Распределенная обработка информации» перенаправляется сюда. Для компьютерной компании см. 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]

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

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

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

Приложения

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

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

Примеры

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

Теоретические основы

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

Модели

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

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

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

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

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

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

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

Пример

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

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

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

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

Меры сложности

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

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

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

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

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

Другие проблемы

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

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

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

Выборы

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

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

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

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

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

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

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

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

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

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

Смотрите также

Примечания

  1. ^ а б Таненбаум, Эндрю С .; Стин, Маартен ван (2002). Распределенные системы: принципы и парадигмы. Река Аппер Сэдл, Нью-Джерси: Пирсон Прентис Холл. ISBN  0-13-088893-1.
  2. ^ Эндрюс (2000). Долев (2000). Гош (2007), п. 10.
  3. ^ Магнони, Л. (2015). «Современный обмен сообщениями для распределенных систем (так в оригинале)». Journal of Physics: Серия конференций. 608 (1): 012038. Дои:10.1088/1742-6596/608/1/012038. ISSN  1742-6596.
  4. ^ Годфри (2002).
  5. ^ а б Эндрюс (2000), п. 291–292. Долев (2000), п. 5.
  6. ^ Линч (1996), п. 1.
  7. ^ а б Гош (2007), п. 10.
  8. ^ Эндрюс (2000) С. 8–9, 291. Долев (2000), п. 5. Гош (2007), п. 3. Линч (1996), п. XIX, 1. Пелег (2000), п. XV.
  9. ^ Эндрюс (2000), п. 291. Гош (2007), п. 3. Пелег (2000), п. 4.
  10. ^ Гош (2007), п. 3–4. Пелег (2000), п. 1.
  11. ^ Гош (2007), п. 4. Пелег (2000), п. 2.
  12. ^ Гош (2007), п. 4, 8. Линч (1996), п. 2–3. Пелег (2000), п. 4.
  13. ^ Линч (1996), п. 2. Пелег (2000), п. 1.
  14. ^ Гош (2007), п. 7. Линч (1996), п. XIX, 2. Пелег (2000), п. 4.
  15. ^ Гош (2007), п. 10. Кейдар (2008).
  16. ^ Линч (1996), п. XIX, 1-2. Пелег (2000), п. 1.
  17. ^ Пелег (2000), п. 1.
  18. ^ Пападимитриу (1994), Глава 15. Кейдар (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. Получено 2017-01-09. Цитировать журнал требует | журнал = (помощь)
  28. ^ Вигна П., Кейси М.Дж. Эпоха криптовалют: как биткойн и блокчейн бросают вызов мировому экономическому порядку St. Martin's Press 27 января 2015 г. ISBN  9781250065636
  29. ^ Хиеу., Ву, Куанг (2010). Одноранговые вычисления: принципы и приложения. Lupu, Mihai., Ooi, Beng Chin, 1961–. Гейдельберг: Springer. п. 16. ISBN  9783642035135. OCLC  663093862.
  30. ^ Линд П., Алм М. (2006), "Виртуальная химическая система, ориентированная на базу данных", Модель J Chem Inf, 46 (3): 1034–9, Дои:10.1021 / ci050360b, PMID  16711722.
  31. ^ Чиу, Г. (1990). «Модель оптимального размещения базы данных в распределенных вычислительных системах». Ход работы. IEEE INFOCOM'90: Девятая ежегодная совместная конференция компьютерных и коммуникационных обществ IEEE.
  32. ^ Эльмасри и Нават (2000), Раздел 24.1.2.
  33. ^ Эндрюс (2000), п. 10–11. Гош (2007), п. 4–6. Линч (1996), п. XIX, 1. Пелег (2000), п. XV. Эльмасри и Нават (2000), Раздел 24.
  34. ^ Осман, Дж. (2019).«Экономичная параллельная обработка нерегулярно структурированных задач в средах облачных вычислений». Журнал кластерных вычислений. 22 (3): 887–909. Дои:10.1007 / s10586-018-2879-3.
  35. ^ Toomarian, N.B .; Barhen, J .; Гулати, С. (1992). «Нейронные сети для робототехнических приложений в реальном времени». В Фиджани, А .; Бейчи, А. (ред.). Системы параллельных вычислений для робототехники: алгоритмы и архитектуры. World Scientific. п. 214. ISBN  9789814506175.
  36. ^ Сэвидж, Дж. Э. (1998). Модели вычислений: исследование мощности вычислений. Эддисон Уэсли. п. 209. ISBN  9780201895391.
  37. ^ Кормен, Лейзерсон и Ривест (1990), Раздел 30.
  38. ^ Херлихи и Шавит (2008), Главы 2-6.
  39. ^ Линч (1996)
  40. ^ Кормен, Лейзерсон и Ривест (1990), Разделы 28 и 29.
  41. ^ Коул и Вишкин (1986). Кормен, Лейзерсон и Ривест (1990), Раздел 30.5.
  42. ^ Эндрюс (2000), п. ix.
  43. ^ Арора и Барак (2009), Раздел 6.7. Пападимитриу (1994), Раздел 15.3.
  44. ^ Пападимитриу (1994), Раздел 15.2.
  45. ^ Линч (1996), п. 17–23.
  46. ^ Пелег (2000), Разделы 2.3 и 7. Линиал (1992). Наор и Стокмейер (1995).
  47. ^ Schneider, J .; Ваттенхофер Р. (2011). "Торговая битовая, информационная и временная сложность распределенных алгоритмов". В Пелег, Д. (ред.). Распределенных вычислений. Springer Science & Business Media. С. 51–65. ISBN  9783642240997.
  48. ^ Линч (1996), Разделы 5–7. Гош (2007), Глава 13.
  49. ^ Линч (1996), п. 99–102. Гош (2007), п. 192–193.
  50. ^ Долев (2000). Гош (2007), Глава 17.
  51. ^ Линч (1996), Раздел 16. Пелег (2000), Раздел 6.
  52. ^ Линч (1996), Раздел 18. Гош (2007), Разделы 6.2–6.3.
  53. ^ Гош (2007), Раздел 6.4.
  54. ^ а б Халой, С. (2015). Apache ZooKeeper: главное. Пакт Паблишинг Лтд., Стр. 100–101. ISBN  9781784398323.
  55. ^ ЛеЛанн, Г. (1977). «Распределенные системы - к формальному подходу». Обработка информации. 77: 155 · 160 - через Elsevier.
  56. ^ Р. Г. Галлагер, П. А. Хамблет и П. М. Спира (январь 1983 г.). «Распределенный алгоритм для минимально-весовых остовных деревьев» (PDF). Транзакции ACM по языкам и системам программирования. 5 (1): 66–77. Дои:10.1145/357195.357200.CS1 maint: несколько имен: список авторов (связь)
  57. ^ Корах, Ефрем; Куттен, Шай; Моран, Шломо (1990). «Модульный метод разработки эффективных распределенных алгоритмов поиска лидера» (PDF). Транзакции ACM по языкам и системам программирования. 12 (1): 84–101. CiteSeerX  10.1.1.139.7342. Дои:10.1145/77606.77610.
  58. ^ Гамильтон, Ховард. «Распределенные алгоритмы». Получено 2013-03-03.
  59. ^ "Основные нерешенные проблемы в распределенных системах?". cstheory.stackexchange.com. Получено 16 марта 2018.
  60. ^ «Как большие данные и распределенные системы решают традиционные проблемы масштабируемости». theserverside.com. Получено 16 марта 2018.
  61. ^ Свозил, К. (2011). «Индетерминизм и случайность через физику». В Гектор, З. (ред.). Случайность посредством вычислений: некоторые ответы, еще вопросы. World Scientific. С. 112–3. ISBN  9789814462631.
  62. ^ Пападимитриу (1994), Раздел 19.3.

Рекомендации

Книги
Статьи
Веб-сайты

дальнейшее чтение

Книги
  • Аттия, Хагит и Дженнифер Велч (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, О'Рейли: Распределенные вычисления Java, Джим Фабер, 1998 г.
  • Гарг, Виджай К. (2002), Элементы распределенных вычислений, Wiley-IEEE Press ISBN  0-471-03600-5.
  • Тел, Джерард (1994), Введение в распределенные алгоритмы, Издательство Кембриджского университета
  • Чанди, Мани; и другие., Разработка параллельных программ
Статьи
Материалы конференции

внешняя ссылка