Lawrence L. Larmore

TCS Journal 2023 Journal Article

Analysis of a memory-efficient self-stabilizing BFS spanning tree construction

• Ajoy K. Datta
• Stéphane Devismes
• Colette Johnen
• Lawrence L. Larmore

In this paper, we present the last work we collaborated with our late friend, Professor Ajoy Kumar Datta (1958-2019), who prematurely left us four years ago. This article is therefore dedicated to him. In this work, we shed new light on a self-stabilizing wave algorithm proposed by Colette Johnen in 1997 [1]. Starting from an arbitrary configuration, this algorithm endlessly re-constructs a BFS spanning tree in any connected rooted network. Nowadays, it is still the best existing self-stabilizing BFS spanning tree construction in terms of memory requirement, i. e. , it only requires Θ ( 1 ) bits per edge. However, it has been originally proven assuming a weakly fair daemon. Moreover, its stabilization time was unknown until now. Here, we study the slightly modified version of this algorithm, still keeping the same memory requirement. We prove the self-stabilization of this variant under the distributed unfair daemon and show a stabilization time in O ( D ⋅ n 2 ) rounds, where D is the network diameter and n the number of processes.

TCS Journal 2023 Journal Article

Breaking the 2-competitiveness barrier for two servers in a tree

• Wolfgang Bein
• Lawrence L. Larmore

A randomized on-line algorithm is given for the 2-server problem on a tree, with competitiveness less than 1. 94 against the oblivious adversary. This is the first algorithm for this problem with competitive ratio less than 2. The algorithm generalizes earlier work for the line using fractional analysis, and defines a potential in terms of isolation indices from T-theory.

TCS Journal 2020 Journal Article

Loosely-stabilizing leader election with polylogarithmic convergence time

• Yuichi Sudo
• Fukuhito Ooshita
• Hirotsugu Kakugawa
• Toshimitsu Masuzawa
• Ajoy K. Datta
• Lawrence L. Larmore

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 unless the exact number of agents is known a priori. Thus, in our prior work, we introduced concept of loose-stabilization, which is weaker than self-stabilization but has similar advantage in practice. Following this work, several loosely-stabilizing leader election protocols have been given. Loosely-stabilizing leader election guarantees that, starting from an arbitrary configuration, the system reaches a safe configuration with a single leader within a short time, and keeps the unique leader for a long time thereafter. The convergence times of all existing loosely-stabilizing protocols, i. e. , the expected times to reach a safe configuration, are polynomial in n where n is the number of nodes, while their holding times, i. e. , the expected times to keep the unique leader after reaching a safe configuration, are exponential in n. In this paper, a loosely-stabilizing protocol with polylogarithmic convergence time is presented. Its holding time is not exponential, rather an arbitrarily large polynomial function of n.

TCS Journal 2019 Journal Article

A silent self-stabilizing algorithm for the generalized minimal k-dominating set problem

• Ajoy K. Datta
• Stéphane Devismes
• Lawrence L. Larmore

We give a silent self-stabilizing algorithm for the generalized minimal k-dominating set problem in a connected distributed network G. Given a positive integer k and two sets of processes R ⁎ ⊆ D ⁎, the problem is to find a set D which is minimal subject to the conditions that R ⁎ ⊆ D ⊆ D ⁎ and that D is k-dominating relative to D ⁎, meaning that every process within distance k of D ⁎ is also within distance k of D. The algorithm is order-invariant, requires O ( log ⁡ N + log ⁡ k ) space per process, works under the distributed unfair scheduler, and converges in O ( N + k ) rounds, where N is a given upper bound on the number of processes.

TCS Journal 2017 Journal Article

Self-stabilizing silent disjunction in an anonymous network

• Ajoy K. Datta
• Stéphane Devismes
• Lawrence L. Larmore

In this paper, we give a distributed silent self-stabilizing algorithm, DISJ, for the disjunction problem in a connected network. In this problem, each process x has an input bit x. in, assigned by the application layer, and each process must compute the disjunction of the input bits of all processes. DISJ is uniform, and works in an anonymous network under the distributed unfair daemon. The stabilization time of DISJ is O ( n ) rounds, where n is the size of the network, and the memory requirement per process is O ( log ⁡ D + Δ ) where D and Δ are, respectively, the diameter, and the maximum degree of the network.

