연구 그룹

Algorithms for Concurrent and Distributed Systems

The lab researches algorithms for concurrent (multi-core) and distributed (large-scale 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:

    • Distribution-aware concurrent data structures (with Dan Alistarh, IST Austria).
      The load on a key-value data structure is skewed when some keys are requested more frequently than others. In a sequential setting, we typically use some distribution-aware self-adjusting data structures, such as splay trees. Can we apply this principle in a concurrent system? 
    • Range-query 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? 
    • Memory-friendly 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 memory-friendly and memory-optimal concurrent implementations and we are studying their performance and complexity bounds.
    • Complexity of verification of concurrent data structures (with Danny Hendler, Ben-Gurion 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 NP-complete?
    • ML-driven search data structures (with Dan Alistarh, IST Austria).
      The current trend in index-based 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.
  • Distributed systems:

    • Self-adjusting Networks (with Stefan Schmid, U of Vienna).
      We try to develop the theory of self-adjusting 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 well-known 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 range-request (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 fault-tolerant 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 data-sharing implementations by considering weaker but nonetheless practical variants of the problem, and stronger but more realistic variants of the model.

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
Vitaly Aksenov
연구소/그룹 책임자
Aleksandra Drozdova
Aleksandra Drozdova
학생
Petr Kuznetsov
Petr Kuznetsov
연구소/그룹 책임자
Ilya Kokorin
Ilya Kokorin
학생