WikiSort.ru - Не сортированное

Вычислители

• Процессоры работают на произвольной скорости.
• Процессоры могут испытывать сбои.
• Процессоры со стабильным хранилищем могут повторно присоединиться к протоколу после сбоев (в соответствии с моделью сбоя аварийного восстановления).
• Процессоры не вступают в сговор, не лгут или иным образом пытаются подорвать протокол. (То есть византийских провалов не происходит. См. Византийский Паксос для решения, которое допускает сбои, возникающие в результате произвольного/вредоносного поведения процессов.)

Сеть

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

Число процессоров

Как правило, алгоритм консенсуса может добиться прогресса используя 2F+1 процессоров, несмотря на одновременный сбой любых F процессоров. Однако, используя перенастройку, можно использовать протокол, который выдерживает любое количество полных сбоев до тех пор, пока не произойдет сбой не более F процессоров одновременно.

Роли

Паксос описывает действия процессоров по их ролям в протоколе: клиент, приемник (акцептор), заявитель (предлагающий), ученик и лидер. В типичных реализациях один процессор может играть одновременно одну или несколько ролей. Это не влияет на правильность протокола — обычно объединяются роли для уменьшения задержки и/или количества сообщений в протоколе.

Клиент

Клиент выдает запрос распределенной системе и ожидает ответа. Например, запрос на запись в файл на распределенном файловом сервере.

Акцептор (избиратель)

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

Заявитель (предлагающий)

Заявитель защищает запрос клиента, пытаясь убедить акцепторов согласовать этот запрос, и действует в качестве координатора для продвижения протокола в случае возникновения конфликтов.

Ученик

Ученики выступают в качестве фактора репликации протокола. После согласования клиентского запроса акцепторами учащийся может предпринять действия (то есть выполнить запрос и отправить ответ клиенту). Для улучшения доступности обработки можно добавить дополнительных учеников.

Лидер

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

Кворум

Кворумом является большинство из всех членов кластера.

Q = N/2 + 1

К примеру, если в кластере имеется 6 участников, кворумом будет 4.

Кворумы выражают свойства безопасности алгоритма, обеспечивая сохранение информации о результатах по крайней мере в некоторых выживших процессорах.

Кворумы определяются как подмножества множества акцепторов таким образом, чтобы любые два подмножества (то есть любые два кворума) имели по крайней мере один общий элемент. Как правило, кворум является любым большинством участвующих акцепторов. Например, рассмотрим множество акцепторов {А,B,С,D}, кворум большинства для которого будут три любых акцептора: {А,B,С}, {А,С,D}, {А,В,D} или {B,С,D}. В более общем плане акцепторам и кворуму могут быть присвоены произвольные положительные веса, определяемым как любое подмножество акцепторов с суммарным весом, превышающим половину общего веса всех акцепторов.

Предложенное число и согласованное значение

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