Citation

@inproceedings{10.1145/1807167.1807184,
author = {Malewicz, Grzegorz and Austern, Matthew H. and Bik, Aart J.C and Dehnert, James C. and Horn, Ilan and Leiser, Naty and Czajkowski, Grzegorz},
title = {Pregel: A System for Large-Scale Graph Processing},
year = {2010},
isbn = {9781450300322},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1807167.1807184},
doi = {10.1145/1807167.1807184},
booktitle = {Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data},
pages = {135–146},
numpages = {12},
keywords = {distributed computing, graph algorigthms},
location = {Indianapolis, Indiana, USA},
series = {SIGMOD ’10}
}

どんなもの？

グラフ処理を分散処理する方法と、そのフレームワークの C++ 実装。頂点間のメッセージのやり取りで処理を行っていく。

先行研究と比べてどこがすごい？

  • 汎用的な分散処理（MapReduce）に対するアドバンデージ → グラフ処理を一般化すると、各頂点ごとに値が変化していくようなものが多く、 MapReduce 形式にしようとすると、すべての頂点の値を次のステージへ転送する必要があって苦しい。
  • 他の分散グラフ処理に対するアドバンテージ → フォールトトレランス（一部に障害があっても動作する）についての考慮がある。ステップごとに状態を記録しておくことで、障害が発生する前の状態から計算し直せる。

技術や手法のキモはどこ？

頂点間のメッセージパッシングによって処理が進んでいく。頂点はメッセージを受け取ると、処理をひとつ（このステップをスーパーステップと呼ぶ）進める。スーパーステップごとに同期することで、その間は頂点ごとに並列に処理を進めることができる。

どうやって有効だと検証した？

  • このプログラミングモデルでグラフ処理を表現できるか → 少なくとも筆者が知る限りのアルゴリズムは、このモデルで実装することができる。
  • 最短経路探索アルゴリズムをワーカー数を変化させて実行することで、分散処理による高速化を確認した。他の手法との比較はない。

議論はある？

前提として、スパース（ひとつの頂点に対して辺がそんなにない）なグラフを想定しているので、密なグラフではパフォーマンスに問題があるかもしれない。しかし、そのようなグラフは稀であると主張している。

次に読むべき論文は？