Fault-tolerant oblivious assignment with m slots in synchronous systems

Preserving anonymity and privacy of customer actions within a complex software system, such as a cloud computing system, is one of the main issues that should be addressed to boost private computation outsourcing. In this paper, we propose a coordination paradigm, namely oblivious assignment with m slots of a resource R (with m >= 1), allowing processes to compete in order to get a slot of R, while ensuring at the same time both fairness in the assignment of resource slots and that no process learns which slot of R is assigned to a specific process. We present a distributed algorithm solving oblivious assignment with m slots within a distributed system, assuming (1) a bounded number of crash failures f, (2) the existence of at least f + 2 honest processes, and (3) m <= n (where n is the number of processes). The algorithm is based on a rotating token paradigm and its correctness is formally proved. A probabilistic analysis of the average waiting time before getting a slot is also provided. (C) 2014 Elsevier Inc. All rights reserved.