Self-stabilizing and silent distributed algorithms for token distribution in rooted tree networks are given. Initially, each process of a graph holds at most ℓ tokens. Our goal is to distribute the tokens uniformly in the whole network so that every process holds exactly k tokens. In the initial configuration, the total number of tokens in the network may not be nk where n is the number of processes in the network. The root process is given the ability to create a new token or remove a token from the network. We aim to minimize the convergence time, the number of token moves, and the space complexity. First, a self-stabilizing token distribution algorithm that converges within O(nℓ) asynchronous rounds and needs Θ(nhϵ) redundant (or unnecessary) token moves is given, where ϵ=min(k,ℓ−k) and h is the height of the tree network. Next, two novel mechanisms to reduce the number of redundant token moves are presented. One reduces the number of redundant token moves to O(nh) without any additional costs while the other reduces the number of redundant token moves to O(n), but increases the convergence time to O(nhℓ). All given algorithms have constant memory at each process and each link register.

In the population protocol model [Angluin et al. 2006], it is impossible to design a self-stabilizing leader election protocol without any knowledge of the exact number of nodes in the system. The notion of loose-stabilization, which relaxes the closure requirement of self -stabilization, was introduced in 2009 to circumvent this impossibility. The notion can be described as follows: a loosely-stabilizing protocol guarantees that, starting from any initial configuration, a system reaches a safe configuration eventually, and after that, the system maintains its specification (e.g., the unique leader) not forever, but for a sufficiently long time. The previous work of the authors presented a loosely-stabilizing protocol that solves the leader election on complete graphs using only a given upper bound N on the number of nodes n in the system, instead of the exact value of n. In this paper, we propose two loosely-stabilizing protocols that solve leader election for arbitrary graphs. One is a deterministic protocol that uses the unique identifiers of nodes while the other is a probabilistic protocol that works on anonymous networks. Given an upper bound N on the number of nodes, both protocols maintain a unique leader for Ω(Ne2N) expected steps (holding time) after entering a safe configuration. The first algorithm enters a safe configuration within O(mN log n) expected steps (convergence time) while the second one does this within O(mN2log N) expected steps, where m is the number of edges in the graph. Both protocols require only O(log N) bits for each node's memory. A novel concept, called the same speed timer is introduced, by which all nodes of the system can count down their timers at the same speed. This concept allows to achieve fast convergence time of both algorithms. To design the second protocol, we design a self-stabilizing two-hop coloring protocol, which is interesting in its own right. This protocol uses only O(log N) memory space per node. We establish a lower bound. Any loosely-stabilizing leader election protocol with expected exponential holding time requires Ω(mN) expected convergence time. This lower bound shows a near-optimality of the first algorithm.

Self-stabilizing and silent distributed algorithms for token distribution in rooted tree networks are given. Initially, each process of a graph holds at most l tokens. Our goal is to distribute the tokens in the whole network so that every process holds exactly k tokens. In the initial configuration, the total number of tokens in the network may not be equal to nk where n is the number of processes in the network. The root process is given the ability to create a new token or remove a token from the network. We aim to minimize the convergence time, the number of token moves, and the space complexity. A self-stabilizing token distribution algorithm that converges within O(n l) asynchronous rounds and needs Theta(nh epsilon) redundant (or unnecessary) token moves is given, where epsilon = min(k,l-k) and h is the height of the tree network. Two novel ideas to reduce the number of redundant token moves are presented. One reduces the number of redundant token moves to O(nh) without any additional costs while the other reduces the number of redundant token moves to O(n), but increases the convergence time to O(nh l). All algorithms given have constant memory at each process and each link register.

A loosely-stabilizing leader election protocol with polylogarithmic convergence time in the population protocol model is presented in this paper. In the population protocol model, which is a common abstract model of mobile sensor networks, it is known to be impossible to design a self-stabilizing leader election protocol. Thus, in our prior work, we introduced the concept of loose-stabilization, which is weaker than self-stabilization but has similar advantage as self-stabilization in practice. Following this work, several loosely-stabilizing leader election protocols are presented. The loosely-stabilizing leader election guarantees that, starting from an arbitrary configuration, the system reaches a safe configuration with a single leader within a relatively short time, and keeps the unique leader for an sufficiently long time thereafter. The convergence times of all the existing loosely-stabilizing protocols, i.e., the expected time to reach a safe configuration, are polynomial in n where n is the number of nodes (while the holding times to keep the unique leader are exponential in n). In this paper, a loosely-stabilizing protocol with polylogarithmic convergence time is presented. Its holding time is not exponential, but arbitrarily large polynomial in n.

