Переименование: различия между версиями

Рассмотрим систему, в которой n + 1 процессов P0 ... ; Pn взаимодействуют либо путем передачи сообщений, либо путем чтения из общей памяти и записи в нее. Процессы являются асинхронными: не существует верхних или нижних ограничений на их скорость, и до t из них могут уйти в необнаружимый отказ путем останова. В задаче переименования, которую предложили Аттия, Бар-Ной, Долев, Пелег и Райшук [1], каждый процесс получает уникальное входное имя из диапазона 0... ; N и выбирает уникальное выходное имя из строго меньшего диапазона 0... ; K. Чтобы исключить тривиальные решения, функция принятия решения процесса должна зависеть только от входных имен, а не от его заранее назначенного идентификатора (так что Pi не может просто выбрать выходное имя i). Аттия и коллеги показали, что задача не имеет решения при К = n, но имеет решение при К = N + t. В 1993 году Херлихи и Шавит [2] продемонстрировали, что задача не имеет решения при К < N + t.

Вершины, симплексы и комплексы моделируют задачи принятия решений. (См. сопутствующую статью «Топологический подход в распределенных вычислениях»). Состояние процесса в начале или конце задачи представляется в виде вершины v, помеченной идентификатором процесса и значением (входным или выходным): v = hP; vii. Две такие вершины совместимы, если: (1) у них разные идентификаторы процессов и (2) этим процессам можно присвоить эти значения вместе. Например, в задаче переименования входные значения должны быть разными, поэтому две входные вершины совместимы только в том случае, если они помечены разными идентификаторами процессов и разными входными значениями.