A novel constant degree and constant congestion DHT scheme for peer-to-peer networks

1 Introduction and related work In recent years, peer-to-peer computing has attracted significant attention from both industry field and academic field[1-3]. The core component of many proposed peer-to- peer systems is the distributed hash table (DHT) schemes[4,5] that use a hash table-like interface to publish and look up data objects. Many proposed DHT schemes[6-15] are based on some traditional interconnection to- pology: Chord[6], Tapestry[7,8], Pastry[9] are based on hypercube topolog…     

Almost Optimal Dynamic 2-3 Trees

This paper presents a principle to create Almost Optimal Dynamical 2-3 trees basedon the theory of Miller et al.,and gives a searching algorithm,an insertion algorithmand a deletion algorithm for these 2-3 trees.Experimental result given in this paperindicates that these 2-3 trees have very good performance at node-visit cost.We discussasymptotic property of the 2-3 trees as N→∞,and evaluate its approximate height,h=log_(2.45)(N+1),where N is the number of nodes of a 2-3 tree.Finally,this paper analysesthe time complexities of the algorithms,which are O(log_(2.45)(N+1)).     

The Hough Transform on a Reconfigurable Multi-Ring Network

A novel reconfigurable network referred to as the Reconfigurable Multi-Ring Network (RMRN) is described. The RMRN is shown to be a truly scalable network, in that each node in the network has a fixed degree of connectivity and the reconfiguration mechanism ensures a network diameter of O(log₂N) for an N-processor network. Algorithms for the 2-D mesh and the SIMD n-cube are shown to map very elegantly onto the RMRN. Basic message passing and reconfiguration primitives for the SIMD RMRN are designed which could be used as building blocks for more complex parallel algorithms. The RMRN is shown to be a viable architecture for image processing and computer vision problems via the parallel computation of the Hough transform. The parallel implementation of the Y-angle Hough transform of an N × N image is showed to have a asymptotic complexity of O(Y log₂Y + log₂N) on the SIMD RMRN with O(N²) processors. This compares favorably with the O(Y + log₂N) optimal algorithm for the same Hough transform on the MIMD n-cube with O(N²) processors.     

Routing Permutations on Hypercube Machines with Half-Duplex Links

Algorithms are presented for realizing permutations on a less restrictive hypercube model called the S-MIMD (synchronous MIMD), which allows at most one data transfer on a given communication link at a given time instant, and where data movements are not restricted to a single dimension at a given time. First, an optimal algorithm for bit-permute permutations is developed from a very simple realization of the shuffle on a 3-cube; this algorithm needs 2⌊n/2⌋ routing steps on an n-dimensional hypercube. The technique is then extended to an optimal algorithm for bit-permute-complement permutations, one that needs n routing steps. Also, algorithms are sketched for routing permutations in the classes Ω and Ω⁻¹ in 3⌈n/2⌉ routing steps, yielding an off-line algorithm for routing arbitrary permutations in 3n steps.     

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.     

Calculating the n-dimensional fast Fourier transform

The one-dimensional fast Fourier transform (FFT) is the most popular tool for calculating the multidimensional Fourier transform. As a rule, to estimate the n-dimensional FFT, a standard method of combining one-dimensional FFTs, the so-called “by rows and columns” algorithm, is used in the literature. For fast calculations, different researchers try to use parallel calculation tools, the most successful of which are searches for the algorithms related to the computing device architecture: cluster, video card, GPU, etc. [1, 2]. The possibility of paralleling another algorithm for FFT calculation, which is an n-dimensional analog of the Cooley-Tukey algorithm [3, 4], is studied in this paper. The focus is on studying the analog of the Cooley-Tukey algorithm because the number of operations applied to calculate the n-dimensional FFT is considerably less than in the conventional algorithm nN ⁿ log₂ N of addition operations and 1/2N ^{n + 1}log₂ N of multiplication operations of addition operations and $\frac{{2^n - 1}} {{2^n }}N^n \log _2 N$ of multiplication operations against: N ^{n + 1}log₂ N of addition operations and 1/2N ^{n + 1}log₂ N of in combining one-dimensional FFTs.     