We study (deterministic) leader election in unidirectional rings of homonym processes that have no a priori knowledge on the number of processes. In this context, we show that there is no algorithm that solves process-terminating leader election for the class of asymmetric labeled rings. In particular, there is no process-terminating leader election algorithm in rings in which at least one label is unique. However, we show that process-terminating leader election is possible for the subclass of asymmetric rings, where multiplicity is bounded. We confirm this positive results by proposing two algorithms, which achieve the classical trade-off between time and space.

A novel concept of the same speed timer is presented, and is applied in the population protocol (PP) model to improve the convergence time of existing loosely-stabilizing leader election protocols. Loosely-stabilizing leader election guarantees that, starting from any configuration, the system reaches a safe configuration within a short time (convergence), and after that, the system keeps the unique leader for a long time (closure). Two loosely-stabilizing leader election protocols for arbitrary graphs exist in the literature; one uses identifiers of nodes and the other uses random numbers to elect a unique leader. Both protocols guarantee that the expected convergence time is polynomial and the expected holding time (the time the leader is kept) is exponential. In this paper, convergence time of these protocols is dramatically improved by the same speed timer without impairing the exponential holding time. Specifically, a fast deterministic loosely-stabilizing leader election protocol that uses identifiers of nodes and a fast randomized looselystabilizing leader election protocol are given. The expected convergence time and expected holding time of the former protocol are O(mN log N) and Ω(Ne2N), respectively, where m is the number of edges in the graph and N is a given upper bound on the number of nodes n. The expected convergence time and expected holding time of the latter protocol are O(mN2log n) and Ω(Ne2N), respectively. A self-stabilizing two-hop coloring protocol that uses only O(log n) memory space of each agent is given as a tool of the latter protocol. A lower bound is also given: any loosely-stabilizing leader election protocol with expected exponential holding time requires Ω(mN) expected convergence time.

We give a silent self-stabilizing protocol for computing a maximum matching in an anonymous network with a tree topology. The round complexity of our protocol is O(diam), where diam is the diameter of the network, and the step complexity is O(n*diam), where n is the number of processes in the network. The working space complexity is O(1) per process, although the output necessarily takes O(log(delta)) space per process, where delta is the degree of that process. To implement parent pointers in constant space, regardless of degree, we use the cyclic Abelian group Z_7.

The problem of exploring a discrete environment by identical oblivious asynchronous agents (or robots) devoid of direct means of communication has been well investigated so far. The (terminating) exploration requires that starting from a configuration where no two agents occupy the same node, every node needs to be visited by at least one agent, with the additional constraint that all agents eventually stop moving. Agents have sensors that allow them to see their environment and move accordingly. The previous works on this problem assume agents having an unlimited visibility, that is, they can sense the agents on every node of the ring, whatever the ring size. In this paper, we address deterministic exploration in an anonymous, unoriented ring using oblivious, and myopic agents. By myopic, we mean that their visibility is limited in terms of sensing distance. We consider the strongest possible myopia that is, an agent can only sense agents located at its own and at its immediate neighboring nodes. Our contribution is threefold. We first prove that within such settings, no deterministic exploration is possible in the semi-synchronous model. The result is also valid for the (fully) asynchronous model and holds for any k 6. Finally, we provide optimal (in terms of number of agents) deterministic algorithms in the fully synchronous model for both cases 3 6.

