Transversal merge operation: a nondominated coterie construction method for distributed mutual exclusion

A coterie is a set of subsets (called quorums) of the processes in a distributed system such that any two quorums intersect with each other and is mainly used to solve the mutual exclusion problem in a quorum-based algorithm. The choice of a coterie sensitively affects the performance of the algorithm and it is known that nondominated (ND) coteries achieve good performance in terms of criteria such as availability and load. On the other hand, grid coteries have some other attractive features: 1) a quorum size is small, which implies a low message complexity, and 2) a quorum is constructible on the fly, which benefits a low space complexity. However, they are not ND coteries unfortunately. To construct ND coteries having the favorite features of grid coteries, we introduce the transversal merge operation that transforms a dominated coterie into an ND coterie and apply it to grid coteries. We call the constructed ND coteries ND grid coteries. These ND grid coteries have availability higher than the original ones, inheriting the above desirable features from them. To demonstrate this fact, we then investigate their quorum size, load, and availability, and propose a dynamic quorum construction algorithm for an ND grid coterie.     

Coterie join algorithm

Given a set of nodes in a distributed system, a coterie is a collection of subsets of the set of nodes such that any two subsets have a nonempty intersection and are not properly contained in one another. A subset of nodes in a coterie is called a quorum. An algorithm, called the join algorithm, which takes nonempty coteries as input, and returns a new, larger coterie called a composite coterie is introduced. It is proved that a composite coterie is nondominated if and only if the input coteries are nondominated. Using the algorithm, dominated or nondominated coteries may be easily constructed for a large number of nodes. An efficient method for determining whether a given set of nodes contains a quorum of a composite coterie is presented. As an example, tree coteries are generalized using the join algorithm, and it is proved that tree coteries are nondominated. It is shown that the join algorithm may be used to generate read and write quorums which may be used by a replica control protocol     

Nondominated coteries on graphs

Let C and D be two distinct coteries under the vertex set V of a graph G=(V,E) that models a distributed system. Coterie C is said to G-dominate D (with respect to G) if the following condition holds: For any connected subgraph H of G that contains a quorum in D (as a subset of its vertex set), there exists a connected subgraph H' of H that contains a quorum in C. A coterie C on a graph G is said to be G-nondominated (G-ND) (with respect to G) if no coterie D(≠C) on G G-dominates C. Intuitively, a G-ND coterie consists of irreducible quorums. This paper characterizes G-ND coteries in graph theoretical terms, and presents a procedure for deciding whether or not a given coterie C is G-ND with respect to a given graph G, based on this characterization. We then improve the time complexity of the decision procedure, provided that the given coterie C is nondominated in the sense of Garcia-Molina and Barbara (1985). Finally, we characterize the class of graphs G on which the majority coterie is G-ND     

Minimizing the maximum delay for reaching consensus in quorum-basedmutual exclusion schemes

The use of quorums is a well-known approach to achieving mutual exclusion in distributed computing systems. This approach works based on a coterie, a special set of node groups where any pair of the node groups shares at least one common node. Each node group in a coterie is called a quorum. Mutual exclusion is ensured by imposing that a node gets consensus from all nodes in at least one of the quorums before it enters a critical section. In a quorum-based mutual exclusion scheme, the delay for reaching consensus depends critically on the coterie adopted and, thus, it is important to find a coterie with small delay. Fu (1997) introduced two related measures called max-delay and mean-delay. The former measure represents the largest delay among all nodes, while the latter is the arithmetic mean of the delays. She proposed polynomial-time algorithms for finding max-delay and mean-delay optimal coteries when the network topology is a tree or a ring. In this paper, we first propose a polynomial-time algorithm for finding max-delay optimal coteries and, then, modify the algorithm so as to reduce the mean-delay of generated coteries. Unlike the previous algorithms, the proposed algorithms can be applied to systems with arbitrary topology     

Recognizing nondominated coteries and wr-coteries by availability

