Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
On Distinguishing Views in Symmetric Networks.
du groupe Algorithmique Distribuée

Date 2015-10-12  14:00-15:00
TitreOn Distinguishing Views in Symmetric Networks. 
RésuméThe view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. It is an important concept in the context of symmetry breaking in distributed systems. For example a deterministic rendezvous is infeasible if the agents start from positions with the same views. We want to decide if two views are identical but we would like to compare the infinite trees truncated to certain depth d. We are looking for such d that if the views truncated to depth d are equal then the whole infinite trees are also equal and there are some nodes whose views differ only at depth d. It turns out that truncating to depth Theta(D*log(n/D)) (where D is the diameter and n is the number of nodes) is always sufficient and sometimes necessary to distinguish the views. The talk will be based on two papers: Views in a graph: to which depth must equality be checked? Julien M. Hendrickx Distinguishing Views in Symmetric Networks: A Tight Lower Bound Dariusz Dereniowski, Adrian Kosowski, Dominik Paj?k 
Lieu178 
OrateurDominik Pajak  
UrlUniversity of Cambridge 



Aucun document lié à cet événement.

Retour
Retour à l'index