Transformations on Quorum Structures

基于仲裁的协议是根据称为“仲裁结构”的数据结构形式化的。已经进行了几次尝试，以根据各种度量（例如可用性和仲裁大小）获得最佳仲裁结构。然而，一组节点U下的群体数量可能在ıU！，并且随着节点数量的增加，quorum结构上的许多基本计算（如可用性分析）变得难以处理。因此，在大量节点下获得“最优”群体是极其困难的。本研究将探讨以仲裁结构为输入并返回新的仲裁结构的仲裁结构转换。特别地，将定义以下转换：1。在比输入仲裁结构大得多的节点集下生成一个新的结构；保留输入结构的某些理想属性，或将输入结构转换为具有理想属性的结构。这种转换对于在大量节点下生成“良好”的仲裁结构非常有用，原因如下：具有某些理想性质的仲裁结构即使在大型节点集下也可以很容易地构建；分而治之的方法可用于计算由这种转换构造的仲裁结构。这使得诸如可用性分析之类的计算成为可能，否则这些计算是“难以处理的”。

Quorum based protocols are formalized in terms of data structures called "quorum structures." Several attempts have been made to obtain optimal quorum structures in terms of various measures, such as availability and quorum size. However, the number of quorums under a set of nodes U may be exponential in ıU!, and many essential computations on quorum structures, such as availability analysis, become intractable as the number of nodes becomes large. Thus, obtaining "optimal" quorums under a large set of nodes is extremely difficult. This research will investigate transformations of quorum structures which take quorum structures as input and return new quorum structures. In particular, transformations will be defined which: 1. generate a new structure under a substantially larger set of nodes than the input quorum structures, and 2. preserve certain desirable properties of the input structures, or convert input structures into a structure with desirable properties. Such transformations are extremely useful to generate "good" quorum structures under a large set of nodes for the following reasons: 1. quorum structures which have certain desirable properties may be easily constructed even under a large set of nodes, and 2. a divide and conquer approach may be used for computations on the quorum structures constructed by such transformations. This enables such computations as availability analysis which are otherwise "intractable."