Fault-tolerant oblivious assignment with m slots in synchronous systems

作者：Ateniese Giuseppe; Baldoni Roberto; Bonomi Silvia^*; Di Luna Giusepp Antonio

来源：Journal of Parallel and Distributed Computing, 2014, 74(7): 2648-2661.

DOI：10.1016/j.jpdc.2014.02.008

• Distributed coordination abstractions
• Secure computations
• Mutual exclusion
• Distributed systems
• Failures

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.

• 出版日期2014-7