Теоретические вопросы в распределенных вычислениях
Область распределенных вычислений оказалась крайне неудачной в разработке единой математической теории для описания распределенных алгоритмов. Существует несколько «моделей» и структур распределенных вычислений, которые просто не совместимы друг с другом. Абсолютный взрыв различных временных...
В 1980-х годах появились модели параллельных вычислений PRAM и BSP . Кажется, что расцвет обеих моделей был в конце 80-х и начале 90-х годов. Эти области все еще активны с точки зрения исследования параллельных алгоритмов? Существуют ли более новые, более сложные модели для параллельных вычислений?...
Вдохновленный этим вопросом , каковы основные проблемы и существующие решения, которые нуждаются в улучшении в (теоретической) области распределенных систем. Что-то вроде протоколов членства, согласованности...
Этот вопрос был перенесен из Cross Validated, потому что на него можно ответить на теоретической бирже информатики. Мигрировал 8 лет назад . У меня есть довольно уникальная проблема, которую я хочу решить, и я надеюсь, что кто-то здесь может дать мне некоторое представление о том, как лучше всего...
В распределенных вычислениях проблема консенсуса, по-видимому, является одной из центральных тем, которая привлекла интенсивные исследования. В частности, статья «Невозможность распределенного консенсуса с одним ошибочным процессом» была удостоена награды PODC за выдающуюся работу в 2001 году . Так...
Этот вопрос вдохновлен комментарием Юкки Суомела к другому вопросу . Каковы примеры бесконечно больших, но локально конечных вычислительных задач (и алгоритмов)? Другими словами, каковы примеры вычислений, которые останавливаются за конечное время, когда каждая машина Тьюринга считывает и...
В этой статье Kempe-Kleinberg-Tardos авторы предлагают жадные алгоритмы, основанные на субмодульных функциях, для определения наиболее влиятельных узлов в графе с приложениями к социальным сетям.kkk В основном алгоритм работает следующим образом: S=empty setS=empty setS = {\rm empty~set} выберите...
Я читаю статью «Быстрых Паксосов» Лесли Лампорта и застреваю с доказательствами правильности как классических Паксосов, так и Быстрых Паксосов. Для согласованности значение vvv выбранное координатором на этапе 2a2a2a в раунде iii должно удовлетворять CP(v,i):CP(v,i):CP(v,i): Для любого...
На прошлой неделе я снова читал текст Лесли Лампорта, опубликованный в 1982 году, на конференции, которую он дал о « Решенных проблемах, нерешенных проблемах и проблемах в параллелизме» . Бумага легко читается, но одна из вещей, которая заставила меня задуматься, это следующее утверждение: Можно ли...
Существует два основных типа сбоев процессора в моделях распределенных вычислений: (1) Сбои: процессор останавливается и больше не запускается. (2) Византийские сбои: процессоры ведут себя соперничающе, злонамеренно. Мой вопрос: Каковы некоторые другие типы отказов процессора, которые были изучены,...
Проблема сплетен в распределенных системах заключается в следующем. У нас есть граф с n вершинами. Каждая вершина v имеет сообщение m v, которое необходимо отправить всем узлам.GGGnnnvvvmvmvm_v Теперь мой вопрос в контексте специальной сетевой модели (мы предполагаем, что узел не имеет каких-либо...
В распределенных системах контроля версий (таких как Mercurial и Git ) существует необходимость эффективного сравнения направленных ациклических графов (DAG). Я - разработчик Mercurial, и нам было бы очень интересно услышать о теоретической работе, в которой обсуждается сложность времени и сети при...
Я магистр, специализирующийся на распределенных системах, но также интересующийся теоретической информатикой. Мне было интересно, есть ли формальное представление распределенной системы поверх машины Тьюринга? То есть возможно ли расширить (сделать вариант) концепцию машины Тьюринга, чтобы...
Пусть нерегулярный связный граф, степень которого ограничена. Предположим, что каждый узел содержит уникальный токен.G=(V,E)G=(V,E)G= (V, E) Я хочу равномерно перетасовать токены среди графа, используя только локальные перестановки (т.е. обмен токенами между двумя соседними узлами)? Известна ли...
Определения Пусть ϵ>0ϵ>0\epsilon > 0 и пусть ddd , rrr и ggg - натуральные числа (при g>2r+1g>2r+1g > 2r+1 ). Пусть G=(V,E)G=(V,E)G = (V,E) простой регулярный неориентированный конечный граф с обхватом не менее .гdddggg Пусть быть общий порядок на .V≤≤\leVVV Для каждого пусть состоит из...
Дэвид Родригес - dribeas написал в комментарии к StackOverflow, что «Не все коллекции могут быть реализованы без блокировок». Я не уверен, правда ли это, и я не могу найти доказательств в любом случае. Это утверждение не очень точное, но позвольте мне попытаться перефразировать его немного более...
Справочная информация: обработка транзакций была традиционной темой исследования в теории баз данных. В настоящее время распределенные транзакции популяризируются крупномасштабными распределенными системами хранения, которые обычно включают разделение данных (также называемое разделением ) и...
Упрощенная классическая транзакция базы данных может рассматриваться как: чтение М предметов выполняя некоторые расчеты на основе этих чтений написание некоторых N результатов, основанных на этих расчетах, которые могут включать элементы, которые изначально были прочитаны. При выполнении этих...
Какие документы по обработке ошибок в распределенных системах вы
Распределенные алгоритмы, которые устойчивы к сбоям, могут быть либо детерминированными, либо вероятностными. Возьмите для примера проблему консенсуса. Paxos является детерминированным в том смысле, что, учитывая допущение, оно всегда работает. В противоположность этому рандомизированный консенсус...