Cette demi-journée pôle calcul aura lieu le 18 novembre. Nous aurons la chance d’avoir trois orateurs.
Orateur : Dmitry Sokolov (LORIA)
Titre : How to compute locally invertible maps
Résumé : Mapping a triangulated surface to 2D plane (or a tetrahedral mesh to 3D space) is the most fundamental problem in geometry processing. The critical property of a good map is a (local) invertibility, and it is not an easy one to obtain. We propose a mapping method inspired by the mesh untangling problem. In computational physics, untangling plays an important role in mesh generation: it takes a mesh as an input, and moves the vertices to get rid of foldovers. In fact, mesh untangling can be considered as a special case of mapping, where the geometry of the object is to be defined in the map space and the geometric domain is not explicit, supposing that each element is regular. This approach allows us to produce locally invertible maps, which is the major challenge of mapping. In practice, our method succeeds in very difficult settings, and with less distortion than the previous work, both in 2D and 3D.
Orateur : Corentin Travers (LABRI)
Titre : Synchronous t-Resilient Consensus in Arbitrary Graphs
Résumé : We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius that considers all ways in which t nodes may crash, and present an algorithm that solves consensus in radius rounds. Then we derive a lower bound showing that our algorithm is optimal for vertex-transitive graphs, among oblivious algorithms.
Our lower bound technique is inspired by the topological techniques for distributed computing. It is similar to the connectivity analysis of the protocol complex, the structure of states at the end of executions of an algorithm after a certain number of rounds. However, instead of working with the protocol complex, we consider an information flow directed graph version based on failure patterns.
Joint work with Armando Castaneda, Pierre Fraigniaud, Ami Paz, Sergio
Rajsbaum, and Matthieu Roy
Orateur : Victor Chepoi (LIS)
Titre : 1-safe Petri nets and special cube complexes
Résumé : In the talk, I will explain the following bijection between 1-safe Petri nets and finite special cube complexes: the event structures arising as unfolding of 1-safe Petri nets are exactly the event structures whose domains arise as principal filters of the universal cover of a finite 1-safe Petri net.
This can be viewed as a positive answer to the (disproved) conjecture by Thiagarajan that the event structures arising as unfolding of 1-safe Petri nets are exactly the regular event structures. If the time permits, I will give some (positive and negative) applications of this bijection.
Joint work with Jérémie Chalopin.