4918
правок
Переименование: различия между версиями
Материал из WEGA
м
→Ключевые слова и синонимы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 7 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Переименование без ожидания | Переименование без ожидания (''Wait-free renaming'') | ||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 41: | Строка 41: | ||
(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 | ||
[[Категория: Совместное определение связанных терминов]] | |||
