stringtranslate.com

Распределенные вычисления

Распределенные вычисления — это область компьютерной науки , изучающая распределенные системы , определяемые как компьютерные системы , взаимодействующие компоненты которых расположены на разных сетевых компьютерах . [1] [2]

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

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

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

Введение

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

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

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

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

Узоры

Вот общие архитектурные шаблоны , используемые для распределенных вычислений: [21]

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

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

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

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

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

История

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

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

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

Архитектура

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

То, совместно используют ли эти процессоры ресурсы или нет, определяет первое различие между тремя типами архитектуры:

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

Другим основным аспектом архитектуры распределенных вычислений является метод коммуникации и координации работы между параллельными процессами. С помощью различных протоколов передачи сообщений процессы могут напрямую взаимодействовать друг с другом, как правило, в отношении «главный/подчиненный». В качестве альтернативы, «база-центрированная» архитектура может позволить выполнять распределенные вычисления без какой-либо формы прямой межпроцессной коммуникации , используя общую базу данных . [37] База-центрированная архитектура, в частности, обеспечивает аналитику реляционной обработки в схематической архитектуре, допускающей ретрансляцию в реальном времени. Это позволяет выполнять функции распределенных вычислений как внутри, так и за пределами параметров сетевой базы данных. [38]

Приложения

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

Примеры

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

Реактивные распределенные системы

Согласно Reactive Manifesto, реактивные распределенные системы отзывчивы, устойчивы, эластичны и управляются сообщениями. Соответственно, реактивные системы более гибкие, слабосвязанные и масштабируемые. Чтобы сделать ваши системы реактивными, вам рекомендуется реализовать Reactive Principles. Reactive Principles — это набор принципов и шаблонов, которые помогают сделать ваше облачное приложение, а также граничные собственные приложения более реактивными. [42]

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

Модели

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

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

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

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

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

Параллельные алгоритмы в модели с общей памятью
Параллельные алгоритмы в модели передачи сообщений
Распределенные алгоритмы в модели передачи сообщений

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

Пример

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

Централизованные алгоритмы [49]
Параллельные алгоритмы
Распределенные алгоритмы

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

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

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

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

При анализе распределенных алгоритмов больше внимания обычно уделяется операциям связи, чем вычислительным шагам. Возможно, самая простая модель распределенных вычислений — это синхронная система, в которой все узлы работают в режиме lockstep. Эта модель обычно известна как модель LOCAL. Во время каждого раунда связи все узлы параллельно (1) получают последние сообщения от своих соседей, (2) выполняют произвольные локальные вычисления и (3) отправляют новые сообщения своим соседям. В таких системах центральной мерой сложности является количество синхронных раундов связи, необходимых для выполнения задачи. [54]

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

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

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

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

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

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

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

Обратите внимание, что в распределенных системах задержка должна измеряться с помощью «99-го процентиля», поскольку «медиана» и «среднее» могут вводить в заблуждение. [63]

Выборы

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

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

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

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

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

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

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

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

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

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

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

