Size bounds for superconcentrators

We prove that any N-superconcentrator of indegree two has at least 4N - o(N) nodes. From this lower bounds of 4N - o(N) follow on the number of additions required to compute the Discrete Fourier Transform of prime order and cyclic convolution. Using small examples we illustrate how small superconcentrators can suggest fast algorithms for instances of these problems.For superconcentrators with no degree restrictions we prove a lower bound of 5N - o(N) edges. Also, we give a recursive construction with 3Nlog₂N edges that improves on the best bounds previously known for values of N up to several thousand.     

Parallel algorithms for tree traversals

Three commonly used traversal methods for binary trees (forsets) are pre-order, in-order and post-order. It is well known that sequential algorithms for these traversals takes order O(N) time where N is the total number of nodes. This paper establishes a one-to-one correspondence between the set of nodes that possess right sibling and the set of leaf nodes for any forest. For the case of pre-order traversal, this result is shown to provide an alternate characterization that leads to a simple and elegant parallel algorithm of time complexity O(log N) with or without read-conflicts on an N processor SIMD shared memory model, where N is the total number of nodes in a forest.     

Bounds on the Diameter of One-Dimensional Pec Networks

The diameter of a packed exponential connections (PEC) network on N nodes is shown to be Θ([formula] × [formula]).⁴ A routing algorithm which can route between any two nodes in O([formula] × [formula]) steps is shown. A methodology to find a set of links to be used by a shortest path from node 1 to node N − 1 is derived. We also show that semigroup operations can be performed in O([formula] × [formula]) parallel steps.     

On the area of hypercube layouts

This paper precisely analyzes the wire density and required area in standard layout styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N² nodes in the plane, in an N×N grid arrangement, uses ⌊2N/3⌋+1 horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any cut position and a full characterization of all places where the wire density is maximized (which does not occur at the bisection).     

A fast fault-identification algorithm for bijective connection graphs using the PMC model

Diagnosis of reliability is an important topic for interconnection networks. Under the classical PMC model, Dahura and Masson [5] proposed a polynomial time algorithm with time complexity O(N^2.5) to identify all faulty nodes in an N-node network. This paper addresses the fault diagnosis of so called bijective connection (BC) graphs including hypercubes, twisted cubes, locally twisted cubes, crossed cubes, and Möbius cubes. Utilizing a helpful structure proposed by Hsu and Tan [20] that was called the extending star by Lin et al. [24], and noting the existence of a structured Hamiltonian path within any BC graph, we present a fast diagnostic algorithm to identify all faulty nodes in O(N) time, where N = 2ⁿ, n ? 4, stands for the total number of nodes in the n-dimensional BC graph. As a result, this algorithm is significantly superior to Dahura–Masson’s algorithm when applied to BC graphs.     

On the Smallest Size of an Almost Complete Subset of a Conic in PG(2, <Emphasis Type="Italic">q</Emphasis>) and Extendability of Reed–Solomon Codes

Abstract—In the projective plane PG(2, q), a subset S of a conic C is said to be almost complete if it can be extended to a larger arc in PG(2, q) only by the points of C \ S and by the nucleus of C when q is even. We obtain new upper bounds on the smallest size t(q) of an almost complete subset of a conic, in particular,

$$t(q) < \sqrt {q(3lnq + lnlnq + ln3)} + \sqrt {\frac{q}{{3\ln q}}} + 4 \sim \sqrt {3q\ln q} ,t(q) < 1.835\sqrt {q\ln q.} $$

The new bounds are used to extend the set of pairs (N, q) for which it is proved that every normal rational curve in the projective space PG(N, q) is a complete (q+1)-arc, or equivalently, that no [q+1,N+1, q?N+1]_q generalized doubly-extended Reed–Solomon code can be extended to a [q + 2,N + 1, q ? N + 2]_q maximum distance separable code.

     

Some results on tries with adaptive branching

