Résumé

Dans cet exposé, nous présentons et étudions un algorithme de rendez-vous basé sur des délais aléatoires. Cet algorithme peut également être considéré comme un algorithme distribué probabiliste pour trouver le couplage maximal.

Tout processus du réseau génère une variable aléatoire uniforme dans l'intervalle réel [0,1] pour chacun de ses processus voisins. Le nombre produit est censé être un temps possible pour avoir un rendez-vous, si les deux processus sont disponibles à ce moment-là. Initialement, le nombre des temps potentiellement possibles proposés par les processus est deux fois le nombre de liens entre eux. Toutes les fois que l'horloge atteint le plus petit temps généré, il y aura un rendez-vous entre le processus qui propose ce temps et le processus sollicité et tous les deux annulent toutes autres données de leurs agendas, informant leurs voisins. Ces derniers mettent à jour leurs agendas en suppriment les temps qu'ils ont proposé initialement à ces deux processus. L'algorithme continue pour les processus restants jusqu'à ce que le temps 1 ait expiré.

Nous étudions l'espérence du nombre rendez-vous qui est la taille moyenne de couplage obtenu. Nous donnons une formule récursive qui pourrait être employée pour calculer, en général, ce nombre et nous donnons aussi les formes closes ou les valeurs asymptotiques pour quelques familles intéressantes des graphes (arbres, graphes aléatoires, mille-pattes, ...).

Notre algorithme est plus efficace que ceux que nous connaissons dans la mesure où le nombre prévu de rendez-vous par tour est plus grand.