Примечания

  1. ^ ab Tanenbaum, Andrew S.; Steen, Maarten van (2002). Распределенные системы: принципы и парадигмы. Upper Saddle River, NJ: Pearson Prentice Hall. ISBN 0-13-088893-1. Архивировано из оригинала 2020-08-12 . Получено 2020-08-28 .
  2. ^ "Распределенные программы". Тексты по информатике . Лондон: Springer London. 2010. стр. 373–406. doi :10.1007/978-1-84882-745-5_11. ISBN 978-1-84882-744-8. ISSN  1868-0941. Системы состоят из ряда физически распределенных компонентов, которые работают независимо, используя свое личное хранилище, но также время от времени взаимодействуют посредством явной передачи сообщений. Такие системы называются распределенными системами.
  3. ^ Дюссо и Дюссо 2016, стр. 1–2.
  4. ^ Форд, Нил (3 марта 2020 г.). Основы архитектуры программного обеспечения: инженерный подход (1-е изд.). O'Reilly Media. С. 146–147. ISBN 978-1492043454.
  5. ^ Эволюционные модели от монолита к микросервисам для преобразования вашего монолита . O'Reilly Media. ISBN 9781492047810.
  6. ^ Создание бессерверных приложений на Knative . O'Reilly Media. ISBN 9781098142049.
  7. ^ "Распределенные программы". Тексты по информатике . Лондон: Springer London. 2010. стр. 373–406. doi :10.1007/978-1-84882-745-5_11. ISBN 978-1-84882-744-8. ISSN  1868-0941. Распределенные программы — это абстрактные описания распределенных систем. Распределенная программа состоит из набора процессов, которые работают параллельно и взаимодействуют посредством явной передачи сообщений. Каждый процесс может получить доступ к набору переменных, которые не пересекаются с переменными, которые могут быть изменены любым другим процессом.
  8. ^ Эндрюс (2000). Долев (2000). Гош (2007), стр. 10.
  9. ^ Magnoni, L. (2015). "Современный обмен сообщениями для распределенных систем (sic)". Journal of Physics: Conference Series . 608 (1): 012038. doi : 10.1088/1742-6596/608/1/012038 . ISSN  1742-6596.
  10. ^ Годфри (2002).
  11. ^ Эндрюс (2000), стр. 291–292. Долев (2000), стр. 5.
  12. Линч (1996), стр. 1.
  13. ^ ab Ghosh (2007), стр. 10.
  14. Эндрюс (2000), стр. 8–9, 291. Долев (2000), стр. 5. Гош (2007), стр. 3. Линч (1996), стр. xix, 1. Пелег (2000), стр. xv.
  15. ^ Эндрюс (2000), стр. 291. Гош (2007), стр. 3. Пелег (2000), стр. 4.
  16. ^ Гош (2007), стр. 3–4. Пелег (2000), стр. 1.
  17. ^ Гош (2007), стр. 4. Пелег (2000), стр. 2.
  18. ^ Ghosh (2007), стр. 4, 8. Lynch (1996), стр. 2–3. Peleg (2000), стр. 4.
  19. Линч (1996), стр. 2. Пелег (2000), стр. 1.
  20. ^ Гош (2007), стр. 7. Линч (1996), стр. xix, 2. Пелег (2000), стр. 4.
  21. ^ Основы архитектуры программного обеспечения: инженерный подход . O'Reilly Media. 2020. ISBN 978-1492043454.
  22. ^ Гош (2007), с. 10. Кейдар (2008).
  23. Линч (1996), стр. xix, 1–2. Пелег (2000), стр. 1.
  24. Пелег (2000), стр. 1.
  25. ^ Пападимитриу (1994), Глава 15. Кейдар (2008).
  26. ^ См. ссылки во Введении.
  27. ^ Bentaleb, A.; Yifan, L.; Xin, J.; et al. (2016). "Parallel and Distributed Algorithms" (PDF) . National University of Singapore. Архивировано (PDF) из оригинала 2017-03-26 . Получено 20 июля 2018 .
  28. ^ Эндрюс (2000), стр. 348.
  29. ^ Эндрюс (2000), стр. 32.
  30. Питер (2004), История электронной почты. Архивировано 15 апреля 2009 г. на Wayback Machine .
  31. ^ Бэнкс, М. (2012). На пути к Сети: Тайная история Интернета и его основателей. Apress. С. 44–5. ISBN 9781430250746. Архивировано из оригинала 2023-01-20 . Получено 2018-07-20 .
  32. ^ Тел, Г. (2000). Введение в распределенные алгоритмы. Cambridge University Press. С. 35–36. ISBN 9780521794831. Архивировано из оригинала 2023-01-20 . Получено 2018-07-20 .
  33. ^ Олидал, М.; Ярош, Дж.; Шварц, Дж.; и др. (2006). «Эволюционное проектирование расписаний связи OAB и AAB для сетей взаимосвязей». В Ротлауф, Ф.; Бранке, Дж.; Каньони, С. (ред.). Приложения эволюционных вычислений . Springer Science & Business Media. стр. 267–78. ISBN 9783540332374.
  34. ^ "Системы реального времени и распределенных вычислений" (PDF) . ISSN  2278-0661. Архивировано из оригинала (PDF) 2017-01-10 . Получено 2017-01-09 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  35. ^ Винья П., Кейси М.Дж. Эпоха криптовалют: как биткоин и блокчейн бросают вызов мировому экономическому порядку St. Martin's Press 27 января 2015 г. ISBN 9781250065636 
  36. ^ Куанг Хьеу Ву; Михай Лупу; Бенг Чин Уи (2010). Пиринговые вычисления: принципы и приложения . Гейдельберг: Springer. стр. 16. ISBN 9783642035135. OCLC  663093862.
  37. ^ Линд П., Альм М. (2006), «Виртуальная химическая система, ориентированная на базу данных», J Chem Inf Model , 46 (3): 1034–9, doi : 10.1021/ci050360b, PMID  16711722.
  38. ^ Чиу, Г. (1990). «Модель оптимального размещения баз данных в распределенных вычислительных системах». Труды. IEEE INFOCOM'90: Девятая ежегодная совместная конференция обществ IEEE Computer and Communications .
  39. ^ Эльмасри и Навате (2000), раздел 24.1.2.
  40. ^ Эндрюс (2000), с. 10–11. Гош (2007), с. 4–6. Линч (1996), с. xix, 1. Пелег (2000), с. хв. Эльмасри и Навате (2000), раздел 24.
  41. ^ Хаусманн, Дж. (2019). «Экономически эффективная параллельная обработка нерегулярно структурированных задач в облачных вычислительных средах». Журнал кластерных вычислений . 22 (3): 887–909. doi :10.1007/s10586-018-2879-3. S2CID  54447518.
  42. ^ Реактивная разработка приложений . Мэннинг. 2018. ISBN 9781638355816.
  43. ^ Toomarian, NB; Barhen, J.; Gulati, S. (1992). "Нейронные сети для робототехнических приложений в реальном времени". В Fijany, A.; Bejczy, A. (ред.). Параллельные вычислительные системы для робототехники: алгоритмы и архитектуры . World Scientific. стр. 214. ISBN 9789814506175. Архивировано из оригинала 2020-08-01 . Получено 2018-07-20 .
  44. ^ Savage, JE (1998). Модели вычислений: исследование мощности вычислений . Addison Wesley. стр. 209. ISBN 9780201895391.
  45. ^ Кормен, Лейзерсон и Ривест (1990), Раздел 30.
  46. ^ Херлихи и Шавит (2008), главы 2–6.
  47. ^ Линч (1996)
  48. ^ Кормен, Лейзерсон и Ривест (1990), разделы 28 и 29.
  49. ^ abc TULSIRAMJI GAIKWAD-PATIL Колледж инженерии и технологий, Нагпур Кафедра информационных технологий Введение в распределенные системы[1]
  50. ^ Коул и Вишкин (1986). Кормен, Лейзерсон и Ривест (1990), раздел 30.5.
  51. ^ Эндрюс (2000), стр. ix.
  52. ^ Арора и Барак (2009), раздел 6.7. Пападимитриу (1994), раздел 15.3.
  53. ^ Пападимитриу (1994), раздел 15.2.
  54. Линч (1996), стр. 17–23.
  55. ^ Пелег (2000), разделы 2.3 и 7. Линиал (1992). Наор и Стокмейер (1995).
  56. ^ Шнайдер, Дж.; Ваттенхофер, Р. (2011). «Торговый бит, сообщение и временная сложность распределенных алгоритмов». В Пелег, Д. (ред.). Распределенные вычисления . Springer Science & Business Media. стр. 51–65. ISBN 9783642240997. Архивировано из оригинала 2020-08-01 . Получено 2018-07-20 .
  57. ^ Линч (1996), Разделы 5–7. Гош (2007), Глава 13.
  58. ^ Линч (1996), стр. 99–102. Гош (2007), стр. 192–193.
  59. ^ Долев (2000). Гош (2007), Глава 17.
  60. Линч (1996), Раздел 16. Фалек (2000), Раздел 6.
  61. Линч (1996), Раздел 18. Гош (2007), Разделы 6.2–6.3.
  62. ^ Гош (2007), Раздел 6.4.
  63. ^ Основы приложений с интенсивным использованием данных. Анализ больших объемов данных под капотом . 2021. ISBN 9781119713012.
  64. ^ аб Халой, С. (2015). Основы Apache ZooKeeper. Packt Publishing Ltd., стр. 100–101. ISBN 9781784398323. Архивировано из оригинала 2023-01-20 . Получено 2018-07-20 .
  65. ^ ЛеЛанн, Г. (1977). «Распределенные системы — к формальному подходу». Обработка информации . 77 : 155·160 – через Elsevier.
  66. ^ RG Gallager , PA Humblet и PM Spira (январь 1983 г.). «Распределенный алгоритм для остовных деревьев минимального веса» (PDF) . ACM Transactions on Programming Languages ​​and Systems . 5 (1): 66–77. doi :10.1145/357195.357200. S2CID  2758285. Архивировано (PDF) из оригинала 26.09.2017.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  67. ^ Корах, Эфраим; Куттен, Шей ; Моран, Шломо (1990). «Модульная методика проектирования эффективных распределенных алгоритмов поиска лидера» (PDF) . Труды ACM по языкам программирования и системам . 12 (1): 84–101. CiteSeerX 10.1.1.139.7342 . doi :10.1145/77606.77610. S2CID  9175968. Архивировано (PDF) из оригинала 2007-04-18. 
  68. ^ Гамильтон, Ховард. "Распределенные алгоритмы". Архивировано из оригинала 2012-11-24 . Получено 2013-03-03 .
  69. ^ "Основные нерешенные проблемы в распределенных системах?". cstheory.stackexchange.com . Архивировано из оригинала 20 января 2023 г. . Получено 16 марта 2018 г. .
  70. ^ "Как большие данные и распределенные системы решают традиционные проблемы масштабируемости". theserverside.com . Архивировано из оригинала 17 марта 2018 г. . Получено 16 марта 2018 г. .
  71. ^ Svozil, K. (2011). «Индетерминизм и случайность через физику». В Hector, Z. (ред.). Случайность через вычисления: некоторые ответы, больше вопросов . World Scientific. стр. 112–3. ISBN 9789814462631. Архивировано из оригинала 2020-08-01 . Получено 2018-07-20 .
  72. ^ Пападимитриу (1994), раздел 19.3.

Ссылки

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

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

Книги
Статьи
Материалы конференции

Внешние ссылки