Distributed Computability for Sub-Models : Set-Agreement and other Simple Results from Geometrization Topology
Wednesday, June 26, 2024Speaker(s) : Emmanuel Godard (prof. LIS Marseille)
There are many distributed models that can be represented by simplicial subdivisions. We consider here models where the subdivision is in addition also mesh-shrinking. The most used model with these properties is the Iterated Immediate Snapshot model, which is known to be equivalent to the standard wait-free model. In this setting, we consider general sub-models M of such models, that is arbitrary subsets of executions. We present a new geometrization mapping $geo$ introduced recently to investigate set-agreement. We show how it is possible to associate a new topology, called the geometrization topology, to any sub-models. This topology has a simple correspondance with the standard topology of $R^n$.
Finally we show hints for getting a simple necessary and sufficient condition to have a colorless task (I, O, ∆) solvable under M in the form of the existence of a continuous function f : geo(I × M) −→ |O| carried by ∆. This necessary and sufficient condition for colorless tasks was already known for full models like the Iterated Immediate Snapshot model, so this result can be seen as an extension of this type of characterization to any submodels. As an example of its simplicity, we can now directly derive the characterization of the computability of set-agreement on submodels by a simple application of the No-Retraction theorem of standard topology textbooks. Joint work with Yannis Coutouly (Université Aix-Marseille)
Bio: Emmanuel Godard is professor at "Laboratoire d'Informatique et des Systèmes" in Marseille. He is a specialist of distributed computability, interested in unifying the many models for distributed computations through the use of topological and geometrical methods.
maria.potop-butucaru (at) nulllip6.fr