Coterie is a widely accepted concept for solving the mutual exclusion problem. Nondominated coteries are an important class of coteries which have better performance than dominated coteries. The performance of a coterie is usually measured by availability. Higher availability of a coterie exhibits greater ability to tolerate node or communication link failures. In this paper, we demonstrate a way to recognize nondominated coteries using availability. By evaluating the availability of a coterie instead of using a formal proof, the coterie can be recognized as a nondominated coterie or not. Moreover, with regard to wr-coterie, a concept for solving the replica control problem, we also present a similar result for recognizing nondominated wr-coteries. Finally, we apply our results to some well-known coteries and wr-coteries     

Composite k-arbiters

The k-arbiter is a useful concept to solve the distributed h-out-of-k mutual exclusion problem. The distributed h-out-of-k mutual exclusion algorithms, based on the k-arbiter, have the benefits of high fault tolerance and low message cost. However, according to the definition of the k-arbiter, it is required to have a nonempty intersection among any (κ + 1) quorums in a k-arbiter. Consequently, constructing k-arbiters is difficult. The coterie join operation proposed by Neilsen and Mizuno (1992) produces a new and larger coterie by joining known coteries. By extending the coterie join operation, we first propose a k-arbiter join operation to construct a new and larger k-arbiter from known k-arbiters for a large system. Then, we derive a necessary and sufficient condition for the k-arbiter join operation to construct a nondominated joined k-arbiter. Moreover, we discuss availability properties of the joined k-arbiters. We observe that, by selecting proper k-arbiters, the joined k-arbiter can provide a higher availability than that of the original input. Finally, we propose a k-arbiter compound, operation to construct k-arbiters by using coteries and/or k-coteries. By that way, the problem of constructing k-arbiters can be reduced to the problem of constructing coteries and/or k-coteries     

Recognition of interval Boolean functions

Interval functions constitute a special class of Boolean functions for which it is very easy and fast to determine their functional value on a specified input vector. The value of an n-variable interval function specified by interval [a,b] (where a and b are n-bit binary numbers) is true if and only if the input vector viewed as an n-bit number belongs to the interval [a,b]. In this paper we study the problem of deciding whether a given disjunctive normal form represents an interval function and if so then we also want to output the corresponding interval. For general Boolean functions this problem is co-NP-hard. In our article we present a polynomial time algorithm which works for monotone functions. We shall also show that given a Boolean function f belonging to some class which is closed under partial assignment and for which we are able to solve the satisfiability problem in polynomial time, we can also decide whether f is an interval function in polynomial time. We show how to recognize a “renamable” variant of interval functions, i.e., their variable complementation closure. Another studied problem is the problem of finding an interval extension of partially defined Boolean functions. We also study some other properties of interval functions.      

Robust Polynomials and Quantum Algorithms

We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We compare several different possible definitions. Our main results are: *For every n-bit Boolean function f there is an n-variate polynomial p of degree O(n) that robustly approximates it, in the sense that p(x) remains close to f(x) if we slightly vary each of the n inputs of the polynomial. *There is an O(n)-query quantum algorithm that robustly recovers n noisy input bits. Hence every n-bit function can be quantum computed with O(n) queries in the presence of noise. This contrasts with the classical model of Feige et al., where functions such as parity need Θ(n log n) queries. We give several extensions and applications of these results.     

Nondominated local coteries for resource allocation in grids and clouds

The resource allocation problem is a fundamental problem in Grid and Cloud computing environments. This paper focuses on constructing nondominated (ND) local coteries to solve the problem in a distributed way. Distributed algorithms using coteries usually incur low communication overheads and have high degrees of fault-tolerance, and ND coteries are candidates for the algorithms to achieve the highest degree of fault-tolerance. A new type of coteries, called p-coteries, is defined to aid the construction of local coteries. Theorems about the nondomination of p-coteries are then developed, and an operation, called pairwise-union (p-union), is proposed to help generate ND p-coteries, which in turn can be used to generate ND local coteries for solving the resource allocation problem.     

