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     

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.     

传输子网选择:度数有界最大支撑子图逼近

研究了源于无线网状网络的度数有界最大支撑子图问题:给定连通图G=(V,E)和正整数d≥2,求G的一个最大支撑子图H,满足对V中每个顶点v,v在H中的度数dH(v)不超过d。这里,支撑子图指图G的一个连通而且包括G中所有顶点的子图。就输入图的边是否带权,分别设计了多项式时间近似算法。当输入图为无权图时,证明了近似算法的近似比为2;当输入图为赋权图时,证明了算法输出一个最大度数不超过d+1、权重不低于最优解权重1/(d+2)的支撑子图。算法输出的度数有界支撑子图可以用作无线网状网络的传输子网。     

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     

Structure fault tolerance of balanced hypercubes

The Journal of Supercomputing - Let H be a connected subgraph of a given graph G. The H-structure connectivity of G is the cardinality of a minimal set $${\mathcal {F}}$$ of subgraphs of G such...     

A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs

Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O(n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists.     

Generating and approximating nondominated coteries

A coterie, which is used to realize mutual exclusion in a distributed system is a family C of incomparable subsets such that every pair of subsets in C has at least one element in common. Associate with a family of subsets C a positive (i.e., monotone) Boolean function f_c such that f_c(x)=1 if the Boolean vector x is equal to or greater than the characteristic vector of some subset in C, and 0 otherwise. It is known that C is a coterie if and only if f_c is dual-minor, and is a nondominated (ND) coterie if and only if f_c is self-dual. We introduce an operator ρ, which transforms a positive self-dual function into another positive self-dual function, and the concept of almost-self-duality, which is a close approximation to self-duality and can be checked in polynomial time (the complexity of checking positive self-duality is currently unknown). After proving several interesting properties of them, we propose a simple algorithm to check whether a given positive function is self-dual or not. Although this is not a polynomial algorithm, it is practically efficient in most cases. Finally, we present an incrementally polynomial algorithm that generates all positive self-dual functions (ND coteries) by repeatedly applying p operations. Based on this algorithm, all ND coteries of up to seven variables are computed     

An efficient Dijkstra-like labeling method for computing shortest odd/even paths

We show how the problem of determining shortest paths of even or odd length between two specified vertices in a graph G = (V, E) can be reduced to the problem of finding a shortest alternating path with respect to a specific matching in a related graph H. This problem can be solved by a Dijkstra-like labeling procedure of complexity O(|V|²) respectively O(|E|log|V|). Interpreting this procedure appropriately the method can then be applied directly on the given graph G.     

A geometric approach for constructing coteries and k-coteries

Quorum-based mutual exclusion algorithms are resilient to node and communication line failures. Recently, some mutual exclusion algorithms successfully use logical structures to construct coteries with small quorums sizes. In this paper, we introduce a geometric approach on dealing with the logical structures and present some useful geometric properties for constructing coteries and k-coteries. Based on those geometric properties, a logical structure named three-sided graph is proposed to provide a new scheme for constructing coteries with small quorums: The smallest quorum size is O(√N) in a homogeneous system with N nodes and O(1) in a heterogeneous system. In addition, we also extend the three-sided graph to the O-sided graph for constructing k-coteries     

The Probabilistic Minimum Vertex-covering Problem

An instance of the probabilistic vertex-covering problem is a pair ( G =( V , E ),Pr) obtained by associating with each vertex υ _i ∈ V an 'occurrence' probability p _i . We consider a modification strategy Μ transforming a vertex cover C for G into a vertex cover C _I for the subgraph of G induced by a vertex-set I ⊆ V . The objective for the probabilistic vertex-covering is to determine a vertex cover of G minimizing the sum, over all subsets I ⊆ V , of the products: probability of I times C _I . In this paper, we study the complexity of optimally solving probabilistic vertex-covering.     

Disk Embeddings of Planar Graphs

Given a planar graph $G=(V,E)$ and a rooted forest ${\FF}=(V_{\FF}, A_{\FF})$ with leaf set $V$, we wish to decide whether $G$ has a plane embedding $\GG$ satisfying the following condition: There are $|V_{\FF}|-|V|$ pairwise noncrossing Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of ${\FF}$ such that for every nonleaf vertex $f$ of ${\FF}$, the interior of the curve $\JJ_f$ corresponding to $f$ contains all the leaf descendants of $f$ in ${\FF}$ but contains no other leaves of ${\FF}$. This problem arises from theoretical studies in geographic database systems. It is unknown whether this problem can be solved in polynomial time. This paper presents an almost linear-time algorithm for a nontrivial special case where the set of leaf descendants of each nonleaf vertex $f$ in ${\FF}$ induces a connected subgraph of $G$.     

Local 7-coloring for planar subgraphs of unit disk graphs

We study the problem of computing locally a coloring of an arbitrary planar subgraph of a unit disk graph. Each vertex knows its coordinates in the plane and can communicate directly with all its neighbors within unit distance. Using this setting, first a simple algorithm is given whereby each vertex can compute its color in a 9-coloring of the planar graph using only information on the subgraph located within at most 9 hops away from it in the original unit disk graph. A more complicated algorithm is then presented whereby each vertex can compute its color in a 7-coloring of the planar graph using only information on the subgraph located within a constant number (201, to be exact) of hops away from it.     

Super-connected and hyper-connected jump graphs

Let G be a connected graph. The graph G is said to be super-connected if for every minimum vertex cut S of G, G?S has isolated vertices. Moreover, it is said to be hyper-connected if for every minimum vertex cut S, G?S has exactly two components, one of which is an isolated vertex. In this note, we give a necessary and sufficient condition for a graph G whose jump graph J(G) (the complement of line graph of G) is, respectively, super-connected and hyper-connected.     

A 2-approximation NC algorithm for connected vertex cover and tree cover

The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to approximate as the vertex cover problem is. While several 2-approximation NC algorithms are known for vertex cover, whether unweighted or weighted, no parallel algorithm with guaranteed approximation is known for connected vertex cover. Moreover, converting the existing sequential 2-approximation algorithms for connected vertex cover to parallel ones results in RNC algorithms of rather high complexity at best.In this paper we present a 2-approximation NC (and RNC) algorithm for connected vertex cover (and tree cover). The NC algorithm runs in O(log²n) time using O(Δ²(m+n)/logn) processors on an EREW-PRAM, while the RNC algorithm runs in O(logn) expected time using O(m+n) processors on a CRCW-PRAM, when a given graph has n vertices and m edges with maximum vertex degree of Δ.     

强竞赛图的强连通性

D=(V,A)为一个有向图,其中,V为顶点集,A为弧集,A中的元素是有序对(u,v),称为弧。设u和v是有向图D的两个顶点,若从u到v存在一条有向路,则称顶点v是从u可达的,或称从u可达v。若有向图D中任何两个顶点是互相可达的,则称D为强连通图。若有向图T中任意两个顶点之间恰有一条弧,则称T为竞赛图。一个强连通的竞赛图T称为强竞赛图。论文研究顶点个数大于的强竞赛图T的性质,并利用该性质给出了Moon定理的另外一种证明。     

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     

最小权度的网络构建问题

网络构建问题是组合最优化中的经典问题．而连通性是网络设计问题中的一个核心问题。考虑这样一个最优化问题：给定无向图G=（V,E;W）,W：E→Q^＋是权重函数,G’=（V,E’）为G的一个子图．要寻找E的一个子集E”E．使得由E’∪E”所得的诱导子图是一个连通图,其目标是使得所有方案中权度最大者的权度值达到最小。经过对问题分析．对问题的特殊情况E’=Ф,设计了两个时间复杂度分别为O（n^2）和O（mn）的启发式算法。而E”≠Ф的情况也可以类似讨论．     

Error Compensation in Leaf Power Problems

The k-Leaf Power recognition problem is a particular case of graph power problems: For a given graph it asks whether there exists an unrooted tree—the k-leaf root—with leaves one-to-one labeled by the graph vertices and where the leaves have distance at most k iff their corresponding vertices in the graph are connected by an edge. Here we study "error correction" versions of k-Leaf Power recognition—that is, adding or deleting at most l edges to generate a graph that has a k-leaf root. We provide several NP-completeness results in this context, and we show that the NP-complete Closest 3-Leaf Power problem (the error correction version of 3-Leaf Power) is fixed-parameter tractable with respect to the number of edge modifications or vertex deletions in the given graph. Thus, we provide the seemingly first nontrivial positive algorithmic results in the field of error compensation for leaf power problems with k > 2. To this end, as a result of independent interest, we develop a forbidden subgraph characterization of graphs with 3-leaf roots.     

Decision tree complexity of graph properties with dimension at most 5

A graph property is a set of graphs such that if the set contains some graph G then it also contains each isomorphic copy of G(with the same vertex set).A graph propoerty P on n vertices is said to be elusive,if every decision tree algorithm recognizing P must examine all n(n-1)/2 paris of vertices in the worst case.Karp conjectured that every nontrivial monotone graph property is elusive,In this paper,this conjecture is proved for some cases,Especially,it is shown that if the abstract simplicial complex of a nontrivial monotone graph property P has dimension not exceeding 5, then P is elusive.