In this paper, we propose a silent self-stabilizing asynchronous distributed algorithm for constructing a kclustering of any connected network with unique IDs. Our algorithm stabilizes in O(n) rounds, using O(log n) space per process, where n is the number of processes. In the general case, our algorithm constructs O(n/k) k-clusters. If the network is a Unit Disk Graph (UDG), then our algorithm is 7.2552k+O(1)competitive, that is, the number of k-clusters constructed by the algorithm is at most 7.2552k + O(1) times the minimum possible number of k-clusters in any k-clustering of the same network. More generally, if the network is an Approximate Disk Graph (ADG) with approximation ratio λ, then our algorithm is 7.2552λ2k + O(λ)-competitive. Our solution is based on the self-stabilizing construction of a data structure called the MIS Tree, a spanning tree of the network whose processes at even levels form a maximal independent set of the network. The MIS tree construction is the time bottleneck of our k-clustering algorithm, as it takes Θ(n) rounds in the worst case, while the rest of the algorithm takes O(D) rounds, where V is the diameter of the network. We would like to improve that time to be O(D), but we show that our distributed MIS tree construction is a P-complete problem.

A silent self-stabilizing asynchronous distributed algorithm is given for constructing a k-dominating set, and hence a k-clustering, of a connected network of processes with unique IDs and no designated leader. The algorithm is comparison-based, takes O(k) time and uses O(k log n) space per process, where n is the size of the network. It is known that finding a minimum k-dominating set is 𝒩𝒫-hard. A lower bound is given, showing that any comparison-based algorithm for the k-clustering problem that produces clusters of average size more than 2 in the worst case takes Ω(diam) time, where diam is the diameter of the network.

In this paper, we address the problem of k-out-of-lscr exclusion, a generalization of the mutual exclusion problem, in which there are lscr units of a shared resource, and any process can request up to k units (1 les k les lscr). We propose the first deterministic self-stabilizing distributed k-out-of-lscr exclusion protocol in message-passing systems for asynchronous oriented tree networks which assumes bounded local memory for each process.

Given an arbitrary network G of processes with unique IDs and no designated leader, and given a k-dominating set I C G, we propose a silent self-stabilizing distributed algorithm that computes a subset D of I which is a minimal k-dominating set of G. Using D as the set of cluster-heads, a partition of G into clusters, each of radius k, follows. The algorithm is comparison-based, requires O(log n) space per process, converges in O(n) rounds and O(n2) steps, where n is the size of the network, and works under an unfair scheduler.

There exist several general techniques in the literature for speeding up naive implementations of dynamic programming. Two of the best known are the Knuth-Yao quadrangle inequality speedup and the SMAWK algorithm for finding the row-minima of totally monotone matrices. Although both of these techniques use a quadrangle inequality and seem similar, they are actually quite different and have been used differently in the literature. In this article we show that the Knuth-Yao technique is actually a direct consequence of total monotonicity. As well as providing new derivations of the Knuth-Yao result, this also permits to solve the Knuth-Yao problem directly using the SMAWK algorithm. Another consequence of this approach is a method for solving online versions of problems with the Knuth-Yao property. The online algorithms given here are asymptotically as fast as the best previously known static ones. For example, the Knuth-Yao technique speeds up the standard dynamic program for finding the optimal binary search tree of n elements from Θ( n 3 ) down to O ( n 2 ), and the results in this article allow construction of an optimal binary search tree in an online fashion (adding a node to the left or the right of the current nodes at each step) in O ( n ) time per step.

We present two space and time efficient asynchronous distributed self-stabilizing algorithms. The first sorts an oriented chain network and the second heapifies a rooted tree network. The time complexity of both solutions is linear - in terms of the nodes (for the chain) and height (for the tree). The chain sorting algorithm uses O(m) bits per process where m represents the number of bits required to store any value in the network. The heapify algorithm needs O(m ldr D) bits per process where D is the degree of the tree.

We present a parallel algorithm for the Huffman coding problem. We reduce the Huffman coding problem to the concave least weight subsequence (CLWS) problem and give a parallel algorithm that solves the latter problem in $O(\sqrt n \log n)$ time with n processors on a concurrent read exclusive write parameter random-access machine (CREW PRAM). This leads to the first sublinear-time $o(n^2 )$-total-work parallel algorithm for Huffman coding. This reduction of the Huffman coding problem to the CLWS problem also yields an alternative $O(n\log n)$-time (or linear-time, for a sorted input sequence) algorithm for Huffman coding.

