4622
правки
Топологический подход в распределенных вычислениях: различия между версиями
Материал из WEGA
Топологический подход в распределенных вычислениях (посмотреть исходный код)
Версия от 13:29, 18 февраля 2025
, 18 февраль→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
''Вершина'' <math>\vec{v}</math> представляет собой точку в Евклидовом пространстве высокой размерности. Вершины <math>\vec{v_0}, ..., \vec{v_n}</math> ''аффинно независимы'', если <math>\vec{v_1} - \vec{v_0}, ..., \vec{v_n} - \vec{v_{n - 1}}</math> линейно независимы. ''n-мерный симплекс'' (или ''n-симплекс'') <math>S^n = (\vec{s_0}, ..., \vec{s_n})</math> – это выпуклая оболочка множества n + 1 аффинно независимых вершин. Например, 0-симплекс – это вершина, 1-симплекс – отрезок прямой, 2-симплекс – сплошной треугольник, а 3-симплекс – сплошной тетраэдр. Там, где это удобно, надстрочные знаки обозначают размерности симплексов. Считается, что симплекс <math>\vec{s_0}, ..., \vec{s_n}</math> охватывает <math>S^n</math>. Согласно условию, симплекс размерности d < 0 является пустым. | ''Вершина'' <math>\vec{v}</math> представляет собой точку в Евклидовом пространстве высокой размерности. Вершины <math>\vec{v_0}, ..., \vec{v_n}</math> ''аффинно независимы'', если <math>\vec{v_1} - \vec{v_0}, ..., \vec{v_n} - \vec{v_{n - 1}}</math> линейно независимы. ''n-мерный симплекс'' (или ''n-симплекс'') <math>S^n = (\vec{s_0}, ..., \vec{s_n})</math> – это выпуклая оболочка множества n + 1 аффинно независимых вершин. Например, 0-симплекс – это вершина, 1-симплекс – отрезок прямой, 2-симплекс – сплошной треугольник, а 3-симплекс – сплошной тетраэдр. Там, где это удобно, надстрочные знаки обозначают размерности симплексов. Считается, что симплекс <math>\vec{s_0}, ..., \vec{s_n}</math> охватывает <math>S^n</math>. Согласно условию, симплекс размерности d < 0 является пустым. | ||
''Симплициальный комплекс'' (или ''комплекс'') – это множество симплексов, замкнутых относительно операций вложения и пересечения. ''Размерность'' комплекса равна наибольшей размерности любого из его симплексов. <math>\mathcal{L}</math> является ''подкомплексом'' K, если каждый симплекс из L является симплексом из K. Отображение | ''Симплициальный комплекс'' (или ''комплекс'') – это множество симплексов, замкнутых относительно операций вложения и пересечения. ''Размерность'' комплекса равна наибольшей размерности любого из его симплексов. <math>\mathcal{L}</math> является ''подкомплексом'' <math>\mathcal{K}</math>, если каждый симплекс из <math>\mathcal{L}</math> является симплексом из <math>\mathcal{K}</math>. Отображение <math>\mu : \mathcal{K} \to \mathcal{L}</math>, переводящее вершины в вершины, является ''симплициальным'', если оно также порождает отображение симплексов в симплексы. | ||
'''Определение 1'''. Комплекс K является k-связным, если каждое непрерывное отображение k-сферы на K может быть расширено до непрерывного отображения (k + 1)-диска. Согласно условию, комплекс является (-l)-связным тогда и только тогда, когда он непуст, и каждый комплекс k-связен при k < - 1. | '''Определение 1'''. Комплекс <math>\mathcal{K}</math> является ''k-связным'', если каждое непрерывное отображение k-сферы на <math>\mathcal{K}</math> может быть расширено до непрерывного отображения (k + 1)-диска. Согласно условию, комплекс является ''(-l)-связным'' тогда и только тогда, когда он непуст, и каждый комплекс ''k-связен'' при k < - 1. | ||
| Строка 23: | Строка 23: | ||
'''Теорема 2. Если K и L – комплексы, такие, что K и L k-связны, | '''Теорема 2. Если <math>\mathcal{K}</math> и <math>\mathcal{L}</math> – комплексы, такие, что <math>\mathcal{K}</math> и <math>\mathcal{L}</math> k-связны, а <math>\mathcal{K} \cap \mathcal{L}</math> (k-1)-связен, то <math>\mathcal{K} \cup \mathcal{L}</math> k-связен.''' | ||
| Строка 29: | Строка 29: | ||
Множество n + 1 последовательных процессов взаимодействует между собой, посылая друг другу сообщения или выполняя операции над общими объектами. В любой момент процесс может претерпеть сбой: он останавливается и больше не делает никаких шагов. Существует ограничение f на количество процессов, которые могут окончиться сбоями. Разные модели различаются по своим предположениям о времени. На одном конце спектра находится синхронная модель, в которой вычисления производятся в виде последовательности раундов. В каждом раунде процесс отправляет сообщения другим процессам, получает сообщения, отправленные ему другими процессами в этом раунде, и меняет свое состояние. (Либо не обменивается сообщениями, а | Множество n + 1 последовательных ''процессов'' взаимодействует между собой, посылая друг другу сообщения или выполняя операции над общими объектами. В любой момент процесс может претерпеть ''сбой'': он останавливается и больше не делает никаких шагов. Существует ограничение f на количество процессов, которые могут окончиться сбоями. Разные модели различаются по своим предположениям о времени. На одном конце спектра находится ''синхронная модель'', в которой вычисления производятся в виде последовательности раундов. В каждом раунде процесс отправляет сообщения другим процессам, получает сообщения, отправленные ему другими процессами в этом раунде, и меняет свое состояние. (Либо не обменивается сообщениями, а выполняет операции над общими объектами). Все процессы выполняют шаги с одинаковой скоростью, все сообщения доставляются за одно и то же время. На противоположном конце располагается ''асинхронная модель'', в которой нет ограничений на время, которое может пройти между шагами процесса, и на время, которое может потребоваться для доставки сообщения. Между этими крайностями находится ''полусинхронная модель'', в которой время выполнения шагов процесса и время доставки сообщений могут меняться, но ограничены постоянными верхней и нижней границами. Доказательство нижней границы в любой из этих моделей требует глубокого понимания глобальных состояний, которые могут возникнуть в ходе выполнения протокола, и того, как эти глобальные состояния связаны между собой. | ||
Каждый процесс | |||
Каждый процесс начинает с ''входного значения'', взятого из множества V, а затем выполняет детерминированный ''протокол'', в котором он неоднократно получает одно или несколько сообщений, изменяет свое локальное состояние и отправляет одно или несколько сообщений. После конечного числа шагов каждый процесс выбирает ''значение решения'' и останавливается. | |||
