双环Petersen图互联网络及路由算法

Petersen图由于具有短直径和正则性等特性,因此在并行与分布式计算中具有良好的性能.基于双环结构,构造了一个双环Petersen图互联网络DLCPG(k).同时,分别设计了DLCPG(k)上的单播、广播和容错路由算法.证明了DLCPG(k)不但具有良好的可扩展性、短的网络直径和简单的拓扑结构等特性,而且对于10k个节点组成的互联网络,DLCPG(k)还具有比二维Torus以及RP(k)互联网络更小的直径和更优越的可分组性.另外,还证明了其上的单播、广播路由算法的通信效率与RP(k)上的单播和广播路由算法的通信效率相比均有明显的提高.仿真实验表明,新的容错路由算法也具有良好的容错性能.     

Robustness of star graph network under link failure

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.     

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.     

Consensus seeking in a network of discrete-time linear agents with communication noises

This paper studies the mean square consensus of discrete-time linear time-invariant multi-agent systems with communication noises. A distributed consensus protocol, which is composed of the agent's own state feedback and the relative states between the agent and its neighbours, is proposed. A time-varying consensus gain a[k] is applied to attenuate the effect of noises which inherits in the inaccurate measurement of relative states with neighbours. A polynomial, namely ‘parameter polynomial’, is constructed. And its coefficients are the parameters in the feedback gain vector of the proposed protocol. It turns out that the parameter polynomial plays an important role in guaranteeing the consensus of linear multi-agent systems. By the proposed protocol, necessary and sufficient conditions for mean square consensus are presented under different topology conditions: (1) if the communication topology graph has a spanning tree and every node in the graph has at least one parent node, then the mean square consensus can be achieved if and only if ∑^∞_{k = 0}a[k] = ∞, ∑^∞_{k = 0}a²[k] < ∞ and all roots of the parameter polynomial are in the unit circle; (2) if the communication topology graph has a spanning tree and there exits one node without any parent node (the leader–follower case), then the mean square consensus can be achieved if and only if ∑^∞_{k = 0}a[k] = ∞, lim_{k → ∞}a[k] = 0 and all roots of the parameter polynomial are in the unit circle; (3) if the communication topology graph does not have a spanning tree, then the mean square consensus can never be achieved. Finally, one simulation example on the multiple aircrafts system is provided to validate the theoretical analysis.     

Analysis of k-Neigh topology control protocol for mobile wireless networks

