연구 그룹

동시 및 분산 시스템을 위한 알고리즘

연구소에서는 동시(멀티 코어) 및 분산(대규모 네트워크) 시스템에 적용하기 위한 알고리즘을 연구합니다. 이러한 시스템을 뒷받침하는 원리를 조사하고 복잡성의 하한선과 계산 가능성을 이해하는 데 중점을 둡니다.

현재 연구 프로젝트:

  • 동시 시스템:

    • 분포 인식 동시 데이터 구조(Dan Alistarh, IST Austria).
      일부 키가 다른 키보다 더 자주 요청될 때 키-값 데이터 구조의 부하가 왜곡됩니다. 순차적 환경에서는 일반적으로 스플레이 트리(splay tree)와 같은 일부 분포 인식 자체 조정 데이터 구조를 사용합니다. 동시 시스템에 이 원리를 적용할 수 있을까요? 
    • 범위 쿼리 동시 데이터 구조(Dan Alistarh, IST Austria).
      기존의 데이터베이스 쿼리는 삽입, 삭제 및 포함 검사입니다. 그러나 범위 쿼리(즉, 지정된 범위 안에 키가 있는 요소의 수를 계산)도 생각할 수 있습니다. 이러한 범위 쿼리를 동시 환경에서 구현할 수 있는 방법은 무엇이고 이러한 구현에 대해 내재적으로 치러야 할 대가는 무엇일까요? 
    • 메모리 친화적인 동시 데이터 구조.
      결과적인 메모리 범위에 공유 데이터를 저장하면 캐시 사용률이 최적화되어 성능이 향상됩니다. 우리는 이 설계 원리를 근본적인 수준에서 연구하고자 합니다. 이를 위해 메모리 친화적이고 메모리에 최적화된 동시 구현이라는 개념을 도입했으며 그 성능과 복잡성의 한계를 연구하고 있습니다.
    • 동시 데이터 구조를 검증할 때의 복잡성(Danny Hendler, Ben-Gurion 대학).
      동시 데이터 구조의 정확성을 검증하는 데 사용되는 기존의 기술은 실험적이거나 형식적입니다. 그렇다면 우리가 이러한 검증의 복잡성에 대해 알고 있는 것이 있을까요? 예를 들어 NP가 완전한 상태인가요?
    • ML 기반의 검색 데이터 구조(Dan Alistarh, IST Austria).
      인덱스 기반 데이터 구조의 현재 추세는 기계 학습을 적용하는 것입니다. 이 프로젝트의 목표는 이러한 기술을 동시화하는 것입니다.
    • 병렬 일괄 처리 데이터 구조.
      2진 검색 트리, 보간 검색 트리, 학습된 인덱스 등과 같은 기본적인 데이터 구조의 맥락에서 작업 배치의 병렬 구성과 병렬 적용을 연구합니다.
  • 분산 시스템:

    • 자체 조정 네트워크(Stefan Schmid, U of Vienna).
      우리는 서로 다른 실용적 모델에서 자체 조정 네트워크의 이론을 개발하기 위해 노력하고 있습니다.
    • 순서와 관련하여 일관된 샤딩.
      데이터베이스가 샤드에 키 컬렉션을 저장하고 시간이 지남에 따라 그 수가 변할 수 있다고 가정합니다. 키가 추가/제거되는 경우에 샤드 사이에서 이러한 키를 효율적으로 재배포하는 것이 일반적인 작업입니다. 예를 들어 일관된 랑데부 해싱과 같이 정렬되지 않은 키 집합에 대해 잘 알려진 솔루션이 많이 있습니다. 그러나 이러한 접근 방식에는 한 가지 큰 단점이 있는데, 키가 그 순서를 따지지 않고 샤드에 저장되고, 범위 요청(예를 들어, 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
연구원