Grupo de pesquisa

Algoritmos para Sistemas Simultâneos e Distribuídos

O laboratório pesquisa algoritmos para sistemas simultâneos (multi-core) e distribuídos (em rede de grande escala). Nosso foco é investigar os princípios fundamentais por detrás desses sistemas e compreender as possibilidades de cálculos e os limites inferiores de complexidade.

Projetos de pesquisa atuais:

  • Sistemas simultâneos:

    • Estruturas de dados simultâneas com reconhecimento de distribuição (com Dan Alistarh, IST Áustria).
      A carga em uma estrutura de dados de chaves/valores é distorcida quando algumas chaves são solicitadas com mais frequência do que outras. Em uma configuração sequencial, normalmente usamos algumas estruturas de dados autoajustáveis com reconhecimento de distribuição, como árvores de splay. Podemos aplicar esse princípio em um sistema simultâneo? 
    • Estruturas de dados simultâneas de consultas de intervalo (com Dan Alistarh, IST Áustria).
      Consultas convencionais de banco de dados são inserção, exclusão e verificação de contenção. Mas também podemos pensar em consultas de intervalo, ou seja, contar o número de elementos cujas chaves estão dentro de um determinado intervalo. Como essas consultas de intervalo podem ser implementadas em uma configuração simultânea e quais são os custos inerentes dessas implementações? 
    • Estruturas de dados simultâneas compatíveis com memória.
      O armazenamento de dados compartilhados em intervalos de memória consequentes resulta em melhor desempenho devido à utilização otimizada do cache. Queremos estudar esse princípio de design em um nível fundamental. Para esse fim, introduzimos a noção de implementações concorrentes compatíveis com memória e otimizadas para memória e estamos estudando seus limites de desempenho e sua complexidade.
    • A complexidade da verificação de estruturas de dados simultâneas (com Danny Hendler, Ben-Gurion University).
      As técnicas convencionais usadas para verificar a exatidão das estruturas de dados concorrentes são experimentais ou formais. Porém, sabemos algo sobre a complexidade de tal verificação? Por exemplo, ela é NP-completa?
    • Estruturas de dados de pesquisa baseadas em ML (com Dan Alistarh, IST Áustria).
      A tendência atual em estruturas de dados baseadas em índice é aplicar machine learning. O objetivo deste projeto é tornar essas técnicas simultâneas.
    • Estruturas de dados em lote paralelas.
      No contexto de estruturas de dados básicas, como uma árvore de pesquisa binária, uma árvore de pesquisa de interpolação, índice aprendido e assim por diante, pesquisamos a construção paralela e a aplicação paralela de lotes de operações.
  • Sistemas distribuídos:

    • Redes autoajustáveis (com Stefan Schmid, Universidade de Viena).
      Tentamos desenvolver a teoria das redes autoajustáveis em diferentes modelos práticos.
    • Fragmentação consistente em relação à ordenação.
      Suponha que um banco de dados armazene uma coleção de chaves em fragmentos, e sua quantidade possa mudar com o tempo. A tarefa típica é redistribuir com eficiência as chaves entre os fragmentos em caso de adição/remoção. Existem muitas soluções conhecidas para conjuntos não ordenados de chaves, por exemplo, hash consistente e de rendezvous. No entanto, essas abordagens têm uma grande desvantagem: as chaves são armazenadas em fragmentos sem qualquer respeito à ordem das chaves e, se quisermos executar uma solicitação de intervalo (por exemplo, GetAllKeys(MinKey, MaxKey)), precisamos consultar cada fragmento. Nossa abordagem deve respeitar a ordem e ser a mais eficiente possível.
    • Serviços replicados dinâmicos, reconfiguráveis e responsáveis.
      O principal desafio dos serviços replicados tolerantes a falhas, e de blockchains em particular, é implementar um acesso confiável a dados compartilhados em sistemas com desconfiança mútua. Os participantes dos sistemas podem ter interesses conflitantes e até mesmo estar dispostos a trapacear, mas espera-se que a implementação garanta que eles compartilhem dados e troquem ativos de maneira consistente, disponível e justa. Como originalmente concebidas, as blockchains resolvem um problema muito difícil em um modelo muito difícil. Não é de surpreender que as soluções existentes sejam notoriamente lentas e ineficientes. O objetivo desse projeto é descobrir implementações novas e eficientes de compartilhamento de dados, considerando variantes mais fracas do problema, mesmo assim práticas, e variantes do modelo mais fortes, porém mais realistas.

Esses projetos estão sendo realizados atualmente pelos seguintes alunos: Alexandra Drozdova, Ilya Kokorin, Evgeny Feder, Daniil Bolotov, Roman Smirnov, Pavel Ponomarev, Oleg Fafurin, Ildar Amirov (ITMO), Natalia Murashkina (HSE), Alena Martsenuyk, Ildar Zinatullin, Vitalii Krasnov (MIPT).

Contato: Vitaly Aksenov, aksenov.vitaly@gmail.com.

Se tiver interesse em colaborar, não hesite em entrar em contato conosco.

Membros do Grupo

Vitaly Aksenov
Vitaly Aksenov
Chefe de Laboratório/Grupo de Pesquisa
Aleksandra Drozdova
Aleksandra Drozdova
Pesquisador
Petr Kuznetsov
Petr Kuznetsov
Chefe de Laboratório/Grupo de Pesquisa
Ilya Kokorin
Ilya Kokorin
Pesquisador