k-Neigh is a basic neighbor-based topology control protocol based on the construction of k-neighbor graph as logical communication graph. Several topological aspects of the constructed topology which are crucial to the performance of the protocol are not yet analytically investigated. Moreover, the problem of determining the maximum “Hello” interval preserving the connectivity with high probability has not been extensively addressed yet. Since execution of the protocol is a resource consuming task, this problem is of great importance on the performance of the protocol in sense of power consumption and topology control overhead. In this paper, first, several topological properties of the constructed topology for a static network, e.g. average logical degree and average final transmission range, are investigated analytically. Then, temporal properties of the dynamic topology in presence of mobility are studied based on two phenomena, one concerning a connectivity phase transition with time which is reported for the first time and the other one concerning the average degree of the logical communication graph at the time of starting the phase transition defined as disconnection degree. Using the obtained results one may tune the protocol in sense of “Hello” interval, maximum transmission power, or number of neighbors (k). Although the present work considers k-Neigh protocol, many interesting quantities are derived which may have application beyond the specific problem considered in this paper, e.g. the cdf, mean, and variance of the distance to the ith neighbor.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^1.5k ?^?1.5k (α(n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, α is the inverse Ackermann function, and ? ≤ 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ?) times the weight of a minimum weight complete matching.     

An Optimal Approach to Collaborative Target Tracking with Performance Guarantees

In this paper, we present a discrete-time optimization framework for target tracking with multi-agent systems. The “target tracking” problem is formulated as a generic semidefinite program (SDP) that when paired with an appropriate objective yields an optimal robot configuration over a given time step. The framework affords impressive performance guarantees to include full target coverage (i.e. each target is tracked by at least a single team member) as well as maintenance of network connectivity across the formation. Key to this work is the result from spectral graph theory that states the second-smallest eigenvalue—λ ₂—of a weighted graph’s Laplacian (i.e. its inter-connectivity matrix) is a measure of connectivity for the associated graph. Our approach allows us to articulate agent-target coverage and inter-agent communication constraints as linear-matrix inequalities (LMIs). Additionally, we present two key extensions to the framework by considering alternate tracking problem formulations. The first allows us to guarantee k-coverage of targets, where each target is tracked by k or more agents. In the second, we consider a relaxed formulation for the case when network connectivity constraints are superfluous. The problem is modeled as a second-order cone program (SOCP) that can be solved significantly more efficiently than its SDP counterpart—making it suitable for large-scale teams (e.g. 100’s of nodes in real-time). Methods for enforcing inter-agent proximity constraints for collision avoidance are also presented as well as simulation results for multi-agent systems tracking mobile targets in both ?² and ?³.     

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     

Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)?(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.     

A Distributed Critical Section Protocol for General Topology

We present a new critical section protocol designed for distributed systems with general topologies, where the physical layer is implemented as point-to-point physical links in contrast to shared access physical media. The protocol operates correctly for any topology; however, its time performance is topology dependent. The distributed system can be modeled by a graph G(V, E), where V denotes the set of processors and E is the set of bidirectional communication links. We use n to denote |V|; D(G) is the diameter of G, T(G) is the spanning tree of G, and D(T) is the diameter of T(G). An important measure of the performance of the protocol is the amount of traffic caused by its operation. Let message-hop be the amount of traffic generated by a single message between two adjacent nodes. The proposed protocol generates network traffic of only 3*(n − 1) ∈ Θ(n) [message-hops] per critical section access for any topology which is less than other existing fully distributed protocols. A lower bound on traffic for a single critical section access for a fully distributed protocol is shown to be 2*(n − 1) [message-hops]. Some previously published algorithms generate Θ(n²) [message-hops] of network traffic for some topologies. Another important measure of the performance of the protocol is the cs-access time. It is the time required to access the critical section in the absence of other requests; and it depends on the topology. The high cs-access time performance is achieved by taking a novel approach of distributing the communication and parts of computation functions of the protocol and exploiting the physical topology. For a constant size message, the time to traverse an edge, including the message communication software processing in the source and destination nodes, is called message-hop-time and it is denoted by t_h. For a general graph G (with spanning tree T) the new protocol has the cs-access time performance Θ(max(D(T), max(deg (v_i)))) [t_h], where deg(v_i) is computed in T. For the graphs where G has D(G) ∈ Θ(log₂n) and max(deg(v_i)) in G is O(log₂n), the cs-access time performance is Θ(log₂n) [t_h]. For the class of graphs where G has D(G) ∈ Θ(n), the cs-access time performance is Θ(n) [t_h]. For the Star graphs the cs-access time performance is Θ(n) [t_h]. The worst case time performance occurs for linear and Star graphs. The proposed protocol has a better network traffic performance and (depending on the topology) a better or equal cs-access time performance than previously published fully distributed protocols. The protocol keeps the clock bounded in well-designed systems using a distributed predictive "clock squashing" mechanism.     

Performance metrics in the average consensus problem: A tutorial

The average consensus algorithm is a distributed procedure which allows a network of agents to agree on the average of a set of initial values. The computation occurs through local exchange of information only, namely the information exchange takes place only between agents which are neighbors with respect to a graph representing the system communication architecture. Several performance metrics have been proposed for the evaluation of this algorithm. Particularly interesting and challenging is to relate them to the communication topology. Different performance metrics may yield different answers in comparing alternative communication topologies. In this paper, we present a few performance metrics and we show how these metrics are related to the communication topology. In particular, when available, we present bounds which permit to relate performance and topology for general graphs, for graphs with symmetries, called d-dimensional tori, and for geometric graphs.     

Pancyclicity and bipancyclicity of conditional faulty folded hypercubes

A graph is said to be pancyclic if it contains cycles of every length from its girth to its order inclusive; and a bipartite graph is said to be bipancyclic if it contains cycles of every even length from its girth to its order. The pancyclicity or the bipancyclicity of a given network is an important factor in determining whether the network’s topology can simulate rings of various lengths. An n-dimensional folded hypercube FQ_n is an attractive variant of an n-dimensional hypercube Q_n that is obtained by establishing some extra edges between the vertices of Q_n. FQ_n for any odd n is known to be bipartite. In this paper, we explore the pancyclicity and bipancyclicity of FQ_n. For any FQ_n (n ? 2) with at most 2n − 3 faulty edges, where each vertex is incident to at least two fault-free edges, we prove that there exists a fault-free cycle of every even length from 4 to 2ⁿ; and when n ? 2 is even, we prove there also exists a fault-free cycle of every odd length from n + 1 to 2ⁿ − 1. The result is optimal with respect to the number of faulty edges tolerated.     

Folded Petersen cube networks: new competitors for the hypercubes

We introduce and analyze a new interconnection topology, called the k-dimensional folded Petersen (FP_k) network, which is constructed by iteratively applying the Cartesian product operation on the well-known Petersen graph. Since the number of nodes in FP_k is restricted to a power of ten, for better scalability we propose a generalization, the folded Petersen cube network FPQ_n,k =Q_n×FP_k, which is a product of the n-dimensional binary hypercube (Q_n) and FP_k. The FPQ_n,k topology provides regularity, node- and edge-symmetry, optimal connectivity (and therefore maximal fault-tolerance), logarithmic diameter, modularity, and permits simple self-routing and broadcasting algorithms. With the same node-degree and connectivity, FPQ _n,k has smaller diameter and accommodates more nodes than Q _n+3k, and its packing density is higher compared to several other product networks. This paper also emphasizes the versatility of the folded Petersen cube networks as a multicomputer interconnection topology by providing embeddings of many computationally important structures such as rings, multi-dimensional meshes, hypercubes, complete binary trees, tree machines, meshes of trees, and pyramids. The dilation and edge-congestion of all such embeddings are at most two     

Delay-optimal quorum consensus for distributed systems

Given a set of nodes S, a coterie is a set of pairwise intersecting subsets of S. Each element in a coterie is called a quorum. Mutual exclusion in a distributed system can be achieved if each request is required to gel consensus from a quorum of nodes. This technique of quorum consensus is also used for replicated distributed database systems, and bicoteries and wr-coteries have been defined to capture the requirements of read and write operations in user transactions. The author is interested in finding coteries, bicoteries, and wr-coteries with optimal communication delay. The protocols take into account the network topology. They design delay-optimal quorum consensus protocols for network topologies of trees, rings, and clustered networks     

Graph embeddings and simplicial maps

An undirected graph is viewed as a simplicial complex. The notion of a graph embedding of a guest graph in a host graph is generalized to the realm of simplicial maps. Dilation is redefined in this more general setting. Lower bounds on dilation for various guest and host graphs are considered. Of particular interest are graphs that have been proposed as communication networks for parallel architectures. Bhattet al. provide a lower bound on dilation for embedding a planar guest graph in a butterfly host graph. Here, this lower bound is extended in two directions. First, a lower bound that applies to arbitrary guest graphs is derived, using tools from algebraic topology. Second, this lower bound is shown to apply to arbitrary host graphs through a new graph-theoretic measure, called bidecomposability. Bounds on the bidecomposability of the butterfly graph and of thek-dimensional torus are determined. As corollaries to the main lower-bound theorem, lower bounds are derived for embedding arbitrary planar graphs, genusg graphs, andk-dimensional meshes in a butterfly host graph.     

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×???×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box?(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a $\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1}An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×⋅⋅⋅×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box (G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a ?1+\frac1clogn?^d-1\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1} approximation ratio for any constant c≥1 when d≥2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard.     

A kind of conditional fault tolerance of alternating group graphs

A vertex subset F is a k-restricted vertex-cut of a connected graph G if G−F is disconnected and every vertex in G−F has at least k good neighbors in G−F. The cardinality of the minimum k-restricted vertex-cut of G is the k-restricted connectivity of G, denoted by κk(G). This parameter measures a kind of conditional fault tolerance of networks. In this paper, we show that for the n-dimensional alternating group graph AGn, κ²(AG₄)=4 and κ²(AGn)=6n−18 for n?5.     

Distributed algorithms for finding and maintaining a k-tree core in a dynamic network

A k-core C_k of a tree T is subtree with exactly k leaves for k?n_l, where n_l the number of leaves in T, and minimizes the sum of the distances of all nodes from C_k. In this paper first we propose a distributed algorithm for constructing a rooted spanning tree of a dynamic graph such that root of the tree is located near the center of the graph. Then we provide a distributed algorithm for finding k-core of that spanning tree. The spanning tree is constructed in two stages. In the first stage, a forest of trees is generated. In the next stage these trees are connected to form a single rooted tree. An interesting aspect of the first stage of proposed spanning algorithm is that it implicitly constructs the (convex) hull of those nodes which are not already included in the spanning forest. The process is repeated till all non root nodes of the graph have chosen a unique parent. We implemented the algorithms for finding spanning tree and its k-core. A core can be quite useful for routing messages in a dynamic network consisting of a set of mobile devices.     

A (4n − 9)/3 diagnosis algorithm on n-dimensional cube network

As a generalization of the precise and pessimistic diagnosis strategies of system-level diagnosis of multicomputers, the t/k diagnosis strategy can significantly improve the self-diagnosing capability of a system at the expense of no more than k fault-free processors (nodes) being mistakenly diagnosed as faulty. In the case k ? 2, to our knowledge, there is no known t/k diagnosis algorithm for general diagnosable system or for any specific system. Hypercube is a popular topology for interconnecting processors of multicomputers. It is known that an n-dimensional cube is (4n − 9)/3-diagnosable. This paper addresses the (4n − 9)/3 diagnosis of n-dimensional cube. By exploring the relationship between a largest connected component of the 0-test subgraph of a faulty hypercube and the distribution of the faulty nodes over the network, the fault diagnosis of an n-dimensional cube can be reduced to those of two constituent (n − 1)-dimensional cubes. On this basis, a diagnosis algorithm is presented. Given that there are no more than 4n − 9 faulty nodes, this algorithm can isolate all faulty nodes to within a set in which at most three nodes are fault-free. The proposed algorithm can operate in O(N log₂ N) time, where N = 2ⁿ is the total number of nodes of the hypercube. The work of this paper provides insight into developing efficient t/k diagnosis algorithms for larger k value and for other types of interconnection networks.     

On scalability of proximity-aware peer-to-peer streaming

P2P (peer-to-peer) technology has proved itself an efficient and cost-effective solution to support large-scale multimedia streaming. Different from traditional P2P applications, the quality of P2P streaming is strictly determined by performance metrics such as streaming delay. To meet these requirements, previous studies resorted to intuitions and heuristics to construct peer selection solutions incorporating topology and proximity concerns. However, the impact of proximity-aware methodology and delay tolerance of peers on the scalability of P2P system remains an unanswered question. In this paper, we study this problem via an analytical approach. To address the challenge of incorporating Internet topology into P2P streaming analysis, we construct a H-sphere network model which maps the network topology from the space of discrete graph to the continuous geometric domain, meanwhile capturing the power-law property of Internet. Based on this model, we analyze a series of peer selection methods by evaluating their performance via key scalability metrics. Our analytical observations are further verified via simulation on Internet topologies.