In this paper, an $O(nL\log n)$-time algorithm is presented for construction of an optimal alphabetic binary tree with height restricted to L. This algorithm is an alphabetic version of the Package Merge algorithm, and yields an $O(nL\log n)$-time algorithm for the alphabetic Huffman coding problem. The Alphabetic Package Merge algorithm is quite simple to describe, but appears hard to prove correct. Garey [SIAM J Comput., 3 (1974), pp. 101–110] gives an $O(n^3 \log n)$-time algorithm for the height-limited alphabetic binary tree problem. Itai [SIAM J. Comput., 5 (1976), pp. 9–18] and Wessner [Inform. Process. Lett., 4 (1976), pp. 90–94] independently reduce this time to $O(n^2 L)$ for the alphabetic problem. In [SIAM J. Comput., 16 (1987), pp. 1115–1123], a rather complex $O(n^{{3 / 2}} L\log ^{{1 / 2}} n)$ -time “hybrid” algorithm is given for length-limited Huffman coding. The Package Merge algorithm, discussed in this paper, first appeared in [Tech. Report, 88-01, ICS Dept. Univ. of California, Irvine, CA], but without proof of correctness.

A parallel algorithm is given which constructs an optimal alphabetic tree in 0(log3 n) time with n2 log n processors.The construction is basically a paral.lelization of the Garsia-Wachs version [5] of the Hu-tucker algorithm [8].The best previous NC algorithm for the problem uses n6/ logo(l) n processors.[15] Our method is an extension of techniques used first in [3] and later used in [13] for the Huffman coding problem, which can be viewed as the alphabetic tree problem for the special case of a monotone weight sequence.In this paper, we extend to the cue of certain "almost monotone" sequences, which we call "sorted regular valleys.'The processing of such subsequences depends on a quadrangle inequality, while the total number of global iterations depends on a kind of tree contraction.Altogether we can view our algorithmic approach as (quadrangle inegualitg + tree contraction).An optimal alphabetic tree is a special case of an optimal binary search tree where all the weights are in the leaves.Thus, the result gives a partial answer to the open problem posed in [3]: is there an NC algorithm which can find an optimal binary search tree and which U*%S 7?6-t p9%s.7.3.2iTafvr Svme G > o? " This research was supported

The authors define a new, sliced layout architecture for compilation of arbitrary schematics (netlists) into layout for CMOS technology. This sliced architecture uses over-the-cell routing on the second metal layer. The authors define three different architectures with simple folding, interleaved folding, and unrestricted folding and give algorithms for optimizing the layout area for several variants of the selected architecture. A proof demonstrating that the architecture with interleaved folding is as good as the architecture with unrestricted folding with respect to area minimization of the total layout is given. The authors also present results of random benchmarks as well as several real benchmarks.>

Article Parallel construction of trees with optimal weighted path length Share on Authors: Lawrence L. Larmore Department of Computer Science, University of California, Riverside, CA Department of Computer Science, University of California, Riverside, CAView Profile , Teresa M. Przytycka Department of Computer Science, University of California, Riverside, CA and Instytut Informatyki, Uniwersytet Warszawski Department of Computer Science, University of California, Riverside, CA and Instytut Informatyki, Uniwersytet WarszawskiView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 71–80https://doi.org/10.1145/113379.113386Published:01 June 1991 10citation317DownloadsMetricsTotal Citations10Total Downloads317Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The k-server problem is investigated when the metric space is a tree. For this case an on-line k-competitive algorithm for k-servers is presented. The competitiveness ratio k is optimal. The algorithm is memoryless, in the sense that it does not use any information from the past.

A new method for dealing with the server problem is proposed. The technique consists of embedding the given metric space M into a bigger metric space $\text{cl} ( M )$ called the closure of M, and allowing our servers to move in $\text{cl} ( M )$. How this technique can be applied to give a new optimal algorithm for two servers is shown.

An O ( nL )-time algorithm is introduced for constructing an optimal Huffman code for a weighted alphabet of size n , where each code string must have length no greater than L . The algorithm uses O ( n ) space.

