Аноним

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

Материал из WEGA

Переименование (посмотреть исходный код)

Версия от 11:43, 18 февраля 2025

1447 байт добавлено ,  18 февраля 2025
м
→‎Ключевые слова и синонимы
 
(не показано 5 промежуточных версий 2 участников)
Строка 1: Строка 1:
== Ключевые слова и синонимы ==
== Ключевые слова и синонимы ==
Переименование без ожидания
Переименование без ожидания (''Wait-free renaming'')


== Постановка задачи ==
== Постановка задачи ==
Строка 55: Строка 55:




Остов <math>\omega(S^n)</math> (в действительности, любой любой подразделенный n-симплекс) представляет собой (комбинаторное) ''многообразие с границей'': каждый (n – 1)-симплекс является гранью либо одного, либо двух n-симплексов. Если он является гранью двух n-симплексов, то симплекс является ''внутренним'', в противном случае – ''граничным''. Ориентация <math>S^n</math> порождает ориентацию каждого n-симплекса из <math>\omega(S^n)</math>, так что каждый внутренний (n – 1)-симплекс наследует противоположные ориентации. Суммирование этих ориентированных симплексов дает цепь, обозначаемую <math>\omega_*(S^n)</math>, такую, что <math>\partial \sigma_* (S^n) = \sum^n_{i = 0} (-1)^i \sigma_* (face_i(S^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>.




Строка 67: Строка 67:




Лемма 6 Для каждой собственной грани Sm~1 из Sn существует m-цепь a{Sm~l), такая, что
'''Лемма 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>.


Доказательство путем индукции по m. При m = 1, ids(S1) = fi; jg. 01 и /i*(cr*(S1)) – 1-цепи с общей границей hPi; 0) – Pj; 0i, поэтому //.".(o^S1)) – 01 – цикл, и a((P,,O" = ;.


Предположим, что утверждение верно для <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>.


Предположим, что утверждение верно для m; 1 > m < n – 1. Согласно теореме 5, каждый m-цикл является граничным (для m < n – 1), поэтому существует (m + 1)-цепь a(Sm) такая, что


Если взять знакопеременную сумму по граням <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>.
Теорема 7. Не существует протокола переименования без ожидания для (n + 1) процессов, использующих 2n выходных имен.
 
 
Перестановка членов дает <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)-циклом. □


Доказательство. Поскольку
является циклом, из теоремы 5 следует, что она гомологична k ■ @0n для некоторого целого числа k. Поскольку fi симметрична на границе CT(S"), получается знакопеременная сумма по (n – 1)-мерным граням Sn:
   
   
'''Теорема 7. Не существует протокола переименования без ожидания для (n + 1) процессов, использующих 2n выходных имен.'''


Если взять знакопеременную сумму по граням Sm+1, то a(facej(Sm)) сокращается, что дает
Доказательство. Поскольку <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>.
является (m + 1)-циклом.


 
Поскольку не существует значения k, для которого (1 + (n + 1)k) равно нулю, цикл <math>\mu_* (\partial \sigma_* (S^n))</math> не является границей, что противоречит предположению. □
Поскольку не существует значения k, для которого (1 + (n+1)k) равно нулю, цикл /x*(3a*(S")) не является границей, что противоречит предположению.
□


== Применение ==
== Применение ==
Строка 110: Строка 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
[[Категория: Совместное определение связанных терминов]]
Irina
4918

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/15459...15840