Доклад
- Когда и где
-
16 декабря 2019 г. 15:00, понедельник
Актовый зал ИММ УрО РАН
- Докладчики
-
-
Грищенко Виктор Сергеевич
-
Название
-
Линейные порядки в распределённых системах
-
Аннотация
-
Классика computer science выросла из мейнфреймов, поэтому часто подразумевает master-slave репликацию и линейный лог транзакций (ЛУМ). Классические модели для распределённых систем, в частности модель Лампорта, используют частичные порядки и нелинейные идентификаторы и этим усложняют структуру хранения и адресации (ЧУМ).
Опыты с системами на основе CRDT (Conflict-Free Replicated Data Types) показал, что хотя такие системы хорошо работают в распределённой и параллельной среде, связанные с нелинейностью издержки критичны и порой (часто) делают систему непрактичной. Причём, издержки тут измеряются как в байтах, так и в человекочасах.
Модель каузального леса (causal forest, CF) это разновидность CRDT, реализованная поверх модели Лампорта и являющаяся обобщением известной модели каузальных деревьев (causal trees, CT). Но в то время как CT унаследовала все сложности модели Лампорта, CF использует *локальные* линейные порядки для драматического упрощения как структуры хранения (измеримого в байтах и наносекундах) так и внешних интерфесов системы (измеримого в человекочасах).
Реализация CF модели также привела к ряду интересных результатов в области persistent data structures (будут описаны YOLO решётка, скиплог, хронофолд).
-
Презентация
-
-
Ссылка на видео
-
-
Видео
-
Вернуться к списку новостей