Randomised Mutual Search.pdfVIP

Randomised Mutual Search⋆ Jaap-Henk Hoepman Department of Computer Science, University of Twente P.O.Box 217, 7500 AE Enschede, the Netherlands hoepman@cs.utwente.nl Abstract We study the efficiency of randomised solutions to the mutual search problem of finding k agents distributed over n nodes. For a re- stricted class of so-called linear randomised mutual search algorithms we derive a lower bound of k−1 (n+ 1)expected calls in the worst case. A k+1 randomised algorithm in the shared-coins model matching this bound is also presented. Finally we show that in general more adaptive randomised mutual algorithms perform better (using k− 1 + k−1 − k−2 (n−k)worst k+1 n case expected calls in the shared coins model) than the lower bound for the restricted case, even when given only private coins. A lower bound of k− 1 + n−k for this case is also derived. k+1 1 Introduction Buhrman et al. [BFG+99] introduce the mutual search problem, where k agents distributed over a complete network of n distinct nodes are required to learn each other’s location. Agents can do so by calling a single node at a time to determine whether it is occupied by another agent. The object is to find all other agents in as few calls as possible. Buhrman et al. study this problem extensively for synchronous and asynchronous networks, and both in the deterministic and randomised case, predominantly for k = 2 agents. The prime motivation for studying this problem is the cost of conspiracy start-up in secure multi-party computations, or Byzantine agreement problems. Traditionally, th