## Универсальная конструкция

### Введение

Хотим показать, что если `Consensus-Number(X)⩾n`, то любой объект можно реализовать с гарантией wait-free для `n` потоков с помощью объекта `X` и RW-регистров, причем объект будет линеаризуемым.

Например, `Consensus-Number(CAS)=+∞`, значит, любой объект можно сделать с гарантией wait-free.

Объект должен работать детерминированно.

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

Этого можно достичь, сделав лог операций (в виде очереди). Каждый поток поддерживает свою копию лога, вызов выполяет следующим образом:
1. добавляет свой вызов в очередь;
2. затем смотрит с некоторого «последнего» момента, который он запомнил, и проматывает все операции, пока не доходит до своей (этот момент становится «последним» для локальной копии лога в нашем потоке).

Можно делать и умнее (то есть не выполнять все операции из очереди), но это не влияет на соблюдение гарантии wait-free.

Заметим, что операции будут линеаризоваться в тот момент, когда они добавляются в очередь: именно в таком порядке они и будут исполняться.

Как добавлять в очередь? Если добавления не конкурируют, то все просто. А если конкурируют? Им нужно прийти к консенсусу: какую операцию добавить в очередь первой.

### Универсальная lock-free конструкция

В каждом узле очереди будем хранить:
* Invocation — вызов, который нужно выполнить;
* Сonsensus — объект, решающий задачу консенсуса для `n` потоков;
* Seq. number — номер узла в очереди;
* Next — указатель на следующий узел в очереди;

Итак, с помощью консенсуса умеем добавлять в конец... Но мы не знаем, где конец находится. В lock-free очереди мы двигали указатель `Tail` с помощью `CAS`, но здесь такая операция отсутствует. Нужно действовать хитрее.

`Tail` теперь будет массивом из `n` ячеек, каждая из которых содержит указатель на тот узел в очереди, которые является хвостом для соответствующего данной ячейке потока. Чтобы считать хвост, надо пройти по всем этим указателям и выбрать тот узел, у которого наибольший `Seq. number`. Разумеется, наш хвост не обязательно будет актуальным, поэтому операцию потребуется повторить в неуспешном случае.

```
my = ... // create node with method invocation
while (my->seqnum == 0) {
  before = ReadTail()
  after = before->consensus.Decide(my)
  before->next = after
  after->seqnum = before->seqnum + 1
  tail[t] = after
}
```

Как это работает? Мы создали какой-то узел, изначально его номер нулевой. Читаем какую-то версию хвоста очереди. Далее выбираем, какой узел будет следующий, с помощью консенсуса: если хвост был актуален, то вернется наш узел, и мы его добавим. Но нас могли опередить, тогда мы добавим узел повторно (ничего не поломается), обновим свой хвост и повторим операцию (так как `seqnum` по-прежнему будет нулевым).

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

В данной реализации мы можем проигрывать на выборах сколь угодно много раз. Поэтому гарантия wait-free не соблюдается. Получена универсальная lock-free конструкция.

### Универсальная wait-free конструкция

Хотим избежать голодания. Если поток объявил о том, что хочет добавить свой узел в очередь, засыпает, то узел все равно должен добавляться. Идея: просим о помощи.

Для этого заводим массив `announce[]` из `n` элементов. В начале добавления положим свой узел в этот массив в свою ячейку. При добавлении сначала подумаем, кому мы можем помочь. Выберем поток, кому помочь, и если его узел еще не добавлен, добавим его. Если же его узел добавлен, то будет добавлять свой узел. Важно: в один и тот же момент (момент определяется номером, который имеет актуальный хвост лога) все потоки пытаются помочь одному и тому же.

```
my = ... // create node with method invocation
announce[t] = my
tail[t] = ReadTail()
while (my->seqnum == 0) {
  before = tail[t]
  turn = (before->seqnum + 1) % num_threads
  if (announce[turn]->seqnum == 0)
    candidate = announce[turn]
  else
    candidate = my
  after = before->consensus.Decide(candidate)
  before->next = after
  after->seqnum = before->seqnum + 1
  tail[t] = after
}
tail[t] = my
```

`turn` — номер потока, которому в случае необходимости помогаем. Видно, что мы идем по кругу, то есть для помощи используется механизм round robin.

Осталось доказать, что такое добавление соблюдает гарантию wait-free. Действительно, пусть мы анонсировали добавление вершины. Ясно, что среди ближайших `n` вершин найдется такой номер узла, что, оказавшись в некоторый момент хвостом `before`, другой поток нам поможет. Мы тем не менее на каждой итерации цикла сдвигаем `tail` хотя бы на 1. То есть мы выполним не более `n` операций.

На самом деле — за `n+1`. Например, пусть `n=3`, `t=1`, `before->seqnum=9`. Тогда понятно, что следующий узел будет 10-й, то есть 1 по модулю `n`, и нам помогут. Но при этом возможно, что _до нашего анонса_ пришел другой поток, который выиграл на выборах. Тогда, конечно, добавят его узел, а для добавления нашего еще `n` итераций придется подождать. Через круг мы точно выиграем, потому что наш анонс уже будет в массиве, и нас никто не опередит. Таким образом, наш узел окажется среди ближайших `n+1` узлов.

Итого: пусть мы спали. Если мы проснулись далеко от хвоста, то наш узел уже добавлен, и цикл не продолжится. А проснуться недалеко от хвоста можно не более `O(n)` раз, так как хвост движется вперед каждый раз, а в ближайшие `O(n)` узлов наш узел добавят.  Следовательно, каждое добавлеие в очереди выполняется за конечное число шагов, то есть соблюдается гарантия wait-free.

#### Очистка памяти

Каждый поток имеет свой пул узлов, и он их переиспользует. Это нужно, так как мы хотим соблюсти гарантию wait-free. Если не переиспользовать, то будем зависеть от аллокатора (который, скорее всего, не wait-free). Каждый поток удаляет и переиспользует только «свои» узлы.

Заметим, что если мы спим, а хвост продвинулся тем временем сильно вперед, то мы уже не будем смотреть на далекие узлы. Значит, если на какой-то узел точно никто не смотрит, его можно удалять. Спящий поток может обратиться то к `O(n)` ближайшим узлам. Их трогать нельзя. Таким образом, если среди первых `O(n)` потомков узла нет такого, на котором сейчас спит другой поток, то данный узел можно удалить.

Итого: пусть мы спали. Если проснулись далеко от хвоста, то наш узел вставили. Мы не посмотрим на далекие узлы. Если проснулись близко к хвосту, то гарантии, что наш узел вставили, еще нет. Тогда удалять нельзя.

Каждый поток тем самым «блокирует» удаление `O(n)` узлов. Значит, всего потребуется `O(n²)` узлов.