We study a modification of digital trees (or tries) with adaptive multi-digit branching. Such tries can dynamically adjust degrees of their nodes by choosing the number of digits to be processed per lookup. While we do not specify any particular method for selecting the degrees of nodes, we assume that such selection can be accomplished by examining the number of strings remaining in each sub-tree, and/or estimating parameters of the input distribution. We call this class of digital trees adaptive multi-digit tries (or AMD-tries) and provide a preliminary analysis of their expected behavior in a memoryless model. We establish the following results: (1) there exist AMD-tries attaining a constant expected time of a successful search; (2) there exist AMD-tries consuming a linear (in the number of strings inserted) amount of space; (3) both constant search time and linear space usage can be attained if the (memoryless) source is symmetric. We accompany our analysis with a brief survey of several known types of adaptive trie structures, and show how our analysis extends (and/or complements) previous results.     

Succinct and I/O Efficient Data Structures for Traversal in Trees

We present two results for path traversal in trees, where the traversal is performed in an asymptotically optimal number of I/Os and the tree structure is represented succinctly. Our first result is for bottom-up traversal that starts with a node in a tree on N nodes and traverses a path to the root. We show how a tree T on N nodes with q-bit keys, where q=O(lg?N), can be blocked in a succinct fashion such that a bottom-up traversal requires O(K/B+1) I/Os using only $(2+q)N + q \cdot[ \frac{2 \tau N (q + 2 \lg B)}{w} + o(N)] + \frac{8\tau N \lg B}{w}$ bits to store T for any constant 0<τ<1, where K is the path length and w is the word size. This data structure is succinct because the above space cost is at most (2+q)N+q?(ηN+o(N)) bits for any arbitrarily selected constant, η, such that 0<η<1. When storing keys with tree nodes is not required, we can represent T in $2N + \frac{\epsilon N\lg B}{w} + o(N)$ bits, where ? is an arbitrarily selected constant such that 0<?<1, while providing the same support for queries. Our second result is for top-down traversal in binary trees. We store the tree in (3+q)N+o(N) bits, while top-down traversal can still be performed in an asymptotically optimal number of I/Os.     

A fast pessimistic diagnosis algorithm for generalized hypercube multicomputer systems

The reliability of processors is an important issue for designing a massively parallel processing system for which fault-tolerant computing is crucial. In order to achieve high system reliability and availability, a faulty processor (node) when found should be replaced by a fault-free processor. Within a multiprocessor system, the technique of identifying faulty nodes by constructing tests on the nodes and interpreting the test outcomes is known as system-level diagnosis. The topological structure of a multicomputer system can be modeled by a graph of which the vertices and edges correspond to nodes and links of the system, respectively. This work presents a system-level diagnosis algorithm for a generalized hypercube which is an attractive variance of a hypercube. The proposed algorithm is based on the PMC model and can isolate all faulty nodes to within a set which contains at most one fault-free node. If the total number of nodes to be diagnosed in a generalized hypercube is N, the proposed algorithm can run in O(Nlog?N) time, and being superior to Yang??s algorithm proposed in 2004, it can diagnose not only a hypercube but also a generalized hypercube.     

Knowledge versus search: A quantitative analysis using A1

This paper analyzes the average number of nodes expanded by $\text{A1}$ as a function of the accuracy of its heuristic estimates, by treating the errors h1 - h as random variables whose distribution may vary over the nodes in the graph. The search model consists of an m-ary tree with unit branch costs and a unique goal state situated at a distance N from the root.The main result states that if the typical error grows like φ(h1) then the mean complexity of $\text{A1}$ grows approximately like G(N)exp[cφ(N)], where c is a positive constant and G(N) is O(N²). Thus, a necessary and sufficient condition for maintaining polynomial search complexity is that $\text{A1}$ be guided by heuristics with logarithmic precision, e.g. φ(N) = (log N)^k. $\text{A1}$ is shown to make much greater use of its heuristic knowledge than a backtracking procedure would under similar conditions.     

Parallel tree contraction and prefix computations on a large family of interconnection topologies

The derivation of the prefixes of a given sequence (prefix computation) and the fast reduction of a tree to a single node (tree contraction) are two useful primitives for many applications on parallel computers. It is well known that certain special cases of the two problems can be solved efficiently on the hypercube. Here we extend this result to a large family of parallel computers. The family of parallel computers are based on a novel interconnection scheme called thegeneralized Fibonacci cube that encompasses both the hypercube and the second-order Fibonacci cube in [8]. Specifically, we show that thek-th order Fibonacci tree of sizeN can be reduced to a single node inO(logN) steps on ak-th order Fibonacci cube withN nodes (processors). Assuming thatO(logN) data items are on each of theN processors, we also show that the prefixes can be computed inO(logN) steps on thek-th order Fibonacci cube.     

