Compact separator decompositions in dynamic trees and applications to labeling schemes

This paper presents an efficient scheme maintaining a separator decomposition representation in dynamic trees using asymptotically optimal labels. In order to maintain the short labels, the scheme uses relatively low message complexity. In particular, if the initial dynamic tree contains only the root, then the scheme incurs an O(log⁴ n) amortized message complexity per topology change, where n is the current number of vertices in the tree. As a separator decomposition is a fundamental decomposition of trees used extensively as a component in many static graph algorithms, our dynamic scheme for separator decomposition may be used for constructing dynamic versions to these algorithms. The paper then shows how to use our dynamic separator decomposition to construct efficient labeling schemes on dynamic trees, using the same message complexity as our dynamic separator scheme. Specifically, we construct efficient routing schemes on dynamic trees, for both the designer and the adversary port models, which maintain optimal labels, up to a multiplicative factor of O(log log n). In addition, it is shown how to use our dynamic separator decomposition scheme to construct dynamic labeling schemes supporting the ancestry and NCA relations using asymptotically optimal labels, as well as to extend a known result on dynamic distance labeling schemes. Supported in part at the Technion by an Aly Kaufman fellowship. Supported in part by a grant from the Israel Science Foundation.     

Labeling schemes for weighted dynamic trees

A Distance labeling scheme is a type of localized network representation in which short labels are assigned to the vertices, allowing one to infer the distance between any two vertices directly from their labels, without using any additional information sources. As most applications for network representations in general, and distance labeling schemes in particular, concern large and dynamically changing networks, it is of interest to focus on distributed dynamic labeling schemes. The paper considers dynamic weighted trees where the vertices of the trees are fixed but the (positive integral) weights of the edges may change. The two models considered are the edge-dynamic model, where from time to time some edge changes its weight by a fixed quanta, and the increasing-dynamic model in which edge weights can only grow. The paper presents distributed approximate distance labeling schemes for the two dynamic models, which are efficient in terms of the required label size and communication complexity involved in updating the labels following the weight changes.     

A note on exact distance labeling

We show that the vertices of an edge-weighted undirected graph can be labeled with labels of size O(n) such that the exact distance between any two vertices can be inferred from their labels alone in time. This improves the previous best exact distance labeling scheme that also requires O(n)-sized labels but time to compute the distance. Our scheme is almost optimal as exact distance labeling is known to require labels of length Ω(n).     

A note on models for graph representations

This paper is intended more to ask questions than give answers. Specifically, we consider models for labeling schemes, and discuss issues regarding the number of labels consulted vs. the sizes of the labels.     

Distributed verification of minimum spanning trees

The problem of verifying a Minimum Spanning Tree (MST) was introduced by Tarjan in a sequential setting. Given a graph and a tree that spans it, the algorithm is required to check whether this tree is an MST. This paper investigates the problem in the distributed setting, where the input is given in a distributed manner, i.e., every node “knows” which of its own emanating edges belong to the tree. Informally, the distributed MST verification problem is the following. Label the vertices of the graph in such a way that for every node, given (its own state and label and) the labels of its neighbors only, the node can detect whether these edges are indeed its MST edges. In this paper, we present such a verification scheme with a maximum label size of O(log n log W), where n is the number of nodes and W is the largest weight of an edge. We also give a matching lower bound of Ω(log n log W) (as long as W > (log n)^1+ε for some fixed ε > 0). Both our bounds improve previously known bounds for the problem. For the related problem of tree sensitivity also presented by Tarjan, our method yields rather efficient schemes for both the distributed and the sequential settings. A preliminary version of this work was presented in ACM PODC 2006. A. Korman was supported in part at the Technion by an Aly Kaufman fellowship. S. Kutten was supported in part by a grant from the Israeli Ministry for Science and Technology.     

Protocols useful on the Internet from distributed signature schemes

Distributed cryptography deals with scenarios where a cryptographic operation is performed by a collective of persons. In a distributed signature scheme, a group of players share some secret information in such a way that only authorized subsets of players can compute valid signatures. We propose methods to construct some computationally secure protocols from distributed signature schemes, namely, we construct metering schemes from distributed noninteractive signature schemes. We also show that distributed deterministic signature schemes can be used to design distributed key distribution schemes. In particular, we construct the first metering and distributed key distribution schemes based on the RSA primitive.     

Universal routing schemes

Summary.  In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all n-node networks. In [31], Peleg and Upfal showed that one cannot implement a universal routing scheme with less than a total of Ω(n ^1+1/(2s+4)) memory bits for any given stretch factor s≧1. We improve this bound for stretch factors s, 1≦s<2, by proving that any near-shortest path universal routing scheme uses a total of Ω(n ²) memory bits in the worst-case. This result is obtained by counting the minimum number of routing functions necessary to route on all n-node networks. Moreover, and more fundamentally, we give a tight bound of Θ(n log n) bits for the local minimum memory requirement of universal routing scheme of stretch factors s, 1≦s<2. More precisely, for any fixed constant ɛ, 0<ɛ<1, there exists a n-node network G on which at least Ω(n ^ɛ) routers require Θ(n log n) bits each to code any routing function on G of stretch factor <2. This means that, whatever you choose the routing scheme, there exists a network on which one cannot compress locally the routing information better than routing tables do. Received: August 1995 / Accepted: August 1996     