The string editing problem for input strings x and y consists of transforming x into y by performing a series of weighted edit operations on x of overall minimum cost. An edit operation on x can be the deletion of a symbol from x, the insertion of a symbol in x or the substitution of a symbol of x with another symbol. This problem has a well-known $O(|x||y|)$ time-sequential solution. Efficient PRAM parallel algorithms for the string editing problem are given. If $m = \min (|x|,|y|)$ and $n = \max (|x|,|y|)$, then the CREW bound is $O(\log m \log n)$ time with $O({{mn} / {\log m}})$ processors. The CROW bound is $O(\log n(\log \log m)^{2})$ time with $O(mn/ \log \log m)$ processors. In all algorithms, space is $O(mn)$.

An O(log ~ n) time, n2/logn processor as well as an O(log n) time, n3/log n processor CREW deterministic parallel algorithms are presented for constructing Huffman codes from a given list of frequences.The time can be reduced to O(log n(loglog n) 2) on an CRCW model, using only n2/(log log n) 2 processors.Also presented is an optimal O(log n) time, O(n/log n) processor EREW parallel algorithm for constructing a tree given a list of leaf depths when the depths are monotonic.An O(log 2 n) time, n processor parallel algorithm is given for the general tree construction problem.We also give an O(log 2 n) time n2/log2n processor algorithm which finds a nearly optimal binary search tree.An O(log 2 n) time n 2'36 processor algorithm for recognizing linear context free languages is given.A crucial ingredient in achieving those bounds is a formulation of these problems as multiplications of special matrices which we call concave matrices.The structure of these matrices makes their parallel multiplication dramatically more efficient than that of arbitrary matrices.

Huffman’s algorithm finds a prefix-free binary code on a weighted alphabet which minimizes the expected length of the code string for a single symbol. A definition is given for the expected delay for a prefix-free binary code on a weighted alphabet: it is the expected time between a request to transmit the symbol and the completion of that transmission, assuming a channel with fixed capacity, where requests are queued. An $O(n^5 )$-time $O(n^3 )$-space convex hull algorithm is given that finds a code of minimal expected delay, where n is the size of the alphabet. It is conjectured that the algorithm has substantially lower time and space complexities in the worst case, and still lower in the average case. The heart of the proof of polynomial time complexity is the convex hull theorem, which states that under certain conditions a binary tree that minimizes one penalty measure can be changed to a binary tree that minimizes a second penalty measure in a carefully controlled sequence of changes called elementary shifts.

Presented are several algorithms whose operations are governed by a principle of failure functions: When searching for an extremal value within a sequence, it suffices to consider only the subsequence of items each of which is the first possible improvement of its predecessor. These algorithms are more efficient than their more traditional counterparts.

The least weight subsequence (LWS) problem is introduced, and is shown to be equivalent to the classic minimum path problem for directed graphs. A special case of the LWS problem is shown to be solvable in $O(n\log n)$ time generally and, for certain weight functions, in linear time. A number of applications are given, including an optimum paragraph formation problem and the problem of finding a minimum height B-tree, whose solutions realize improvement in asymptotic time complexity.

An algorithm that constructs an optimal height-restricted binary tree for a set of n weights in $O(n^{{3 / 2}} L\log ^{{1 / 2}} n)$ time, where L is the maximum permitted height, is presented. This is an improvement over the fastest previously known algorithm, which requires $O(n^2 L)$ time. The algorithm is a hybrid, combining a technique by Hu and Tan with a technique by Michael Garey.

The Lindstrom marking algorithm uses bounded workspace. Its time complexity is $0(n^2 )$ in all cases, but it has been assumed that the average case time complexity is $0(n\log n)$. It is proven that the average case time complexity is $\Theta (n^2 )$ for a wide variety of probability distributions. Similarly, the average size of the Wegbreit bit stack is shown to be $\Theta (n)$.

The least weight subsequence (LWS) problem is introduced, and is shown to be equivalent to the classic minimum path problem for directed graphs. A special case of the LWS problem is shown to be solvable in O(n log n) time generally and, for certain weight functions, in linear time. A number of applications are given, including an optimum paragraph formation problem and the problem of finding a minimum height B-tree, whose solutions realize improvement in asymptotic time complexity.