Deterministic network exploration by a single agent with Byzantine tokens

A mobile agent has to explore an unknown network with unlabeled nodes: it must visit all nodes by walking along the links of the network, and eventually stop. If no upper bound on the size of the network is known and nodes of the network cannot be marked, then this exploration task cannot be accomplished for arbitrary networks by a deterministic terminating algorithm. On the other hand, it is feasible, if there is one unmovable token at the starting node of the agent. We investigate the exploration problem in arbitrary networks in the presence of identical unmovable tokens, some of which are Byzantine. A Byzantine token can be visible or invisible to the agent whenever the latter visits the node where the token is located, and visibility is decided by the adversary at each visit of the agent. If no upper bound on the number of tokens is known to the agent, deterministic exploration of all networks is impossible, even if all tokens are fault free. It is also impossible if all tokens are Byzantine, even if their number is known. Our main result is a deterministic exploration algorithm with cost polynomial in the (unknown) size of the network, which works in arbitrary networks, provided that the agent knows some upper bound on the total number of tokens, and that at least one token is fault free.

► Deterministic exploration algorithm.
► Works for all undirected connected graphs.
► Works if the agent knows an upper bound on the number of tokens.
► Tokens can be Byzantine.
► Works in polynomial time.