研究小组

并发和分布式系统的算法

该实验室研究并发(多核)和分布式(大规模网络化)系统的算法。 我们的关注点是研究这些系统背后的基本原理,并理解复杂性下限和可计算性。

目前正在进行的研究项目:

  • 并发系统:

    • 分布感知的并发数据结构(与奥地利 IST 的 Dan Alistarh 合作)。
      当某些键比其他键更频繁地被请求时,键-值数据结构上的负载是倾斜的。 在顺序设置中,我们通常使用一些分布感知的自动调节的数据结构,如伸展樹。 我们能否将这一原则应用于并发系统? 
    • 范围查询并发数据结构(与奥地利 IST 的 Dan Alistarh 合作)。
      传统的数据库查询是插入、删除和遏制检查。 但我们也可以考虑范围查询,即计算键位于给定范围内的元素的数量。 如何在并发环境下实现这种范围查询,这些实现的内在成本是什么? 
    • 更便于内存的并发数据结构。
      将共享数据存储在随之产生的内存范围中,由于优化了缓存的利用,从而提高了性能。 我们想从根本上研究这个设计原则。 为此,我们引入了更便于内存和内存最优型并发实现的概念,我们正在研究它们的性能和复杂性界限。
    • 并发数据结构验证的复杂性(与內蓋夫本-古里安大学的 Danny Hendler 合作)。
      用来验证并发数据结构正确性的传统技术要么是实验性的,要么是正式的。 但是我们对这种验证的复杂性有了解吗? 例如,它是 NP 完全的吗?
    • ML 驱动的搜索数据结构(与奥地利 IST 的 Dan Alistarh 合作)。
      目前处理基于索引的数据结构的趋势是应用机器学习。 这个项目的目标是使这些技术并发化。
    • 并行的分批数据结构。
      在基本数据结构方面,如二进制搜索树、插值搜索树、学习索引等,我们研究批量操作的并行构建和并行应用。
  • 分布式系统:

    • 自我调整网络(与维也纳大学的 Stefan Schmid 合作)。
      我们试图在不同的实际模型中发展自动调节的网络的理论。
    • 排序一致的分片。
      假设一个数据库在分片上存储了一个键的集合,并且它们的数量会随着时间而改变。 一般的任务是在增加/删除键的情况下在分片之间有效地重新分配键。 对于无序的键集合,有很多众所周知的解决方案,例如,一致性和最高随机权重哈希。 然而,这些方法有一个主要的缺点:键被存储在分片上时不考虑键的顺序,如果我们想执行一个范围请求(例如,GetAllKeys(MinKey, MaxKey)),我们必须查询每个分片。 我们的方法必须考虑顺序,以尽可能的高效。
    • 动态的、可重新配置的和可问责的复制服务。
      容错复制服务的主要挑战,特别是区块链,是在相互不信任的系统中实现对共享数据的可信访问。 系统参与者可能会有冲突的利益,甚至可能愿意作弊,但实施时应要确保他们以一致、可用和公平的方式共享数据和交换资产。 按照最初的设想,区块链在一个非常困难的模型中解决了一个非常困难的问题。 毫不奇怪,现有的解决方案特别缓慢和低效。 这个项目的目标是通过考虑问题的较弱但仍然实用的变体,以及模型的较强但更现实的变体,来发现新颖和高效的数据共享实现。

这些项目目前正由以下学生承担: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)。

联系人: Vitaly Aksenov, aksenov.vitaly@gmail.com.

如果您有兴趣合作,请随时与我们联系。

小组成员

Vitaly Aksenov
Vitaly Aksenov
研究实验室/小组负责人
Aleksandra Drozdova
Aleksandra Drozdova
研究员
Petr Kuznetsov
Petr Kuznetsov
研究实验室/小组负责人
Ilya Kokorin
Ilya Kokorin
研究员