Mapping two complete binary trees into the star graph with quick fault recovery

This paper proposes an approach for embedding two complete binary trees (CBT) into ann-dimensional star graph (S _n), and provides a fault-tolerant scheme for the trees. First, aCBT with height Σ _m=2 ⁿ ?logm? is embedded into theS _n with dilation 3. The height of theCBT is very close to ?Σ _m=2 ⁿ logm?, the height of the largest possibleCBT which can be embedded into theS _n. Shifting the firstCBT by generating function productg ₂ g ₃ g ₄ g ₃, anotherCBT with height Σ _m=2 ⁿ ?logm? can also be embedded into theS _n without conflicting with the first one. Moreover, if three-eights of nodes in the firstCBT and all nodes in the secondCBT are faulty, all of them can be recovered. Under the condition that the firstCBT with smaller height (?Σ _m=2 ⁿ logm? ? 1) is embedded, all the replacement nodes will be free. As a consequence, even in the case that all nodes in the two trees are faulty, they can be recovered in the smallest number of recovery steps and only with dilation 5.     

Multi-mesh of trees with its parallel algorithms

In recent years the multi-mesh network [Proceedings of the Ninth International Parallel Processing Symposium, Santa Barbara, CA, April 25–28, 1995, 17; IEEE Trans. on Comput. 68 (5) (1999) 536] has created a lot of interests among the researchers for its efficient topological properties. Several parallel algorithms for various trivial and nontrivial problems have been mapped on this network. However, because of its O(n) diameter, a large class of algorithms that involves frequent data broadcast in a row or in a column or between the diametrically opposite processors, requires O(n) time on an n×n multi-mesh. In search of faster algorithms, we introduce, in this paper, a new network topology, called multi-mesh of trees. This network is built around the multi-mesh network and the mesh of trees. As a result it can perform as efficiently as a multi-mesh network and also as efficiently as a mesh of trees. Several topological properties, including number of links, diameter, bisection width and decomposition are discussed. We present the parallel algorithms for finding sum of n⁴ elements and the n²-point Lagrange interpolation both in O(logn)¹ time. The solution of n²-degree polynomial equation, n²-point DFT computation and sorting of n² elements are all shown to run in O(logn) time too. The communication algorithms one-to-all, row broadcast and column broadcast are also described in O(logn) time. This can be compared with O(n) time algorithms on multi-mesh network for all these problems.     

Exact Solutions to Diameter and Routing Problems in PEC Networks

Recently, the diameter problem for packed exponential connections (PEC) networks was addressed by Cho-Chin Lin and V. K. Prasanna [Proc. Symposium on Parallel and Distributed Processing, 1992, pp. 368–375], who presented asymptotically tight bounds for the diameter and showed asymptotically optimal routing algorithms. In this paper exact, solutions to the diameter and routing problems of PEC networks are derived, thereby strengthening the asymptotic bounds of Lin and Prasanna. For anN= 2ⁿnode PEC network, with[formula]an integer, it is shown that the diameter is given by the simple expression[formula]An exact expression for the diameter of PEC networks for generalNis also derived. Efficient algorithms for shortest-path routing between nodes in a PEC network are then developed. These algorithms use at mostO(log²N) time for computing the lengths of minimal routes between nodes. Finally, a simple modification to obtain symmetric PEC networks is suggested.     

Acknowledged broadcasting in ad hoc radio networks

