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

Thumbnail Image
Bian, Yiming
Major Professor
Committee Member
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Journal Issue
Is Version Of
Electrical and Computer Engineering
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.
This is a manuscript of a proceeding published as Bian, Yiming, and Arun K. Somani. "An Efficient Systematic Approach to Find All Cyclic Quorum Sets with All-pairs Property." In 2021 IEEE International Conference on Big Data (Big Data), pp. 197-206. IEEE, 2021. DOI: 10.1109/BigData52589.2021.9671935 Copyright 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Posted with permission.