リサーチグループ

並行システムおよび分散システムのアルゴリズム

並行システム(マルチコア)および分散システム(大規模ネットワーク)のアルゴリズムを研究しているラボです。 システムの背後にある基本原則を調査し、複雑さの下界と計算可能性を理解することに焦点を当てています。

現在のリサーチプロジェクト:

  • 並行システム:

    • 分散対応並行データ構造(IST Austria の Dan Alistarh との共同研究)。
      キー値データ構造にかかる負荷は、あるキーの要求頻度がほかのキーより高い場合に歪んでしまう。 連続的な環境では、スプレー木などの、分散対応自己調整データ構造を使用するのが一般的だが、 この原則を並行システムに応用できるのか? 
    • 並行データ構造の範囲クエリ(IST Austria の Dan Alistarh との共同研究)。
      挿入、削除、および包含チェックを行うのが従来のデータベースクエリだが、 キーが特定の範囲内にある要素の数を数えるというように、範囲クエリを実行することも考えられる。 このような範囲クエリを並行環境で実装するにはどうすればよいのか、またこの継承にはどのような実装コストがかかるのか? 
    • メモリへの負荷が少ない並行データ構造。
      共有データを結果のメモリ範囲に格納すると、キャッシュの使用率が最適化され、パフォーマンスが改善される。 この設計原理を基本的なレベルで研究することを目的としている。 これを行う上で、メモリフレンドリーでメモリに最適な並行実装の概念を導入し、そのパフォーマンスと複雑さの限界を研究している。
    • 並行データ構造の検証の複雑性(ベン=グリオン大学、Danny Hendler との共同研究)。
      並行データ構造の正確性を検証するにあたり、実験的または形式的な手法が従来の手法とされてきたが、 そのような検証の複雑性について理解されているのだろうか? これは NP 完全問題なのか、など。
    • ML 駆動の検索データ構造(IST Austria の 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
研究員