We consider ad hoc radio networks in which each node knows only its own identity but is unaware of the topology of the network, or of any bound on its size or diameter. Acknowledged broadcasting (AB) is a communication task consisting in transmitting a message from a distinguished source to all other nodes of the network and making this fact common knowledge among all nodes. To do this, the underlying directed graph must be strongly connected. Working in a model allowing all nodes to transmit spontaneously even before getting the source message, Chlebus et al. [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] proved that AB is impossible, if collision detection is not available, and gave an AB algorithm using collision detection that works in time O(nD) where n is the number of nodes and D is the eccentricity of the source. Uchida et al. [J. Uchida, W. Chen, K. Wada, Acknowledged broadcasting and gossiping in ad hoc radio networks, Theoret. Comput. Sci. 377 (2007) 43-54] showed an AB algorithm without collision detection working in time O(n4/3log10/3n) for all strongly connected networks of size at least 2. In particular, it follows that the impossibility result from [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] is really caused by the singleton network for which AB amounts to realize that the source is alone. We improve those two results by presenting two generic AB algorithms using a broadcasting algorithm without acknowledgement, as a procedure. For a large class of broadcasting algorithms the resulting AB algorithm has the same time complexity. Using the currently best known broadcasting algorithms, we obtain an AB algorithm with collision detection working in time O(min{nlog²D,nlognloglogn}), for arbitrary strongly connected networks, and an AB algorithm without collision detection working in time O(nlognloglogn) for all strongly connected networks of size n?2. Moreover, we show that in the model in which only nodes that already got the source message can transmit, AB is infeasible in a strong sense: for any AB algorithm there exists an infinite family of networks for which this algorithm is incorrect.     

Finding a longest nonnegative path in a constant degree tree

A longest nonnegative path in an edge-weighted tree is a path such that the sum of edge weights on it is nonnegative and the number of edges on it is as large as possible. In this paper we show that if a tree has a constant degree, then its longest nonnegative path can be found in O(nlogn) time, where n is the number of nodes. Previously known algorithms take O(nlog²n) time.     

Parallel Algorithms for Counting and Randomly Generating Integer Partitions

This paper presents parallel algorithms for determining the number of partitions of a given integerN, where the partitions may be subject to restrictions, such as being composed of distinct parts, of a given number of parts, and/or of parts belonging to a specified set. We present a series of adaptive algorithms suitable for varying numbers of processors. The fastest of these algorithms computes the number of partitions ofnwith largest part equal tok, for 1 ≤k≤n≤N, in timeO(log²(N)) usingO(N²/logN) processors. Parallel logarithmic time algorithms that generate partitions uniformly at random, using these quantities, are also presented.     

Maximum Matching in Regular and Almost Regular Graphs

We present an O(n ²logn)-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(rn ²logn) time if the difference between the maximum degree and the minimum degree is less than r. This running time is faster than applying the fastest known general matching algorithm that runs in $O(\sqrt{n}m)$ -time for graphs with m edges, whenever m=ω(rn ^1.5logn).     

An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function

The Lovász ?-function (Lovász in IEEE Trans. Inf. Theory, 25:1–7, 1979) of a graph G=(V,E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr(X) equals 1, and X _ij =0 whenever {i,j}∈E. This function appears as a subroutine for many algorithms for graph problems such as maximum independent set and maximum clique. We apply Arora and Kale’s primal-dual method for SDP to design an algorithm to approximate the ?-function within an additive error of δ>0, which runs in time $O(\frac{\vartheta ^{2} n^{2}}{\delta^{2}} \log n \cdot M_{e})$ , where ?=?(G) and M _e =O(n ³) is the time for a matrix exponentiation operation. It follows that for perfect graphs G, our primal-dual method computes ?(G) exactly in time O(? ² n ⁵logn). Moreover, our techniques generalize to the weighted Lovász ?-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1+?) in time O(? ^?2 n ⁵logn).     

The fastcube: a variation on hypercube topology with lower diameter

This paper presents a class of n-dimensional interconnection topologies with N=2ⁿ nodes which we refer to as n-fastcubes. The node degree of the n-fastcube is n and its diameter is ⌈(n+1)/2⌉, which is substantially smaller than that of the same size hypercube. Topological properties as well as several routing algorithms for fastcubes are developed. In addition, a new methodology for the design and analysis of fastcubes is employed. This methodology is based on modeling interconnection networks as finite state automata. The inputs to these particular automata are routing sequences. The routing and embedding algorithms developed in this paper produce routing sequences. The main characteristic of routing sequences is their node independence. A node independent routing sequence, p(H), produces a path between any pair of nodes with the Hamming distance of H. Thus, these sequences can be used, without modification, at any node to establish paths in a fastcube.     

Computing Unrestricted Synopses Under Maximum Error Bound

