Полезность консенсусного номера

Question

Какая информация и полезность знают номер Consensus Number общего объекта, дают мне?

Answer 1

Вы, вероятно, не можете сделать гораздо лучше, чем цитата абстрактный из Оригинальная бумага Herlihy :

Бесплатная реализация параллельного объекта данных, которая гарантирует, что любой процесс может завершить любую работу в конечном количестве шагов, независимо от скоростей выполнения других процессов. Проблема построения бесспорной реализации одного объекта данных от другой лежит в основе всей недавней работы в одновременном алгоритмах, одновременных структурах данных и многопроцессорных архитектур. Во-первых, мы вводим простую и общую технику, основанную на сокращении до консенсусного протокола, для доказательства заявлений формы, “ нет никакой реализации X по Y. » Мы вынимаем иерархию объектов, таких, что ни один объект на одном уровне не имеет реализации без ожидания в условиях объектов на более низких уровнях. В частности, мы показываем, что атомные реестры чтения / записи, которые были в центре внимания большого внимания, находятся в нижней части иерархии: их нельзя использовать для построения бесплатных реализаций до упододвиненности до употребления многих простых и знакомых типов данных. Более того, классические примитивы синхронизации, такие как Test & Set и Fetch & Add, в то время как более мощные, чем чтение и запись, также являются вычислительно слабыми, как и стандартные примитивы передачи сообщений. Во-вторых, тем не менее, мы показываем, что существуют простые универсальные объекты, из которых можно построить бессповую реализацию любого последовательного объекта.