An application, peer and method for determining a faulty peer in a structured Peer-to-Peer overlay network. The overlay network includes plural peers besides the faulty peer. The method includes determining that a message sent from a given peer to a target peer along a first path did not reach the target peer; determining an intermediate peer at which the message had arrived; using a second path to send the message from the given peer to the target peer; determining that the message had arrived at the target peer on the second path; adjusting a node identifier (nodeID) of at least one of the target peer and the intermediate peer to obtain a new target peer or a new intermediate peer; and reusing the first and second paths to send the message to the new target peer or the new intermediate peer until the faulty peer is detected.