4488
правок
Переименование: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
'''Определение 1'''. Протокол ''основан на сравнении', если единственные операции, которые процесс может выполнять над идентификаторами процессора – это проверка на равенство и порядок; то есть, если даны два P и Q, процесс может проверить P = Q, P < | '''Определение 1'''. Протокол ''основан на сравнении'', если единственные операции, которые процесс может выполнять над идентификаторами процессора – это проверка на равенство и порядок; то есть, если даны два P и Q, процесс может проверить выполнимость <math>P = Q, P \le Q</math> и <math>P \ge Q</math>, но не может исследовать структуру идентификаторов более подробно. | ||
Лемма 3. Если существует протокол переименования для K имен, не требующий ожидания, то существует и протокол, основанный на сравнении. | '''Лемма 3'''. Если существует протокол переименования для K имен, не требующий ожидания, то существует и протокол, основанный на сравнении. | ||
Доказательство. Аттия и др. [ ] предложили простой протокол переименования без ожидания, основанный на сравнении, который использует 2n+1 выходных имен. Применим этот алгоритм для присвоения каждому процессу промежуточного имени, а затем используем это промежуточное имя в качестве входных данных для протокола с K именами. □ | Доказательство. Аттия и др. [1] предложили простой протокол переименования без ожидания, основанный на сравнении, который использует 2n+1 выходных имен. Применим этот алгоритм для присвоения каждому процессу ''промежуточного'' имени, а затем используем это промежуточное имя в качестве входных данных для протокола с K именами. □ | ||
Алгоритмы, основанные на сравнении, симметричны относительно границы остова. Пусть | Алгоритмы, основанные на сравнении, ''симметричны'' относительно границы остова. Пусть <math>S^n</math> – входной симплекс, <math>\phi: \sigma(S^n) \to \mathcal{F}(S^n)</math> – остов, а <math>\mathcal{R}</math> – выходной комплекс для 2n имен. Компоновка карты остова <math>\phi</math> и карты решений <math>\delta</math> дает карту <math>\sigma(S^n) \to \mathcal{R}</math>. Эту карту можно упростить, заменив каждое выходное имя его четностью и заменив комплекс <math>\mathcal{R}</math> бинарной n-сферой <math>\mathcal{B}^n</math>. | ||