Transformations on Quorum Structures

基于仲裁的协议按照称为“仲裁结构”的数据结构进行形式化。已经进行了几次尝试，以获得关于诸如可用性和仲裁大小的各种度量的最优仲裁结构。然而，在ıU！中，一组节点U下的仲裁数目可能是指数的，并且许多关于仲裁结构的基本计算，例如可用性分析，随着节点数目的增加而变得困难。因此，在大量节点下获得“最佳”法定人数是极其困难的。本研究将研究以Quorum结构为输入并返回新Quorum结构的Quorum结构转换。具体地，将定义如下变换：1.在比输入法定结构大得多的节点集合下生成新结构，以及2.保留输入结构的某些所需属性，或将输入结构转换为具有所需属性的结构。这种转换对于在大量节点下生成“良好的”仲裁结构非常有用，原因如下：1即使在一大组节点下也可以容易地构建具有某些所需属性的法定结构，以及2.可以使用分而治之的方法对由这种变换构造的仲裁结构进行计算。这使得诸如可用性分析之类的计算成为可能，否则这些计算是“棘手的”。

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."