An Efficient Systematic Approach to Find All Cyclic Quorum Sets with All-pairs Property

The use of cyclic quorum sets has proved to be an efficient method for distributed systems to solve t asks requiring massive computations. In all-pairs data interaction problem, cyclic quorum sets can be used to avoid communication completely after initial data placement. However, searching for cyclic quorum sets with all-pairs property for a given number of objects, p, in a distributed system is a daunting task that involves massive computations as it is a combinatorial problem requiring full search. No time complexity reduction method has been found thus far. In other applications of cyclic quorum sets such as cycle-based routing problem, different cyclic quorum sets provide similar fault coverage yet generate significant resource utilization difference. Inspired by the need for all cyclic quorum sets with all-pairs property, we develop a methodology to optimize the search process by avoiding the search space where no new set could be found. After studying all possible cyclic quorum sets for a given p, we develop insights into the properties of all quorum sets that helps us to reduce the number of searches significantly. A s a result, for small values of p, when doing brutal-force search, our method not only reduces the time to find the first cyclic quorum base set with all-pairs property but is also able to find a ll of them in a reasonable amount of time. Moreover, we notice that as p grows, up to several orders of magnitude of search reduction could be achieved compared to naïve search. For large values of p, with existing results of base sets, we also propose a heuristic method with constant time complexity that computes a feasible subsets-assigning solution that meets the all-pairs requirement.

I. Introduction

A large number of applications use a big volume of data in the current wave of data-based decision-making processes. One of the most significant big data problems a rises when many data elements need to interact with each other to derive meaningful conclusions. It is known as all-pairs data interaction problem and has many applications such as in data mining, the computation of similarity matrix is a critical step for clustering and classification. [1] It provides all pairwise similarities and dissimilarities between objects. [2] In physics and astronomy, n-body problem is commonly found and it consists of prediction the motions of a group of large, celestial objects interacting with one another. [3]