Obtaining coteries that optimize the availability of replicateddatabases

Techniques for implementing the coterie scheme and for obtaining optimal coteries for a system are presented. Central to the techniques is the notion of an acceptance set, which is an alternative representation of the information contained in a coterie. Using this concept, the coterie scheme can be implemented efficiently, and an optimal coterie for a system can be obtained more directly. The problem of determining an optimal acceptance set is formulated as a sparse zero-one linear programming problem. Hence, the optimization problem can be handled using the very rich class of existing techniques for solving such problems. Experimental results indicate that the optimization approach is feasible for up to eight nodes at least. The ways in which the scheme and the optimization approach can be used for systems that distinguish between read and write operations are indicated     

自对偶布尔函数的若干密码学性质研究

通过分析布尔函数的特征,建立了[n]元自对偶布尔函数和[n-1]元布尔函数之间的关系,根据此关系讨论了[n]元自对偶布尔函数的代数免疫度及其非线性度,得出自对偶布尔函数的非零次单项式个数为奇数,给出了[n]元[n-1]次自对偶布尔函数的个数和代数正规型表示的特征及其密码学性质,对其代数次数为[t]的单项式个数提出了猜想,对其中两种特殊情况进行了证明。     

布尔函数和伪布尔函数多项式表示的快速实现算法

布尔函数和伪布尔函数在不同的领域有着广泛的应用,利用多项式表示有利于刻划它们的一些特征属性。论文首先在已知输入都能得到输出的条件下给出了布尔函数多项式表示的快速实现算法,该算法仅用到模2加运算,运算次数少,具有简洁、易于编程实现、准确而快速的特点,而且该算法很易推广为伪布尔函数多项式表示的快速实现算法,只需把模2加运算换成实数加运算即可。接着通过比较说明了伪布尔函数多项式表示的快速实现算法,同时指出任何伪布尔函数都能通过多项式形式表示出来。最后通过实例进一步验证了算法的正确性。     

布尔矩阵乘的分布式异构并行优化

布尔多项式求解是当今密码代数分析中的关键步骤,F4算法是布尔多项式求解的高效算法。分析了Lachartre为F4矩阵专门设计的高斯消去算法,针对其中布尔矩阵乘这一耗时的计算步骤,设计并实现了分布式异构(CPU+MIC)并行算法。布尔矩阵相对于普通矩阵主要体现在矩阵元素取值区间不一样上,由于布尔矩阵元素(0,1)导致矩阵乘操作的特殊性,普通矩阵乘的优化方法不能很好地满足布尔矩阵乘的需求。分别从布尔矩阵的存储、OpenMP多线程组织、访存、任务划分和调度等方面进行了性能优化,实现了布尔矩阵乘的分布式异构并行算法。通过随机生成布尔矩阵测试,优化后的分布式异构并行程序相较于分布式同构并行程序达到了2.45的加速比,体现了良好的性能提升。     

Delay optimal coteries on regular symmetric networks

Coteries, introduced by Garcia-Molina and Barbara [Journal for the Association for Computing Machinery, 32 (4) (1985) 841], are an important and effective tool for enforcing mutual exclusion in distributed systems. Communication delay is an important performance measure for a coterie. Fu et al. [IEEE Transactions on Parallel and Distributed Systems, 8 (1) (1997) 59] emphasize that while calculating communication delay, the actual distances between different sites in a network must be taken into account and using this idea, obtain delay optimal coteries for trees, rings and hypercubes. Also, topology of an interconnection network plays an important role in the performance of a distributed system. For certain applications, it is desirable that the degree of each node in the interconnection network is the same. Constant Degree Four Cayley Graphs introduced by Vadapalli and Srimani [IEEE Transactions on Parallel and Distributed Systems 7(2) (1996) 26] provide an ideal topology for such applications. They are regular, have a logarithmic diameter and a node connectivity of four. In this paper, we prove that no coterie on an arbitrary network can have a delay of less than half the diameter of the network and use this result to obtain delay optimal coteries on regular symmetric networks with special reference to constant degree four Cayley interconnection-network.     

