[logic-ml] Talk by Nayuta Yanagisawa, Wed 30 Mar

[Toshiki Kataoka]

皆様，

以下のように，来週水曜日，京都大学の柳澤名由太さんをお招きして講演をしていただきます。
ぜひご参加ください。

-- 片岡 俊基 (Toshiki Kataoka, http://www-mmm.is.s.u-tokyo.ac.jp/~tos/)

--------------------
Wed 30 Mar 2016, 16:30–18:00
Room 236, Chemistry Building East (“Kagaku-Higashikan”). Next to our
building (School of Science Bldg. No. 7)
Access: http://www-mmm.is.s.u-tokyo.ac.jp/access.html


1. Topological Theory of Distributed Computing

分散コンピューティングへの組合せトポロジー的なアプローチについて解説します．


2. A Topological Characterization of Wait-Free Solvability in the
Infinite Arrival Model

We extend the topological theory of distributed computing for systems
with a fixed set
of n processes to that for systems with infinitely many processes. We
investigate
a necessary and sufficient condition for the finitely-valued colorless
tasks to be
wait-free solvable in such distributed systems. A finitely-valued
colorless task is a task
that assumes a finite set of possible input/output values, and
specifies input/output
relation without referring to process IDs. Our characterization only
resorts to finite
combinatorial structures, called finite simplicial complexes as the
topological device.
By restricting our attention to finitely-valued colorless tasks, we
can represent possible
protocol states that are innocent of process IDs by a finite simplicial complex,
even if the number of participating processes is infinite.