Исследовательская группа

Алгоритмы для конкурентных и распределенных систем

Наша научная группа разрабатывает и анализирует алгоритмы и структуры данных для многоядерных и распределенных систем.

Текущие проекты:

  • Конкурентные системы:

    • Конкурентные структуры данных, зависимые от распределения (с Dan Alistarh, IST Austria).
      Зачастую нагрузка на сервер неравномерна — некоторые ключи запрашиваются чаще других. В таких случаях используются самоподстраивающиеся структуры данных, такие как сплей-дерево. Вопрос в том, можем ли мы такие структуры данных сделать конкурентными?
    • Конкурентные структуры данных с запросами на отрезках (с Dan Alistarh, IST Austria).
      Наличие, вставка, удаление — типичные запросы в базах данных. Но иногда запросы бывают на отрезке, например подсчитать число элементов, которые лежат в заданных границах. Чтобы отвечать на запросы такого типа, мы представляем новый тип конкурентных структур данных.
    • Конкурентные структуры данных, дружелюбных к памяти.
      Как известно, если мы храним данные в последовательных участках памяти, то получаем дополнительное ускорение программы за счет использования кешей. Мы хотим перенести эту идею в многоядерный мир. Для этого наши структуры данных будут выделять память сразу под несколько элементов. Мы изучаем теоретическую и практическую сторону таких реализаций.
    • Сложность верификации конкурентных структур данных (с Danny Hendler, Университет Бен-Гуриона).
      Стандартные техники верификации конкурентных структур данных основаны или на экспериментах, или на формальных верификаторах. А знаем ли мы что-нибудь о теоретической сложности таких верификаций: P или NP?
    • ML-driven поисковые структуры данных (с Dan Alistarh, IST Austria).
      Текущий тренд в индексируемых структурах данных — использовать помощь машинного обучения, чтобы обучить индекс. Есть несколько способов сделать такие последовательные структуры данных. А можем ли мы сделать их конкурентными?
    • Parallel batched data structures.
      Мы берем базовые последовательные структуры данных, такие как бинарное дерево поиска, интерполяционное дерево поиска, обучаемый индекс, и пр., и пытаемся их строить или обрабатывать набор запросов параллельно.
  • Distributed systems:

    • Самоподстраивающиеся сети (с Stefan Schmid, University of Vienna).
      Мы изучаем теорию самоподстраивающихся сетей в различных моделях.
    • Консистентное шардирование с сохранением порядка.
      Как правило, база данных хранится на шардах, число которых может меняться со временем. Типичная задача заключается в том, как эффективно перераспределить ключи при добавлении/удалении шарда. Существует много известных решений, например консистентные или рандеву-хеширования. Однако, у всех таких способов есть большой минус — они не учитывают порядок ключей. Поэтому, чтобы сделать запрос на отрезке, приходится опрашивать все шарды вместо нескольких выделенных. Наше решение должно учитывать порядок и тем самым ускорять выполнение запросов.
    • Динамические и перестраивающиеся сервисы репликации.
      Основной задачей отказоустойчивого сервиса репликации (например, блокчейна) является доверительный доступ к общим данным в системе, в которой никто никому не доверяет. Участники системы могут иметь конфликтующие интересы и могут даже обманывать, но реализация должна гарантировать, что общие данные остаются консистентными и доступными. Эта задача оказывается очень сложной в известных моделях. Неудивительно, что текущие решения невероятно медленные и неэффективные. Наша цель заключается в нахождении эффективного решения в немного расслабленной, но все еще реалистичной модели.

Эти проекты выполняются группой следующих студентов: Александра Дроздова, Илья Кокорин, Евгений Федер, Даниил Болотом, Роман Смирнов, Павел Пономарев, Олег Фафурин, Ильдар Амиров (ИТМО), Наталья Мурашкина (ВШЭ), Алена Марценюк, Ильдар Зинатуллин, Виталий Краснов (МФТИ).

Контакт: Виталий Аксенов aksenov.vitaly@gmail.com.

Если у Вас есть идеи для сотрудничества, мы всегда готовы.

Состав