4824
правки
Переименование: различия между версиями
Материал из WEGA
м
→Ключевые слова и синонимы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 11 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Переименование без ожидания | Переименование без ожидания (''Wait-free renaming'') | ||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 18: | Строка 18: | ||
== Основные результаты == | == Основные результаты == | ||
'''Теорема 1. Пусть <math>S^n</math> – n-симплекс, а <math>S^m</math> – грань <math>S^n</math>. Обозначим за S комплекс, состоящий из всех граней <math>S^m</math>, за <math>\dot{S}</math> – комплекс, состоящий из всех собственных граней <math>S^n</math> (граничный комплекс <math>S</math>). Если <math>\sigma( \dot{S})</math> – подразделение S, а <math>\phi: \sigma (\dot{S}) \to \mathcal{F}(S)</math> – симплициальная карта, то существуют подразделение <math>\tau(S)</math> и симплициальная карта <math>\psi: \tau (\dot{S}) \to \mathcal{F}(S)</math>, такие, что <math>\tau (\dot{S}) = \sigma (\dot{S})</math>, и <math>\phi</math> и <math>\psi</math> сходятся (согласуются) на <math>\sigma (\dot{S})</math>.''' | '''Теорема 1. Пусть <math>S^n</math> – n-симплекс, а <math>S^m</math> – грань <math>S^n</math>. Обозначим за <math>S</math> комплекс, состоящий из всех граней <math>S^m</math>, за <math>\dot{S}</math> – комплекс, состоящий из всех собственных граней <math>S^n</math> (граничный комплекс <math>S</math>). Если <math>\sigma( \dot{S})</math> – подразделение <math>S</math>, а <math>\phi: \sigma (\dot{S}) \to \mathcal{F}(S)</math> – симплициальная карта, то существуют подразделение <math>\tau(S)</math> и симплициальная карта <math>\psi: \tau (\dot{S}) \to \mathcal{F}(S)</math>, такие, что <math>\tau (\dot{S}) = \sigma (\dot{S})</math>, и <math>\phi</math> и <math>\psi</math> сходятся (согласуются) на <math>\sigma (\dot{S})</math>.''' | ||
Неформально, любая симплициальная карта m-сферы в F может быть «заполнена» до симплициальной карты (m + 1)-диска. Остовом для F( | Неформально, любая симплициальная карта m-сферы в <math>\mathcal{F}</math> может быть «заполнена» до симплициальной карты (m + 1)-диска. ''Остовом'' для <math>\mathcal{F}(S^n)</math> является подразделение <math>\sigma</math> входного симплекса <math>S^n</math> вместе с симплициальной картой <math>\phi: \sigma(S^n) \to \mathcal{F}(S^n)</math>, такое, что для каждой грани <math>S^m</math> из <math>S^n</math> выполняется соотношение <math>\phi: \sigma(S^m) \to \mathcal{F}(S^m)</math>. Остовы строятся по одной размерности за раз. Для каждого <math> \vec s = \langle P_i, v_i \rangle \in S^n \; \phi</math> переносит <math> \vec s</math> для одиночного выполнения <math>P_i</math> с входным значением <math> \vec v_i</math>. Для каждого <math>S^1 = (\vec s_0, \vec s_1)</math> из теоремы 1 следует, что <math>\phi(\vec s_0)</math> и <math>\phi(\vec s_1)</math> могут быть соединены путем в <math>\mathcal{F}(S^1)</math>. Для каждого <math>S^1 = (\vec s_0, \vec s_1, \vec s_2)</math> построенные по индукции остовы определяют каждую грань граничного комплекса <math>\phi: \sigma(S^1_{ij}) \to \mathcal{F}(S^1)_{ij}</math> для <math>i, j \in \{ 0, 1, 2 \}</math>. Из теоремы 1 следует, что эту карту можно «заполнить», распространив подразделение с граничного комплекса на весь комплекс. | ||
Теорема 2. Если у задачи принятия решения имеется протокол в асинхронной памяти чтения/записи, то каждый входной симплекс имеет остов. | '''Теорема 2. Если у задачи принятия решения имеется протокол в асинхронной памяти чтения/записи, то каждый входной симплекс имеет остов.''' | ||
| Строка 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>. | ||
(1) | (1) <math>\mu : \sigma(S^n) \to \mathcal{B}^n</math>. | ||
Обозначим симплекс | Обозначим симплекс <math>\mathcal{B}^n</math>, все значения которого равны нулю, как <math>0^n</math>, а симплекс со всеми единицами – как <math>1^n</math>. | ||
Лемма 4. | '''Лемма 4'''. <math> \mu^{-1} (0^N) = \mu^{-1} (1^n) = 0</math>. | ||
Доказательство. В диапазоне 0...: ; 2 n - 1 не содержится n + 1 различных четных или n + 1 различных нечетных имен. □ | Доказательство. В диапазоне 0...: ; 2 n - 1 не содержится n + 1 различных четных или n + 1 различных нечетных имен. □ | ||
Назовем n-цилиндром бинарную n-сферу без | Назовем ''n-цилиндром'' <math>C^n</math> бинарную n-сферу без <math>0^n</math> и <math>1^n</math>. Неформально, остальная часть аргументации сводится к тому, чтобы показать, что граница остова «оборачивается» вокруг отверстия в <math>C^n</math> ненулевое число раз. | ||
Остов | Остов <math>\sigma(S^n)</math> (в действительности, любой любой подразделенный n-симплекс) представляет собой (комбинаторное) ''многообразие с границей'': каждый (n – 1)-симплекс является гранью либо одного, либо двух n-симплексов. Если он является гранью двух n-симплексов, то симплекс является ''внутренним'', в противном случае – ''граничным''. Ориентация <math>S^n</math> порождает ориентацию каждого n-симплекса из <math>\sigma(S^n)</math>, так что каждый внутренний (n – 1)-симплекс наследует противоположные ориентации. Суммирование этих ориентированных симплексов дает цепь, обозначаемую <math>\sigma_*(S^n)</math>, такую, что <math>\partial \sigma_* (S^n) = \sum^n_{i = 0} (-1)^i \sigma_* (face_i(S^n))</math>. | ||
| Строка 61: | Строка 61: | ||
Теорема 5. Пусть цепь | '''Теорема 5. Пусть цепь <math>0^n</math> – это симплекс <math>0^n</math>, ориентированный как <math>S^n</math>. (1) При 0 < m < n любые два m-цикла гомологичны, и (2) каждый n-цикл <math>C^n</math> гомологичен <math>k \cdot \partial O^n</math> для некоторого целого числа k. <math>C^n</math> является границей тогда и только тогда, когда k = 0.''' | ||
Пусть <math>S^m</math> – грань <math>S^n</math>, натянутая на одиночные выполнения <math>P_0, ..., P_m</math>. Обозначим за <math>0^m</math> некоторый m-симплекс из <math>C^n</math>, все значения которого равны нулю. Какой именно, будет понятно из контекста. | |||
'''Лемма 6.''' Для каждой собственной грани <math>S^{m - 1}</math> симплекса <math>S^n</math> существует m-цепь <math>\alpha(S^{m-1})</math>, такая, что <math>\mu_* (\sigma_* (S^m)) - 0^m - \sum^m_{i = 0} (-1)^i \alpha (face_i(S^m))</math> является циклом. | |||
Доказательство путем индукции по m. При m = 1 <math>ids(S^1) = \{ i, j \}</math>. <math>0^1</math> и <math>\mu_* (\sigma_* (S^1))</math> – 1-цепи с общей границей <math>\langle P_i, 0 \rangle – \langle P_j, 0 \rangle</math>, поэтому <math>\mu_* (\sigma_* (S^1)) - 0^1</math> является циклом, и <math>\alpha \langle \langle P_i, 0 \rangle \rangle </math>. | |||
является | Предположим, что утверждение верно для <math>m, 1 \ge m < n – 1</math>. Согласно теореме 5, каждый m-цикл является граничным (для m < n – 1), поэтому существует (m + 1)-цепь <math>\alpha(S^m)</math>, такая, что <math>\mu_* (\sigma_* (S^m)) - 0^m - \sum^m_{i = 0} (-1)^i \alpha (face_i(S^m)) = \partial \alpha(S^m)</math>. | ||
Если взять знакопеременную сумму по граням <math>S^{m+1}</math>, то <math>\alpha (face_i(S^m))</math> сокращается, что дает <math>\mu_* (\partial \sigma_* (S^{m + 1})) - \partial 0^{m + 1} = \sum^{m + 1}_{i = 0} (-1)^i \partial \alpha (face_i(S^{m + 1}))</math>. | |||
Перестановка членов дает <math>\partial \Bigg ( \mu_* (\sigma_* (S^{m + 1})) - 0^{m + 1} - \sum^{m + 1}_{i = 0} (-1)^i \alpha (face_i(S^{m + 1})) \Bigg ) = 0</math>, из чего следует, что <math>\mu_* (\sigma_* (S^{m + 1})) - 0^{m + 1} - \sum^{m + 1}_{i = 0} (-1)^i \alpha (face_i(S^{m + 1}))</math> является (m + 1)-циклом. □ | |||
'''Теорема 7. Не существует протокола переименования без ожидания для (n + 1) процессов, использующих 2n выходных имен.''' | |||
Доказательство. Поскольку <math>\mu_* (\sigma_* (S^{n - 1})) - 0^{n - 1} - \sum^{n}_{i = 0} (-1)^i \alpha (face_i(S^{n - 1}))</math> является циклом, из теоремы 5 следует, что она гомологична <math>k \cdot \partial 0^n</math> для некоторого целого числа k. Поскольку <math>\mu</math> симметрична на границе <math>\sigma(S^n)</math>, знакопеременная сумма по (n – 1)-мерным граням <math>S^n</math> дает: | |||
<math>\mu_* (\partial \sigma_* (S^n)) - \partial 0^n \sim (n + 1) k \cdot \partial 0^n</math> | |||
или | |||
<math>\mu_* (\partial \sigma_* (S^n)) \sim (1 + (n + 1) k) \cdot \partial 0^n</math>. | |||
Поскольку не существует значения k, для которого (1 + (n+1)k) равно нулю, цикл | Поскольку не существует значения k, для которого (1 + (n + 1)k) равно нулю, цикл <math>\mu_* (\partial \sigma_* (S^n))</math> не является границей, что противоречит предположению. □ | ||
□ | |||
== Применение == | == Применение == | ||
| Строка 115: | Строка 108: | ||
2. Herlihy, M.P., Shavit, N.: The asynchronous computability theorem for t-resilient tasks. In: Proceedings 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 111-120 | 2. Herlihy, M.P., Shavit, N.: The asynchronous computability theorem for t-resilient tasks. In: Proceedings 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 111-120 | ||
[[Категория: Совместное определение связанных терминов]] | |||
