研究小组
Algorithms for Concurrent and Distributed Systems
The lab researches algorithms for concurrent (multicore) and distributed (largescale networked) systems. Our focus is on investigating the fundamental principles behind these systems, and understanding complexity lower bounds and computability.
Current Research Projects:

Concurrent systems:
 Distributionaware concurrent data structures (with Dan Alistarh, IST Austria).
The load on a keyvalue data structure is skewed when some keys are requested more frequently than others. In a sequential setting, we typically use some distributionaware selfadjusting data structures, such as splay trees. Can we apply this principle in a concurrent system?  Rangequery concurrent data structures (with Dan Alistarh, IST Austria).
Conventional database queries are insertion, deletion, and containment check. But we can also think of range queries, i.e., counting the number of elements whose keys lie inside a given range. How can such range queries be implemented in a concurrent setting, and what are the inherent costs of these implementations?  Memoryfriendly concurrent data structures.
Storing shared data in consequent memory ranges results in improved performance due to optimized cache utilization. We want to study this design principle at a fundamental level. To this end, we have introduced the notion of memoryfriendly and memoryoptimal concurrent implementations and we are studying their performance and complexity bounds.  Complexity of verification of concurrent data structures (with Danny Hendler, BenGurion University).
Conventional techniques used to verify the correctness of concurrent data structures are either experimental or formal. But do we know anything about the complexity of such verification? For example, is it NPcomplete?  MLdriven search data structures (with Dan Alistarh, IST Austria).
The current trend in indexbased data structures is to apply machine learning. The goal of this project is to make these techniques concurrent.  Parallel batched data structures.
In the context of basic data structures, such as binary search tree, interpolation search tree, learned index, and so on, we research the parallel construction and parallel application of batches of operations.
 Distributionaware concurrent data structures (with Dan Alistarh, IST Austria).

Distributed systems:
 Selfadjusting Networks (with Stefan Schmid, U of Vienna).
We try to develop the theory of selfadjusting networks in different practical models.  Consistent sharding with respect to ordering.
Suppose a database stores a collection of keys on shards, and their quantity can change with time. The typical task is to efficiently redistribute keys between shards in the case of their addition/removal. There are plenty of wellknown solutions for unordered sets of keys, for example, consistent and rendezvous hashing. However, these approaches have one major drawback: the keys are stored on shards without any respect to the order of the keys, and if we want to execute a rangerequest (for example, GetAllKeys(MinKey, MaxKey)), we have to query each shard. Our approach has to respect the order and be as efficient as possible.  Dynamic, reconfigurable and accountable replicated services.
The principal challenge of faulttolerant replicated services, and blockchains in particular, is to implement trustworthy access to shared data in systems with mutual distrust. System participants may have conflicting interests and might even be willing to cheat, but the implementation is expected to ensure that they share data and exchange assets in a consistent, available, and fair way. As originally conceived, blockchains solve a very hard problem in a very hard model. Not surprisingly, existing solutions are notoriously slow and inefficient. The goal of this project is to discover novel and efficient datasharing implementations by considering weaker but nonetheless practical variants of the problem, and stronger but more realistic variants of the model.
 Selfadjusting Networks (with Stefan Schmid, U of Vienna).
These projects are currently being undertaken by the following students: 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).
Contact: Vitaly Aksenov, aksenov.vitaly@gmail.com.
If you are interested in collaborating, please do not hesitate to contact us.
小组成员
Vitaly Aksenov
研究实验室/小组负责人
Aleksandra Drozdova
学生
Petr Kuznetsov
研究实验室/小组负责人
Ilya Kokorin
学生