近年、低性能なデバイスを使った自律分散システムが注目を集めている. そのような低性能なデバイスではその機能が大きく制限されるため、既存の分散システムで扱われるアルゴリズムを適用できない。 そこで、本研究ではそのような機能の制限を考慮した個体群プロトコルモデルを使い、基礎的なタスクを解くために必要な空間計算量を考える。 本研究では、基礎的なタスクとしてk分割問題に着目する。 k分割問題とは、デバイス群全体をk個の同サイズのグループに分けることを目的とした問題である。ここで、kは正の整数である。 さらに本研究では、通信グラフが完全グラフである場合と任意グラフである場合の2つの場合で問題を考えた。 通信グラフが完全グラフである場合、kを2に限定した問題では、先行研究が多くの設定で空間計算量を明らかにしている。 しかしながら、いくつかの設定では、空間計算量が完全に明らかになっていない。 そこで、本研究では、その残りの設定の空間計算量を明らかにした。 さらに、通信グラフが完全グラフのk分割問題に関しても、 ある設定において漸近的に空間最適なアルゴリズムを提案した。 通信グラフが任意グラフである場合は、まずその第一歩としてkを2に限定した問題を考えた。 結果として、その空間計算量を多くの設定の下で明らかにした。
本発表では特に、任意グラフで特定の設定下でのk分割のアルゴリズムを紹介する。