Author Archives: Денис Чащин

Взаимное исключение в распределенной системе. Алгоритм обедающих философов, алгоритм на основе токена, алгоритм на основе кворума

TweetЗадача об обедующих философах Здесь считается, что для того, чтобы есть, философу необходимо иметь все вилки. Процесс ест, когда у него есть все вилки и все вилки чистые После еды вилки помечаются грязными Чистые вилки не отдавать Полученные вилки — чистые Грязные вилки можно мыть, когда есть все остальные Token ring Связываем все процессы в […]

Взаимное исключение в распределенной системе. Централизованный алгоритм, алгоритм Лампорта, алгоритм Рикарта и Агравалы

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

Логические часы Лампорта и векторные часы. Их свойства

TweetОписание Предположим, что у нас есть много компьютеров (вычислительных узлов), которые обмениваются сообщения.  Нужно научиться как-то среди этих сообщений устанавливать порядок. Для этого вводится функция времени, которая позволит для некоторых сообщений сказать какое из них было раньше. Определения Частичный порядок, это когда: Посылка предшествует получению этого-же сообщения, События в одном потоке упорядочены. Логические часы — […]

Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью

TweetРаспределенные вычислительные системы — это физические компьютеры и программные системы, реализующие каким-нибудь способом параллельную обработку данных на многих вычислительных узлах. Отличие от систем с разделяемой памятью: В каждом узле свое время (невозможно задать глобальное время). Связь между узлами происходит с задержкой. Сообщения могут теряться по пути. Любой узел может быть выключен или отказать. Виды масштабируемости: […]

Византийские генералы. Доказательство невозможности

TweetОписание Приведенный в статье «Алгоритм византийских генералов» алгоритм решения задачи о византийских генералах работает только когда , где — число предателей. Сейчас покажем, что является граничным значением. (далее — множество передач сообщений генералов, — множество значений, которые получили генералы). Не получится достигнуть единогласия, если ни только с раундами, но и с бесконечным количеством раундов обмена […]