Efficient multicast schemes for 3-D Networks-on-Chip

3-D Networks-on-Chip (NoCs) have been proposed as a potent solution to address both the interconnection and design complexity problems facing future System-on-Chip (SoC) designs. In this paper, two topology-aware multicast routing algorithms, Multicasting XYZ (MXYZ) and Alternative XYZ (AL + XYZ) algorithms in supporting of 3-D NoC are proposed. In essence, MXYZ is a simple dimension order multicast routing algorithm that targets 3-D NoC systems built upon regular topologies. To support multicast routing in irregular regions, AL + XYZ can be applied, where an alternative output channel is sought to forward/replicate the packets whenever the output channel determined by MXYZ is not available. To evaluate the performance of MXYZ and AL + XYZ, extensive experiments have been conducted by comparing MXYZ and AL + XYZ against a path-based multicast routing algorithm and an irregular region oriented multiple unicast routing algorithm, respectively. The experimental results confirm that the proposed MXYZ and AL + XYZ schemes, respectively, have lower latency and power consumption than the other two routing algorithms, meriting the two proposed algorithms to be more suitable for supporting multicasting in 3-D NoC systems. In addition, the hardware implementation cost of AL + XYZ is shown to be quite modest.     

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.     

Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors

Traditional ant colony optimization (ACO) algorithms have difficulty in addressing dynamic optimization problems (DOPs). This is because once the algorithm converges to a solution and a dynamic change occurs, it is difficult for the population to adapt to a new environment since high levels of pheromone will be generated to a single trail and force the ants to follow it even after a dynamic change. A good solution to address this problem is to increase the diversity via transferring knowledge from previous environments to the pheromone trails using immigrants schemes. In this paper, an ACO framework for dynamic environments is proposed where different immigrants schemes, including random immigrants, elitism-based immigrants, and memory-based immigrants, are integrated into ACO algorithms for solving DOPs. From this framework, three ACO algorithms, where immigrant ants are generated using the aforementioned immigrants schemes and replace existing ants in the current population, are proposed and investigated. Moreover, two novel types of dynamic travelling salesman problems (DTSPs) with traffic factors, i.e., under random and cyclic dynamic environments, are proposed for the experimental study. The experimental results based on different DTSP test cases show that each proposed algorithm performs well on different environmental cases and that the proposed algorithms outperform several other peer ACO algorithms.     

Dynamic detection of subgraphs in computer networks

Most distributed algorithms for computer networks are designed to work with arbitrary graph structures. Most networks, however, can usually be decomposed into subgraphs with a specific structure. Detecting and exploiting these subgraphs can considerably reduce the storage and communication cost of the algorithm. In this paper we propose a distributed algorithm for detecting and exploiting tree subgraphs. In a network with fixed topology, the algorithm is optimal in terms of communication complexity. The algorithm also dynamically adapts to changes in network topology caused by link failure and recovery. The dynamic operation of the algorithm is incremental as only nodes that may be affected by the change reinitiate the algorithm. Another important property of our algorithm is that it requires no node identities or sequence numbers. We examine how this idea can be extended to other subgraph structures.     

Evolving dynamic Bayesian networks with Multi-objective genetic algorithms

A dynamic Bayesian network (DBN) is a probabilistic network that models interdependent entities that change over time. Given example sequences of multivariate data, we use a genetic algorithm to synthesize a network structure that models the causal relationships that explain the sequence. We use a multi-objective evaluation strategy with a genetic algorithm. The multi-objective criteria are a network's probabilistic score and structural complexity score. Our use of Pareto ranking is ideal for this application, because it naturally balances the effect of the likelihood and structural simplicity terms used in the BIC network evaluation heuristic. We use a basic structural scoring formula, which tries to keep the number of links in the network approximately equivalent to the number of variables. We also use a simple representation that favors sparsely connected networks similar in structure to those modeling biological phenomenon. Our experiments show promising results when evolving networks ranging from 10 to 30 variables, using a maximal connectivity of between 3 and 4 parents per node. The results from the multi-objective GA were superior to those obtained with a single objective GA. Brian J. Ross is a professor of computer science at Brock University, where he has worked since 1992. He obtained his BCSc at the University of Manitoba, Canada, in 1984, his M.Sc. at the University of British Columbia, Canada, in 1988, and his Ph.D. at the University of Edinburgh, Scotland, in 1992. His research interests include evolutionary computation, language induction, concurrency, and logic programming. He is also interested in computer applications in the fine arts. Eduardo Zuviria received a BS degree in Computer Science from Brock University in 2004 and a MS degree in Computer Science from Queen's University in 2006 where he held jobs as teacher and research assistant. Currently, he is attending a Ph.D. program at the University of Montreal. He holds a diploma in electronics from a technical college and has worked for eight years in the computer industry as a software developer and systems administrator. He has received several scholarships including the Ontario Graduate Scholarship, Queen's Graduate Scholarship and a NSERC- USRA scholarship.     