Constructing Haar wavelet synopses with guaranteed maximum error on data approximations has many real world applications. In this paper, we take a novel approach towards constructing unrestricted Haar wavelet synopses under maximum error metrics (L _∞). We first provide two linear time (logN)-approximation algorithms which have space complexities of O(logN) and O(N) respectively. These two algorithms have the advantage of being both simple in structure and naturally adaptable for stream data processing. Unlike traditional approaches for synopses construction that rely heavily on examining wavelet coefficients and their summations, the proposed methods are very compact and scalable, and sympathetic for online data processing. We then demonstrate that this technique can be extended to other findings such as Haar⁺ tree. Extensive experiments indicate that these techniques are highly practical. The proposed algorithms achieve a very attractive tradeoff between efficiency and effectiveness, surpassing contemporary (logN)-approximation algorithms in compressing qualities.     

Geometric applications of a matrix-searching algorithm

LetA be a matrix with real entries and letj(i) be the index of the leftmost column containing the maximum value in rowi ofA.A is said to bemonotone ifi ₁ >i ₂ implies thatj(i ₁) ≥J(i ₂).A istotally monotone if all of its submatrices are monotone. We show that finding the maximum entry in each row of an arbitraryn xm monotone matrix requires Θ(m logn) time, whereas if the matrix is totally monotone the time is Θ(m) whenm≥n and is Θ(m(1 + log(n/m))) whenm<n. The problem of finding the maximum value within each row of a totally monotone matrix arises in several geometric algorithms such as the all-farthest-neighbors problem for the vertices of a convex polygon. Previously only the property of monotonicity, not total monotonicity, had been used within these algorithms. We use the Θ(m) bound on finding the maxima of wide totally monotone matrices to speed up these algorithms by a factor of logn.     

Computing the Map of Geometric Minimal Cuts

In this paper we consider the following problem of computing a map of geometric minimal cuts (called MGMC problem): Given a graph G=(V,E) and a planar rectilinear embedding of a subgraph H=(V _H ,E _H ) of G, compute the map of geometric minimal cuts induced by axis-aligned rectangles in the embedding plane. The MGMC problem is motivated by the critical area extraction problem in VLSI designs and finds applications in several other fields. In this paper, we propose a novel approach based on a mix of geometric and graph algorithm techniques for the MGMC problem. Our approach first shows that unlike the classic min-cut problem on graphs, the number of all rectilinear geometric minimal cuts is bounded by a low polynomial, O(n ³). Our algorithm for identifying geometric minimal cuts runs in O(n ³logn(loglogn)³) expected time which can be reduced to O(nlogn(loglogn)³) when the maximum size of the cut is bounded by a constant, where n=|V _H |. Once geometric minimal cuts are identified we show that the problem can be reduced to computing the L _∞ Hausdorff Voronoi diagram of axis aligned rectangles. We present the first output-sensitive algorithm to compute this diagram which runs in O((N+K)log² NloglogN) time and O(Nlog² N) space, where N is the number of rectangles and K is the complexity of the Hausdorff Voronoi diagram. Our approach settles several open problems regarding the MGMC problem.     

Self-stabilizing minimum degree spanning tree within one from the optimal degree

We propose a self-stabilizing algorithm for constructing a Minimum Degree Spanning Tree (MDST) in undirected networks. Starting from an arbitrary state, our algorithm is guaranteed to converge to a legitimate state describing a spanning tree whose maximum node degree is at most Δ^∗+1, where Δ^∗ is the minimum possible maximum degree of a spanning tree of the network.To the best of our knowledge, our algorithm is the first self-stabilizing solution for the construction of a minimum degree spanning tree in undirected graphs. The algorithm uses only local communications (nodes interact only with the neighbors at one hop distance). Moreover, the algorithm is designed to work in any asynchronous message passing network with reliable FIFO channels. Additionally, we use a fine grained atomicity model (i.e., the send/receive atomicity). The time complexity of our solution is O(mn²logn) where m is the number of edges and n is the number of nodes. The memory complexity is O(δlogn) in the send-receive atomicity model (δ is the maximal degree of the network).     

A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.