TCS Journal 2016 Journal Article

Competitive self-stabilizing k-clustering

• Ajoy K. Datta
• Stéphane Devismes
• Karel Heurtefeux
• Lawrence L. Larmore
• Yvan Rivierre

In this paper, we give a silent self-stabilizing algorithm for constructing a k-clustering of any asynchronous connected network with unique IDs. Our algorithm stabilizes in O ( n ) rounds, using O ( log ⁡ k + 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. 2552 k + O ( 1 ) -competitive, that is, the number of k-clusters constructed by the algorithm is at most 7. 2552 k + 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 Quasi-Unit Disk Graph (QUDG) with approximation ratio λ, then our algorithm is 7. 2552 λ 2 k + O ( λ ) -competitive. In case of tree networks, our algorithm computes a k-clustering with the minimum number of clusters. Our solution is based on the self-stabilizing construction of a data structure called an 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 we use (called LFMIS) 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 D 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.

TCS Journal 2015 Journal Article

R–LINE: A better randomized 2-server algorithm on the line

• Lucas Bang
• Wolfgang Bein
• Lawrence L. Larmore

A randomized on-line algorithm is given for the 2-server problem on the line, with competitiveness less than 1. 901 against the oblivious adversary. This improves the previously best known competitiveness of 155 78 ≈ 1. 987 for the problem. The algorithm uses a new approach and defines a potential in terms of isolation indices from T-theory.

TCS Journal 2013 Journal Article

Self-stabilizing labeling and ranking in ordered trees

• Ajoy K. Datta
• Stéphane Devismes
• Lawrence L. Larmore
• Yvan Rivierre

We give two self-stabilizing algorithms for tree networks. The first computes an index, called guide pair, for each process P in O ( h ) rounds using O ( δ P log n ) space per process, where h is the height of the tree, δ P the degree of P, and n the number of processes in the network. Guide pairs have numerous applications, including ordered traversal or navigation in the tree. Our second algorithm, which uses the guide pairs computed by the first algorithm, solves in O ( n ) rounds the ranking problem for an ordered tree, where each process has an input value. This second algorithm has space complexity O ( b + δ P log n ) in each process P, where b is the number of bits needed to store an input value. The first algorithm orders the tree processes according to their topological positions. The second algorithm orders (ranks) the processes according to their input values.

TCS Journal 2011 Journal Article

A randomized algorithm for two servers in cross polytope spaces

• Wolfgang Bein
• Kazuo Iwama
• Jun Kawahara
• Lawrence L. Larmore
• James A. Oravec

It has been a long-standing open problem to determine the exact randomized competitiveness of the 2 -server problem, that is, the minimum competitiveness of any randomized online algorithm for the 2 -server problem. For deterministic algorithms the best competitive ratio that can be obtained is 2 and no randomized algorithm is known that improves this ratio for general spaces. For the line, Bartal et al. (1998) [2] give a 155 78 competitive algorithm, but their algorithm is specific to the geometry of the line. We consider here the 2 -server problem over Cross Polytope Spaces M 24. We obtain an algorithm with competitive ratio of 19 12, and show that this ratio is best possible. This algorithm gives the second non-trivial example of metric spaces with better than 2 -competitive ratio. The algorithm uses a design technique called the knowledge state technique — a method not specific to M 24.

TCS Journal 2011 Journal Article

Self-stabilizing leader election in optimal space under an arbitrary scheduler

• Ajoy K. Datta
• Lawrence L. Larmore
• Priyanka Vemula

A silent self-stabilizing asynchronous distributed algorithm, SSLE, is given for the leader election problem in a connected unoriented (bidirectional) network with unique IDs. SSLE also constructs a BFS tree on the network rooted at that leader. SSLE uses O ( log n ) space per process and stabilizes in O ( n ) rounds, against the unfair daemon, where n is the number of processes in the network.

TCS Journal 2009 Journal Article

A quadratic time 2-approximation algorithm for block sorting

• Wolfgang W. Bein
• Lawrence L. Larmore
• Linda Morales
• I. Hal Sudborough

The block sorting problem is the problem of minimizing the number of steps to sort a list of distinct items, where a sublist of items which are already in sorted order, called a block, can be moved in one step. We give an approximation algorithm for the block sorting problem with an approximation ratio of 2 and run time O ( n 2 ). The approximation algorithm is based on the related concept of block deletion. We show that finding an optimum block deletion sequence can be done in O ( n 2 ) time, even though block sorting is known to be N P -hard. Block sorting has importance in connection with optical character recognition (OCR) and is related to transposition sorting in computational biology.

TCS Journal 2009 Journal Article

Optimally competitive list batching

• Wolfgang Bein
• Leah Epstein
• Lawrence L. Larmore
• John Noga

Batching has been studied extensively in the offline case, but applications such as manufacturing or TCP acknowledgment often require online solutions. We consider online batching problems, where the order of jobs to be batched is fixed and where we seek to minimize the sum of the completion times of the jobs. We present optimally competitive online algorithms for both s -batch and p -batch problems, and we also derive results for certain naturally occurring special cases, such as the case of unit processing times.

SODA Conference 2006 Conference Paper

The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity

• Wolfgang W. Bein
• Mordecai J. Golin
• Lawrence L. Larmore
• Yan Zhang 0021

MFCS Conference 2003 Conference Paper

Faster Algorithms for k -Medians in Trees

• Robert Benkoczi
• Binay K. Bhattacharya
• Marek Chrobak
• Lawrence L. Larmore
• Wojciech Rytter

Abstract In the k -median problem we are given a connected graph with non-negative weights associated with the nodes and lengths associated with the edges. The task is to compute locations of k facilities in order to minimize the sum of the weighted distances between each node and its closest facility. In this paper we consider the case when the graph is a tree. We show that this problem can be solved in time \(O(n {\mbox{\rm polylog}} (n))\) for the following cases: (i) directed trees (and any fixed k ), (ii) balanced undirected trees, and (iii) undirected trees with k =3.

MFCS Conference 2002 Conference Paper

Fast Algorithms with Algebraic Monge Properties

• Wolfgang W. Bein
• Peter Brucker
• Lawrence L. Larmore
• James K. Park

Abstract When restricted to cost arrays possessing the sum Monge property, many combinatorial optimization problems with sum objective functions become significantly easier to solve. The more general algebraic assignment and transportation problems are similarly easier to solve given cost arrays possessing the corresponding algebraic Monge property. We show that Monge-array results for two sum-of-edge-costs shortest-path problems can likewise be extended to a general algebraic setting, provided the problems’ ordered commutative semigroup satisfies one additional restriction. In addition to this general result, we also show how our algorithms can be modified to solve certain bottleneck shortest-path problems, even though the ordered commutative semigroup naturally associated with bottleneck problems does not satisfy our additional restriction. We show how our bottleneck shortest-path techniques can be used to obtain fast algorithms for a variant of Hirschberg and Larmore’s optimal paragraph formation problem, and a special case of the bottleneck traveling-salesman problem.

TCS Journal 2002 Journal Article

The 3-server problem in the plane

• Wolfgang W. Bein
• Marek Chrobak
• Lawrence L. Larmore

In the k-server problem we wish to minimize, in an online fashion, the movement cost of k servers in response to a sequence of requests (we assume that k⩾2). The request issued at each step is specified by a point r in a given metric space M. To serve this request, one of the k servers must move to r. It is known that if M has at least k+1 points then no online algorithm for the k-server problem in M has competitive ratio smaller than k. The best known upper bound on the competitive ratio in arbitrary metric spaces, by Koutsoupias and Papadimitriou (J. ACM 42 (1995) 971), is 2k−1. There are only a few special cases for which k-competitive algorithms are known: for k=2, when M is a tree, or when M has at most k+2 points. We prove that the Work Function Algorithm is 3-competitive for the 3-server problem in the Manhattan plane. As a corollary, we obtain a 4. 243-competitive algorithm for 3 servers in the Euclidean plane. The best previously known competitive ratio for 3 servers in these metric spaces was 5.

MFCS Conference 2001 Conference Paper

The k-Median Problem for Directed Trees

• Marek Chrobak
• Lawrence L. Larmore
• Wojciech Rytter

Abstract The k -median problem is a classical facility location problem. We consider the k -median problem for directed trees, motivated by the problem of locating proxies on the World Wide Web. The two main results of the paper are an O(n log n) time algorithm for k=2 and an O(n log 2 n) time algorithm for k=3. The previously known upper bounds for these two cases were O ( n 2 ).

TCS Journal 1998 Journal Article

Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages

• Lawrence L. Larmore
• Wojciech Rytter

Sublinear time almost optimal algorithms for the recognition problem for three basic subclasses of context-free languages (unambiguous, deterministic and linear) are presented. Optimality is measured with respect to the work of the best-known sequential algorithm for a given problem.

TCS Journal 1997 Journal Article

Correctness of constructing optimal alphabetic trees revisited

• Marek Karpinski
• Lawrence L. Larmore
• Wojciech Rytter

Several new observations which lead to new correctness proofs of two known algorithms (Hu-Tucker and Garsia-Wachs) for construction of optimal alphabetic trees are presented. A generalized version of the Garsia-Wachs algorithm is given. Proof of this generalized version works in a structured and illustrative way and clarifies the usually poorly understood behavior of both the Hu-Tucker and Garsia-Wachs algorithms. The generalized version permits any nonnegative weights, as opposed to strictly positive weights required in the original Garsia-Wachs algorithm. New local structural properties of optimal alphabetic trees are given. The concept of well-shaped segment (a part of an optimal tree) is introduced. It is shown that some parts of the optimal tree are known in advance to be well-shaped, and this implies correctness of the algorithms rather easily. The crucial part of the correctness proof of the Garsia-Wachs algorithm, namely the structural theorem, is identified. The correctness proof of the Hu-Tucker algorithm consists of showing a very simple mutual simulation between this algorithm and the Garsia-Wachs algorithm. For this proof, it is essential to use the generalized version of Garsia-Wachs algorithm, in which an arbitrary locally minimal pair is processed, not necessarily the rightmost minimal pair. Such a generalized version is also needed for parallel implementations. Another result presented in this paper is the clarification of the problem of resolving ties (equalities between weights of items) in the Hu-Tucker algorithm. This is related to the proof, by simulation, of correctness of the Hu-Tucker algorithm. It is shown that the condition that there are no ties may generally be assumed without harm and that, essentially, the Hu-Tucker algorithm avoids ties automatically.

SODA Conference 1996 Conference Paper

Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees

• Marek Karpinski
• Lawrence L. Larmore
• Wojciech Rytter

SODA Conference 1992 Conference Paper

Generosity Helps, or an 11-Competitive Algorithm for Three Servers

• Marek Chrobak
• Lawrence L. Larmore

TCS Journal 1992 Journal Article

HARMONIC is 3-competitive for two servers

• Marek Chrobak
• Lawrence L. Larmore

We consider the server algorithm, called HARMONIC, that always moves the servers with probabilities proportional to the inverses of distances to the request point. We show that for two servers HARMONIC is 3-competitive. Before it was only known that the competitiveness constant of this algorithm is between 3 and 6.

SODA Conference 1990 Conference Paper

Length-Limited Coding

• Lawrence L. Larmore
• Daniel S. Hirschberg

MFCS Conference 1990 Conference Paper

On Fast Algorithms for Two Servers

• Marek Chrobak
• Lawrence L. Larmore

Abstract We consider 2-server algorithms with time complexity O (1) per each request. We show that the previously known algorithm BALANCE2 has competitiveness constant not better than 6, and present another algorithm whose competitiveness constant is 4.

SODA Conference 1990 Conference Paper

On-Line Dynamic Programming with Applications to the Prediction of RNA Secondary Structure

• Lawrence L. Larmore
• Baruch Schieber

FOCS Conference 1985 Conference Paper

The Least Weight Subsequence Problem (Extended Abstract)

• Daniel S. Hirschberg
• Lawrence L. Larmore

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.