Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Distinguishing Views in Symmetric Networks: A Tight Lower Bound

Dariusz Dereniowski 1 Adrian Kosowski 2, 3 Dominik Pajak 2, 3
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, ...
Complete list of metadatas

https://hal.inria.fr/hal-00875370
Contributor : Adrian Kosowski <>
Submitted on : Monday, October 21, 2013 - 8:40:09 PM
Last modification on : Wednesday, September 16, 2020 - 12:46:03 PM
Long-term archiving on: : Friday, April 7, 2017 - 2:35:07 PM

File

view.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00875370, version 1

Citation

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

Share

Metrics

Record views

112

Files downloads

70