並列処理の理論とホモトピー

ホモトピー論の concurrency への応用については, Gunawardena の結果 [Gun94] が一つのきっかけとなっているようである。2-phase locking が安全である, という database の理論ではよく知られているらしい事実を, ホモトピー論を用いて証明している。 Gunawardena の論文は, Gunawardena 自身の website から download できる。そのページによると, この Gunawardena は, Segal予想に関する論文 [AGM85] を書いた Gunawardena と同一人物らしい。 計算機科学, そして生物学に興味が移った経緯についても, その website に詳しく書かれている。

Gunawardena の論文は, 1960年代に Dijkstra により提案された並列処理の表現方法に依っている。 つまり, \(n\)個のプロセスの transaction を \(\R ^n\) 内の点で表し, 複数のプロセスが同時に一つのデータを lock することになる「禁止領域」を \(\R ^n\) の中の部分集合として表すというものである。

よりホモトピー論的なアプローチとして, Gaucher が積極的に現代的なホモトピー論の概念を導入していて, 例えば, [Gau03] では, モデル圏を使ったりしている。 他にも, 様々な新しい概念が導入されているようである。

“Homology, Homotopy and Applications”の vol.5 No.2 は Stanford の workshop の報告集になっていて, 一見に値する。

このような分野は, Bubenik の言葉 [Bub09] を借りると“directed algebraic topology” と呼ぶのがよさそうである。“Directed homotopy theory” と呼んでもよさそうな気がするが, “directed homotopy” は, Grandis により定義された concurrency の特定のモデルを指すようである。

• directed algebraic topology

Gaucher [Gaub] によると, Cattani と Sassone による別の系統のモデル [CS96] もあるらしい。 Gaucher は higher dimensional transition system と呼んでいる。

• HDTS (higher dimensional transition system)

Gaucherは, その論文と続編 [Gaua] で, これについても model category の構造を付与することができることを示している。

Bubenik [Bub12] は, simplicial category を使うことを提案している。またそれによると, 同様のモデルとして Raussen の [Rau10] がある。

別の方向では, Kozlov ら [Koz12; Koza; Kozb] が distributed computing の model として構成した simplicial complexの familyがある。 本も出版されている [HKR14]。

References

[AGM85]

J. F. Adams, J. H. Gunawardena, and H. Miller. “The Segal conjecture for elementary abelian \(p\)-groups”. In: Topology 24.4 (1985), pp. 435–460.

[Bub09]

Peter Bubenik. “Models and van Kampen theorems for directed homotopy theory”. In: Homology, Homotopy Appl. 11.1 (2009), pp. 185–202. arXiv: 0810.4164. url: http://projecteuclid.org/euclid.hha/1251832565.

[Bub12]

Peter Bubenik. “Simplicial models for concurrency”. In: Proceedings of the Workshop on Geometric and Topological Methods in Computer Science (GETCO). Vol. 283. Electron. Notes Theor. Comput. Sci. Elsevier Sci. B. V., Amsterdam, 2012, pp. 3–12. arXiv: 1011.6599. url: https://doi.org/10.1016/j.entcs.2012.05.002.

[CS96]

Gian Luca Cattani and Vladimiro Sassone. “Higher-dimensional transition systems”. In: 11th Annual IEEE Symposium on Logic in Computer Science (New Brunswick, NJ, 1996). Los Alamitos, CA: IEEE Comput. Soc. Press, 1996, pp. 55–62. url: http://dx.doi.org/10.1109/LICS.1996.561303.

[Gaua]

Philippe Gaucher. Homotopy Theory of Labelled Symmetric Precubical Sets. arXiv: 1208.4494.

[Gaub]

Philippe Gaucher. Towards a homotopy theory of higher dimensional transition systems. arXiv: 1011.0918.

[Gau03]

Philippe Gaucher. “A model category for the homotopy theory of concurrency”. In: Homology Homotopy Appl. 5.1 (2003), pp. 549–599. arXiv: math/0308054. url: http://projecteuclid.org/euclid.hha/1139839943.

[Gun94]

Jeremy Gunawardena. “Homotopy and Concurrency”. In: Bulletin of the EATCS 54 (1994), pp. 184–193.

[HKR14]

Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum. Distributed computing through combinatorial topology. Elsevier/Morgan Kaufmann, Waltham, MA, 2014, pp. xiv+319. isbn: 978-0-12-404578-1.

[Koza]

Dmitry N. Kozlov. Topology of the view complex. arXiv: 1311.7283.

[Kozb]

Dmitry N. Kozlov. Weak symmetry breaking and abstract simplex paths. arXiv: 1311.7289.

[Koz12]

Dmitry N. Kozlov. “Chromatic subdivision of a simplicial complex”. In: Homology Homotopy Appl. 14.2 (2012), pp. 197–209. url: http://dx.doi.org/10.4310/HHA.2012.v14.n2.a12.

[Rau10]

Martin Raussen. “Simplicial models of trace spaces”. In: Algebr. Geom. Topol. 10.3 (2010), pp. 1683–1714. url: http://dx.doi.org/10.2140/agt.2010.10.1683.