Есть вектор, элементы которого могут иметь значение 0 или 1. Алгоритм бежит по вектору от начала до конца, для каждого не нулевого элемента i вычисляет f(i) = {j_k}, среди которых не будет i, и записывает в каждый j_k элемент значение 1, не разбираясь, что было в этом элементе до того. Функция f такова, что f(f(i)_k) = {n_k}, среди которых попадётся i.
Если параллелить этот алгоритм тупо, так что каждый поток бежит по своей части вектора и записывает во все остальные части, то надо много блокировок на чтение-запись для элементов вектора. Однако, если вообще не делать блокировок, то результат гарантировано будет правильный ввиду свойств функции f, и логики алгоритма. Тем не менее, без блокировок формально будут race-ы.
Почему-то мне думается, что можно сделать алгоритм без блокировок, без гонок и без перерасхода памяти...
P.S. Алгоритм имеет отношение к симметризации шаблона разреженной матрицы.
