Distinguishing views in symmetric networks A tight lower bound.pdfVIP

Theoretical Computer Science 582 (2015) 27–34 Contents lists available at ScienceDirect Theoretical Computer Science /locate/tcs Distinguishing views in symmetric networks: A tight lower bound Dariusz Dereniowski a,?,1, Adrian Kosowski b, Dominik Paja?k c a Faculty of Electronics, Telecommunications and Informatics, Gdan′sk University of Technology, Poland b Inria Paris and LIAFA, Université Paris Diderot, France c Computer Laboratory, University of Cambridge, United Kingdom article info Article history: Received 22 October 2013 Received in revised form 29 January 2015 Accepted 8 March 2015 Available online 14 March 2015 Communicated by D. Peleg Keywords: Anonymous network Port-labeled network View Quotient graph abstract The view of a node in a port-labeled network is an in?nite tree encoding all walks in the network originating from this node. We prove that for any integers n ≥ D ≥ 1, there exists a port-labeled network with at most n nodes and diameter at most D which contains a pair of nodes whose (in?nite) views are different, but whose views truncated to depth (D log(n/D)) are identical. ? 2015 Elsevier B.V. All rights reserved. 1. Introduction The notion of a view was introduced and ?rst studied by Yamashita and Kameda in [19] in the context of distributed message passing algorithms. In so-called anonymous networks (without unique identi?ers accessible to a distributed algorithm), the view is a fundamental concept which allows for identi?cation of the network topology and for breaking of symmetries between nodes. Different views for a pair of nodes guarantee that the corresponding nodes are distinguishable, which is useful in, e.g., leader election algorithms. View-based approaches have been successfully used when designing algorithms for various network problems, including map construction [3,9], leader election [4,6,8,12,17,20], rendezvous [5,7,13], and other tasks [10,18]. The view from a node of a network is by de?nition (cf. Section 2) an in?nite rooted