Le vendredi 24 juin à partir de 10h30, Ajoy K. Datta, professeur à l'Université du Nevada (Las Vegas), donnera un séminaire en salle 201. Ses principaux thèmes de recherche concernent les systèmes distribués et l'auto-stabilisation.
We give a silent self-stabilizing protocol for computing a maximum matching in an anonymous network with a tree topology. The round complexity of our protocol is O(diam), where diam is the diameter of the network, and the step complexity is O(n.diam), where n is the number of processes in the network. The working space complexity is O(1) per process, although the output necessarily takes O(log delta) space per process, where delta is the degree of that process. To implement parent pointers in constant space, regardless of degree, we use the cyclic Abelian group Z_7.