Multiple Templates Access of Trees in Parallel Memory Systems

We study the problem of mapping theNnodes of a data structure onMmemory modules so that they can be accessed in parallel bytemplates, i.e., distinct sets of nodes. In literature several algorithms are available for arrays (accessed by rows, columns, diagonals, and subarrays) and trees (accessed by subtrees, root-to-leaf paths, levels, etc.). Although some mapping algorithms for arrays allow conflict-free access to several templates at once (for example rows and columns), no mapping algorithm is known for efficiently accessing subtree, path and level templates in complete binary trees. In our paper, we first prove that any mapping algorithm that is conflict-free for tree/level template has Ω(M/logM) conflicts when access is done according to path template and vice versa. Therefore, no mapping algorithm can be found that is conflict-free on both path and tree (or path and level) templates. Our main result is an algorithm for mapping complete binary trees withN= 2^M− 1 nodes onMmemory modules in such a way that:

• &#x02022;the number of conflicts for accessing an-node subtree,adjacent nodes in the same level, orconsecutive nodes of a root-to-leaf path is(),
• &#x02022;the load (i.e., the ratio between the maximum and minimum number of data items mapped on each module) is 1 + o(1),
• &#x02022;the time complexity for retrieving the module where a given data item is stored is(1), if a preprocessing phase of space and time complexity(log) is executed, or(log log), if no preprocessing is allowed.

The algorithm can be easily generalized to complete binary trees of any size.     

Optical clustering

This paper presents a definition of ‘optical clusters’ which is derived from the concept of optical resolution. The clustering problem (induced by this definition) is transformed such that the application of well known Computational Geometry methods yields efficient solutions. One result (which can be extended to different classes of objects and metrices) is the following: Given a setS ofN disjoint line segments inE ².

1. The optical clusters with respect to a given separation parameterr∈R can be computed in timeO(Nlog² N).
2. Given an interval [a, b] for the numberm(S, r) of optical clusters which we want to compute, then timeO(N log² N)[O(Nlog² N+CN)] suffices to compute the interval [R(b),R(a)]={r∈R/m(S,r)∈[a,b]} [allC optical clusterings withR(b)≦ r≦R(a)].

     

On the performance of multicomputer interconnection networks

Several researchers have analysed the performance of k-ary n-cubes taking into account channel bandwidth constraints imposed by implementation technology, namely the constant wiring density and pin-out constraints for VLSI and multiple-chip technology respectively. For instance, Dally [IEEE Trans. Comput. 39(6) (1990) 775], Abraham [Issues in the architecture of direct interconnection networks schemes for multiprocessors, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1992], and Agrawal [IEEE Trans. Parallel Distributed Syst. 2(4) (1991) 398] have shown that low-dimensional k-ary n-cubes (known as tori) outperform their high-dimensional counterparts (known as hypercubes) under the constant wiring density constraint. However, Abraham and Agrawal have arrived at an opposite conclusion when they considered the constant pin-out constraint. Most of these analyses have assumed deterministic routing, where a message always uses the same network path between a given pair of nodes. More recent multicomputers have incorporated adaptive routing to improve performance. This paper re-examines the relative performance merits of the torus and hypercube in the context of adaptive routing. Our analysis reveals that the torus manages to exploit its wider channels under light traffic. As traffic increases, however, the hypercube can provide better performance than the torus. Our conclusion under the constant wiring density constraint is different from that of the works mentioned above because adaptive routing enables the hypercube to exploit its richer connectivity to reduce message blocking.     

Oracle-dependent properties of the lattice of NP sets

We consider under the assumption P ≠ NP questions concerning the structure of the lattice of NP sets together with the sublattice P. We show that two questions which are slightly more complex than the known splitting properties of this lattice cannot be settled by arguments which relativize. The two questions which we consider are whether every infinite NP set contains an infinite P subset and whether there exists an NP-simple set. We construct several oracles, all of which make P ≠ NP, and which in addition make the above-mentioned statements either true or false. In particular we give a positive answer to the question, raised by Bennett and Gill (1981), whether an oracle B exists making P^B ≠ NP^B and such that every infinite set in NP^B has an infinite subset in P^B. The constructions of the oracles are finite injury priority arguments.     

