Searching with mobile agents in networks with liars

✍ Scribed by Nicolas Hanusse; Evangelos Kranakis; Danny Krizanc

• Book ID: 104294166
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 261 KB
• Volume: 137
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00189-6

✦ Synopsis

We present deterministic algorithms to search for an item s contained in a node of a network, without prior knowledge of its exact location. Each node of the network has a database that will answer queries of the form "how do I get to s?" by responding with the ÿrst edge on a shortest path to the node containing s. It may happen that some nodes, called liars, give bad advice. If the number of liars k is bounded, we show di erent strategies to ÿnd the item depending on the topology of the network. In particular we consider the complete graph, ring, torus, hypercube and bounded degree trees.