Representation of Boolean functions by polynomial forms

Two canonical polynomial representations of Boolean functions are introduced: polynomial perfect normal form and polynomial derivative positive form in the Boolean function g. We derive the necessary and sufficient conditions on the function g for the existence of such representations for any Boolean function.Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 175–179, May–June, 1992.     

改进的布尔公式学习算法

当前,布尔公式学习算法的研究大多数是理论上的模型建立和推导,很少有人考虑到布尔公式学习算法在实际应用中的效率改进。现在较成熟的布尔学习算法主要利用的是询问模型,而询问模型需要依赖外部的SMT 工具进行询问问题的回答。虽然,布尔公式学习算法可以在多项式次数的询问之后得到正确结果,但是,减少询问的次数可以减少使用 SMT 工具进行问题计算的次数,即减少问题计算的时间。主要针对布尔公式学习算法在实际系统中的应用问题,提出了利用单调理论中的最小赋值向量的方法,来减少布尔公式学习算法的询问次数,提高算法效率和适用性。     

Exact Transversal Hypergraphs and Application to Boolean μ-Functions

Call an hypergraph, that is a family of subsets (edges) from a finite vertex set, an exact transversal hypergraph iff each of its minimal transversals, i.e., minimal vertex subsets that intersect each edge, meets each edge in a singleton. We show that such hypergraphs are recognizable in polynomial time and that their minimal transversals as well as their maximal independent sets can be generated in lexicographic order with polynomial delay between subsequent outputs, which is impossible in the general case unless P= NP. The results obtained are applied to monotone Boolean μ-functions, that are Boolean functions defined by a monotone Boolean expression (that is, built with ∧, ∨ only) in which no variable occurs repeatedly. We also show that recognizing such functions from monotone Boolean expressions is co-NP-hard, thus complementing Mundici's result that this problem is in co-NP.     

Learning intersections and thresholds of halfspaces

We give the first polynomial time algorithm to learn any function of a constant number of halfspaces under the uniform distribution on the Boolean hypercube to within any constant error parameter. We also give the first quasipolynomial time algorithm for learning any Boolean function of a polylog number of polynomial-weight halfspaces under any distribution on the Boolean hypercube. As special cases of these results we obtain algorithms for learning intersections and thresholds of halfspaces. Our uniform distribution learning algorithms involve a novel non-geometric approach to learning halfspaces; we use Fourier techniques together with a careful analysis of the noise sensitivity of functions of halfspaces. Our algorithms for learning under any distribution use techniques from real approximation theory to construct low-degree polynomial threshold functions. Finally, we also observe that any function of a constant number of polynomial-weight halfspaces can be learned in polynomial time in the model of exact learning from membership and equivalence queries.     

NXOR- or XOR-based robust template decomposition for cellular neural networks implementing an arbitrary Boolean function via support vector classifiers

Robust template design for cellular neural networks (CNNs) implementing an arbitrary Boolean function is currently an active research area. If the given Boolean function is linearly separable, a single robust uncoupled CNN can be designed preferably as a maximal margin classifier to implement the Boolean function. On the other hand, if the linearly separable Boolean function has a small geometric margin or the Boolean function is not linearly separable, a popular approach is to find a sequence of robust uncoupled CNNs implementing the given Boolean function. In the past research works using this approach, the control template parameters and thresholds are usually restricted to assume only a given finite set of integers. In this study, we try to remove this unnecessary restriction. NXOR- or XOR-based decomposition algorithm utilizing the soft margin and maximal margin support vector classifiers is proposed to design a sequence of robust templates implementing an arbitrary Boolean function. Several illustrative examples are simulated to demonstrate the efficiency of the proposed method by comparing our results with those produced by other decomposition methods with restricted weights.