Fault-tolerant oblivious assignment with mm slots in synchronous systems

• We defined the SOmA problem in a failure-prone environment.
• We provided an algorithm solving the SOmA problem with up to ff failures.
• We provided correctness proofs.
• We provided an analysis of the average latency to get a slot.

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 mm slots of a resource RR (with m≥1m≥1), allowing processes to compete in order to get a slot of RR, while ensuring at the same time both fairness in the assignment of resource slots and that no process learns which slot of RR is assigned to a specific process. We present a distributed algorithm solving oblivious assignment with mm slots within a distributed system, assuming (1) a bounded number of crash failures ff, (2) the existence of at least f+2f+2honest   processes, and (3) m≤nm≤n (where nn 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.