Причинная непротиворечивость

Модель причинной непротиворечивости представляет собой ослабленный вариант последовательной непротиворечивости, при которой проводится разделение между событиями, потенциально обладающими причинно-следственной связью, и событиями, ею не обладающими. Если событие В вызвано предшествующим событием A или находится под его влиянием, то причинно-следственная связь требует, чтобы все окружающие наблюдали сначала событие A, а затем В.

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

На схеме представлена последователь­ность событий, возможная для хранилища с причинной непротиворечивостью, но запрещенная для хранилищ со строгой или последовательной непротиворечи­вые. Стоит отметить, что W2(x)b и W1(x)c — параллельные операции, и по­тому их очередность для различных процессов не важна.

Рассмотрим второй пример. На следующей схеме (a) а мы видим, что W2(x)b потенциально зависит от W1(x)a, поскольку b может быть результатом вычислений, в которые входит значение, прочитанное операцией R2(x)a. Две операции записи связаны причинно-следственной связью, а значит, все процессы должны наблюдать их в одинаковом порядке. Таким образом схема (а) некорректна.

С другой стороны, на схеме (б) операция чтения из процесса Р2 убрана, и теперь W1(x)a и W2(x)b стали параллельными операциями записи. Хранилище с причинной непротиворечивостью не требует, чтобы параллельные операции записи обладали глобальной упорядоченностью, и потому схема корректна.

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

Дата добавления: 2015-08-18