Grupo de investigación

Algoritmos para sistemas simultáneos y distribuidos

El laboratorio investiga algoritmos para sistemas simultáneos (multinúcleo) y distribuidos (en red a gran escala). Nos centramos en investigar los principios fundamentales de estos sistemas y en entender las posibilidades de cálculos y los límites inferiores de complejidad.

Proyectos de investigación actuales:

  • Sistemas simultáneos:

    • Estructuras de datos simultáneas con reconocimiento de distribución (con Dan Alistarh, IST Austria).
      La carga en una estructura de datos clave-valor se sesga cuando se solicitan algunas claves con más frecuencia que otras. En una configuración secuencial, normalmente usamos algunas estructuras de datos autoajustadas con reconocimiento de distribución, como los árboles de reproducción. ¿Podemos aplicar este principio en un sistema simultáneo? 
    • Estructuras de datos simultáneas de consulta de intervalo (con Dan Alistarh, IST Austria).
      Las consultas en bases de datos convencionales son la inserción, la eliminación y la comprobación de contención. Sin embargo, también podemos pensar en consultas de intervalo, es decir, contar el número de elementos cuyas claves se encuentran dentro de un intervalo determinado. ¿Cómo se pueden implementar esas consultas de intervalo en una configuración simultánea y cuáles son los costes inherentes de estas implementaciones? 
    • Estructuras de datos simultáneas compatibles con la memoria.
      Almacenar datos compartidos en intervalos de memoria consiguientes supone un rendimiento mejorado debido a la utilización optimizada del almacenamiento en caché. Queremos estudiar este principio de diseño a nivel fundamental. Para ello, hemos introducido la noción de implementaciones simultáneas compatibles con la memoria y óptimas para la memoria, y estamos estudiando sus límites de rendimiento y complejidad.
    • Complejidad de la verificación de estructuras de datos simultáneas (con Danny Hendler, Universidad Ben-Gurión).
      Las técnicas convencionales utilizadas para verificar la corrección de las estructuras de datos simultáneas son experimentales o formales. Sin embargo, ¿sabemos algo sobre la complejidad de dicha verificación? Por ejemplo, ¿es NP-completa?
    • Estructuras de datos de búsqueda basadas en ML (con Dan Alistarh, IST Austria).
      La tendencia actual en las estructuras de datos basadas en índices es aplicar el machine learning. El objetivo de este proyecto es hacer que estas técnicas sean simultáneas.
    • Estructuras de datos por lotes paralelas.
      En el contexto de las estructuras de datos básicas, como los árboles de búsqueda binaria, los árboles de búsqueda de interpolación o los índices aprendido, entre otros, investigamos la construcción paralela y la aplicación paralela de lotes de operaciones.
  • Sistemas distribuidos:

    • Redes autoajustadas (con Stefan Schmid, Universidad de Viena).
      Tratamos de desarrollar la teoría de las redes autoajustadas en diferentes modelos prácticos.
    • Partición consistente respecto al orden.
      Supongamos que una base de datos almacena una serie de claves en particiones y su cantidad puede cambiar con el tiempo. La tarea típica es redistribuir de forma eficaz las claves entre particiones en el caso de su adición/eliminación. Hay muchas soluciones conocidas para conjuntos desordenados de claves, por ejemplo, hashing consistente y de encuentro. Sin embargo, estos enfoques tienen un inconveniente importante: las claves se almacenan en particiones sin tener en cuenta el orden de estas y, si queremos ejecutar una solicitud de intervalo (por ejemplo, GetAllKeys(MinKey, MaxKey)), tenemos que consultar cada partición. Nuestro enfoque tiene que respetar el orden y ser lo más eficiente posible.
    • Servicios replicados dinámicos, reconfigurables y responsables.
      El principal reto de los servicios replicados tolerantes a fallos y de las cadenas de bloques en particular es implementar un acceso de confianza a los datos compartidos en sistemas con desconfianza mutua. Los participantes del sistema pueden tener conflictos de intereses e incluso podrían estar dispuestos a hacer trampas, pero se espera que la implementación garantice que compartan datos e intercambien activos de una manera consistente, disponible y justa. Tal como fueron concebidas, las cadenas de bloques resuelven un problema muy difícil en un modelo muy duro. No es de extrañar que las soluciones existentes sean claramente lentas e ineficientes. El objetivo de este proyecto es descubrir implementaciones novedosas y eficientes de intercambio de datos teniendo en cuenta variantes más débiles, pero prácticas, del problema y variantes más fuertes, pero realistas, del modelo.

Estos proyectos están siendo realizados actualmente por los siguientes estudiantes: 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).

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

Si está interesado en colaborar, no dude en ponerse en contacto con nosotros.

Miembros del grupo

Vitaly Aksenov
Vitaly Aksenov
Responsable del laboratorio/grupo de investigación
Aleksandra Drozdova
Aleksandra Drozdova
Investigador
Petr Kuznetsov
Petr Kuznetsov
Responsable del laboratorio/grupo de investigación
Ilya Kokorin
Ilya Kokorin
Investigador