A repartitioning hypergraph model for dynamic load balancing

In parallel adaptive applications, the computational structure of the applications changes over time, leading to load imbalances even though the initial load distributions were balanced. To restore balance and to keep communication volume low in further iterations of the applications, dynamic load balancing (repartitioning) of the changed computational structure is required. Repartitioning differs from static load balancing (partitioning) due to the additional requirement of minimizing migration cost to move data from an existing partition to a new partition. In this paper, we present a novel repartitioning hypergraph model for dynamic load balancing that accounts for both communication volume in the application and migration cost to move data, in order to minimize the overall cost. The use of a hypergraph-based model allows us to accurately model communication costs rather than approximate them with graph-based models. We show that the new model can be realized using hypergraph partitioning with fixed vertices and describe our parallel multilevel implementation within the Zoltan load balancing toolkit. To the best of our knowledge, this is the first implementation for dynamic load balancing based on hypergraph partitioning. To demonstrate the effectiveness of our approach, we conducted experiments on a Linux cluster with 1024 processors. The results show that, in terms of reducing total cost, our new model compares favorably to the graph-based dynamic load balancing approaches, and multilevel approaches improve the repartitioning quality significantly.     

A new routing algorithm for multirate rearrangeable Clos networks

In this paper, we study the problem of finding routing algorithms on the multirate rearrangeable Clos networks which use as few number of middle-stage switches as possible. We propose a new routing algorithm called the “grouping algorithm”. This is a simple algorithm which uses fewer middle-stage switches than all known strategies, given that the number of input-stage switches and output-stage switches are relatively small compared to the size of input and output switches. In particular, the grouping algorithm implies that m = 2n+(n−1)/2^k is a sufficient number of middle-stage switches for the symmetric three-stage Clos network C(n,m,r) to be multirate rearrangeable, where k is any positive integer and rn/(2^k−1).     

Modeling and performance analysis of ad hoc broadcasting schemes

Broadcasting is a technique widely used for distributing control packets in ad hoc networks. The traditional flooding scheme has been proven to unnecessarily consume network capacity and may lead to severe packet collisions in high-density networks. New schemes have been proposed for alleviating this so-called broadcast storm problem and their efficiencies are usually analyzed and compared by ns-2 simulations. However, little work has been done on mathematical modeling and rigorous analysis. In this paper, we focus on two popular ad hoc broadcasting schemes and provide their detailed analysis in one-dimensional and two-dimensional ideal networks. The statistical results obtained have revealed new relationships between network parameters and the performance metrics. These results are useful for optimally setting network parameters in designing protocols. It is also expected that the analytical methods developed will lay a solid foundation for the development of mathematical models for other ad hoc broadcast and multicast schemes.     

An efficient distributed algorithm for generating and updating multicast trees

As group applications are becoming widespread, efficient network utilization becomes a growing concern. Multicast transmission represents a necessary lower network service for the wide diffusion of new multimedia network applications. Multicast transmission may use network resources more efficiently than multiple point-to-point messages; however, creating optimal multicast trees (Steiner Tree Problem in networks) is prohibitively expensive. This paper proposes a distributed algorithm for the heuristic solution of the Steiner Tree Problem, allowing the construction of effective distribution trees using a coordination protocol among the network nodes. Furthermore, we propose a novel distributed technique for dynamically updating the multicast tree. The approach proposed has been implemented and extensively tested both in simulation, and on experimental networks. Performance evaluation indicates that the distributed algorithm performs as well as the centralized version, providing good levels of convergence time and communication complexity.     

Reconfigurable distributed storage for dynamic networks

This paper presents a new algorithm for implementing a reconfigurable distributed shared memory in an asynchronous dynamic network. The algorithm guarantees atomic consistency (linearizability) in all executions in the presence of arbitrary crash failures of the processing nodes, message delays, and message loss. The algorithm incorporates a classic quorum-based algorithm for read/write operations, and an optimized consensus protocol, based on Fast Paxos for reconfiguration, and achieves the design goals of: (i) allowing read and write operations to complete rapidly and (ii) providing long-term fault-tolerance through reconfiguration, a process that evolves the quorum configurations used by the read and write operations. The resulting algorithm tolerates dynamism. We formally prove our algorithm to be correct, we present its performance and compare it to existing reconfigurable memories, and we evaluate experimentally the cost of its reconfiguration mechanism.