# Distinguishing Views in Symmetric Networks: A Tight Lower Bound

2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers $n\geq D\geq 1$, there exists a port-labeled network with at most $n$ nodes and diameter at most $D$ which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth $\Omega(D\log (n/D))$ are identical.
Document type :
Preprints, Working Papers, ...

https://hal.inria.fr/hal-00875370
Submitted on : Thursday, May 15, 2014 - 8:54:46 PM
Last modification on : Wednesday, September 16, 2020 - 12:46:03 PM
Long-term archiving on: : Monday, April 10, 2017 - 11:03:31 PM

### Files

view.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00875370, version 2
• ARXIV : 1407.2511

### Citation

Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak. Distinguishing Views in Symmetric Networks: A Tight Lower Bound. 2013. ⟨hal-00875370v2⟩

Record views