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 : 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

Collections

Citation

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

Share

Metrics

Record views

276

Files downloads

181