Parallel Load Balancing for Problems with Good Bisectors

Parallel load balancing is studied for problems with certain bisection properties. A class of problems has α-bisectors if every problem p of weight w(p) in the class can be subdivided into two subproblems whose weight (load) is at least an α-fraction of the original problem. A problem p is to be split into N subproblems such that the maximum weight among them is as close to w(p)/N as possible. It was previously known that good load balancing can be achieved for such classes of problems using Algorithm HF, a sequential algorithm that repeatedly bisects the subproblem with maximum weight. Several parallel variants of Algorithm HF are introduced and analyzed with respect to worst-case load imbalance, running-time, and communication overhead. For fixed α, all variants have running-time O(log N) and provide constant upper bounds on the worst-case load imbalance. Results of simulation experiments regarding the load balance achieved in the average case are presented.     

TR-clustering: Alleviating the impact of false clustering on P2P overlay networks

Designing topologically-aware overlays is a recurrent subject in peer-to-peer research. Although there exists a plethora of approaches, Internet coordinate systems such as GNP (which attempt to predict the pair-wise O(N²) latencies between N nodes using only O(N) measurements) have become the most attractive approach to make the overlay connectivity structures congruent with the underlying IP-level network topology. With appropriate input, coordinate systems allow complex distributed problems to be solved geometrically, including multicast, server selection, etc. For these applications, and presumably others like that, exact topological information is not required and it is sufficient to use informative hints about the relative positions of Internet clients. Clustering operation, which attempts to partition a set of objects into several subsets that are distinguishable under some criterion of similarity, could significantly ease these operations. However, when the main objective is clustering nodes, Internet coordinate systems present strong limitations to identify the right clusters, a problem known as false clustering.In this work, the authors answer a fundamental question that has been obscured in proximity techniques so far: how often false clustering happens in reality and how much this affects the overall performance of an overlay. To that effect, the authors present a novel approach called TR-Clustering to cluster nodes in overlay networks based on their physical positions on the Internet. To be specific, TR-Clustering uses the Internet routers with high vertex betweenness centrality to cluster participating nodes. Informally, the betweenness centrality of a router is defined as the fraction of shortest paths between all pairs of nodes running through it. Simulation results illustrate that TR-Clustering is superior to existing techniques, with less than a 5% of falsely clustered peers (of course, relative to the datasets utilized in their evaluation).     

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.     

Scalable percolation search on complex networks

We introduce a scalable searching protocol for locating and retrieving content in random networks with heavy-tailed and in particular power-law (PL) degree distributions. The proposed algorithm is capable of finding any content in the network with probability one   in time O(logN)$\mathrm{O}(\log N)$, with a total traffic that provably scales sub-linearly with the network size, N. Unlike other proposed solutions, there is no need to assume that the network has multiple copies of contents; the protocol finds all contents reliably, even if every node in the network starts with a unique content. The scaling behavior of the size of the giant connected component of a random graph with heavy-tailed degree distributions under bond percolation is at the heart of our results. The percolation search algorithm can be directly applied to make unstructured peer-to-peer (P2P) networks, such as Gnutella, Limewire and other file-sharing systems (which naturally display heavy-tailed degree distributions and approximate scale-free network structures), scalable. For example, simulations of the protocol on the limewire crawl number 5 network [Ripeanu et al., Mapping the Gnutella network: properties of large-scale peer-to-peer systems and implications for system design, IEEE Internet Comput. J. 6 (1) (2002)], consisting of over 65,000 links and 10,000 nodes, shows that even for this snapshot network, the traffic can be reduced by a factor of at least 100, and yet achieve a hit-rate greater than 90%.     

Mutually Unbiased Bases and the Complementarity Polytope

A complete set of N + 1 mutually unbiased bases (MUBs) forms a convex polytope in the N² − 1 dimensional space of N × N Hermitian matrices of unit trace. As a geometrical object such a polytope exists for all values of N, while it is unknown whether it can be made to lie within the body of density matrices unless N = p^k, where p is prime. We investigate the polytope in order to see if some values of N are geometrically singled out. One such feature is found: It is possible to select N² facets in such a way that their centers form a regular simplex if and only if there exists an affine plane of order N. Affine planes of order N are known to exist if N = p^k; perhaps they do not exist otherwise. However, the link to the existence of MUBs — if any — remains to be found.