По мотивам  http://codeforces.net/blog/entry/2374 от  SkidanovAlex.

Изначальная формулировка задачи (та же самая, просто другими словами).

Имеется N потоков. На всех имеется общий объект синхронизации следующего вида: в синхронном режиме поток обращается к флагу, смотрит его значение ("да" или "нет"), и по желанию выставляет новое значение флага "да" или "нет".  

Необходимо выяснить, что все потоки закончили свою работу.

Все потоки помечены собственным номером. Планировщик задач действует строго случайным образом.

а) изначальная задача. Необходимо, чтобы хоть один поток с гарантией сказал, что все потоки закончили работу (при известном и неизвестном начальном положении флага). 

Вроде бы, легко. Далее положение флага будем считать известным.

б) задача 2. Необходимо, чтобы каждый поток с гарантией узнал, что все потоки закончили работу. То есть каждый поток должен сказать "хватит", причем все остальные потоки должны к этому моменту хотя бы раз обращаться к флагу, после чего перестать обращаться к флагу.

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

в) задача 3. Будем оценивать средние затраты времени на синхронизацию потоков в задаче 1, считая, что ни один поток не может отказаться от работы. Будем считать, что флаг имеет O(1) >= 2 состояний. Возможно ли добиться оптимальных затрат ? Кажется, что можно добиться

На это нет идей даже близко.