A modular drinking philosophers algorithm

Summary A variant of the drinking philosophers algorithm of Chandy and Misra is described and proved correct in a modular way. The algorithm of Chandy and Misra is based on a particular dining philosophers algorithm and relies on certain properties of its implementation. The drinking philosophers algorithm presented in this paper is able to use an arbitrary dining philosophers algorithm as a subroutine; nothing about the implementation needs to be known, only that it solves the dining philosophers problem. An important advantage of this modularity is that by substituting a more time-efficient dining philosophers algorithm than the one used by Chandy and Misra, a drinking philosophers algorithm withO(1) worst-case waiting time is obtained, whereas the drinking philosophers algorithm of Chandy and Misra hasO(n) worst-case waiting time (forn philosophers). Careful definitions are given to distinguish the drinking and dining philosophers problems and to specify varying degrees of concurrency. Jennifer L. Welch received her B.A. in 1979 from the University of Texas at Austin, and her S.M. and Ph.D. from the Massachusetts Institute of Technology in 1984 and 1988 respectively. She has been a member of technical staff at GTE Laboratories Incorporated in Waltham, Massachusetts and an assistant professor at the University of North Carolina at Chapel Hill. She is currently an assistant professor at Texas A&M University. Her research interests include algorithms and lower bounds for distributed computing.Much of this work was performed while this author was at the Laboratory for Computer Science, Massachusetts Institute of Technology, supported by the Advanced Research Projects Agency of the Department of Defense under contract N00014-83-K-0125, the National Science Foundation under grants DCR-83-02391 and CCR-86-11442, the Office of Army Research under contract DAAG29-84-K-0058, and the Office of Naval Research under contract N00014-85-K-0168. This author was also supported in part by NSF grant CCR-9010730, an IBM Faculty Development Award, and NSF Presidential Young Investigator Award CCR-9158478This author was supported by the Office of Naval Research under contract N00014-91-J-1046, the Advanced Research Projects Agency of the Department of Defense under contract N00014-89-J-1988, and the National Science Foundation under grant CCR-89-15206. The photograph and autobiography of Professor N.A. Lynch were published in Volume 6, No. 2, 1992 on page 121     

AE1: An extension matrix approximate method for the general covering problem

A new approach, the extension matrix approach, is introduced and used to show that some optimization problems in general covering problem areNP-hard. Approximate solutions for these problems are given. Combining these approximate solutions, this paper presents an approximately optimal covering algorithm,AE1. Implementation shows thatAE1 is efficient and gives optimal or near optimal results.This research was supported in part by the National Science Foundation under Grant DCR 84-06801, Office of Naval Research under Grant N00014-82-K-0186, Defense Advanced Research Project Agency under Grant N00014-K-85-0878, and Education Ministry of the People's Republic of China.On leave from Harbin Institute of Technology, Harbin, China.     

Parallel triangulation of a polygon in two calls to the trapezoidal map

We give a parallel method for triangulating a simple polygon by two (parallel) calls to the trapezoidal map computation. The method is simpler and more elegant than previous methods. Along the way we obtain an interesting partition of one-sided monotone polygons. Using the best-known trapezoidal map algorithm, ours run in timeO(logn) usingO(n) CREW PRAM processors.This research was supported by NSF Grants No. DCR-84-01898 and No. DCR-84-01633, and ONR Contract N00014-85-K-0046.     

The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the firstn/logn processor,O(logn)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.Richard Cole was supported in part by NSF Grants DCR-84-01633 and CCR-8702271, ONR Grant N00014-85-K-0046 and by an IBM faculty development award. Uzi Vishkin was supported in part by NSF Grants NSF-CCR-8615337 and NSF-DCR-8413359, ONR Grant N00014-85-K-0046, by the Applied Mathematical Science subprogram of the office of Energy Research, U.S. Department of Energy under Contract DE-AC02-76ER03077 and the Foundation for Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences and Humanities.     

The complexity of planar compliant motion planning under uncertainty

We consider the computational complexity of planning compliant motions in the plane, given geometric bounds on the uncertainty in sensing and control. We can give efficient algorithms for generating and verifying compliant motion strategies that are guaranteed to succeed as long as the sensing and control uncertainties lie within the specified bounds. We also consider the case where a compliant motion plan is required to succeed over some parametric family of geometries. While these problems are known to be intractable in three dimensions, we identify tractable subclasses in the plane.This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's Artificial Intelligence research is provided in part by the Office of Naval Research under Office of Naval Research Contract N00014-81-K-0494 and in part by the Advanced Research Projects Agency under Office of Naval Research Contracts N00014-85-K-0124 and N00014-82-K.-0334. The author was funded in part by a NASA fellowship administered by the Jet Propulsion Laboratory, and in part by the Mathematical Sciences Institute and the National Science Foundation.     

A parallel algorithm for approximating the minimum cycle cover

We address the problem of approximating aminimum cycle cover in parallel. We give the first efficient parallel algorithm for finding an approximation to aminimum cycle cover. Our algorithm finds a cycle cover whose size is within a factor of 0(1 +n logn/(m + n) of the minimum-sized cover usingO(log² n) time on (m + n)/logn processors.Research supported by ONR Grant N00014-88-K-0243 and DARPA Grant N00039-88-C0113 at Harvard University.Research supported by a graduate fellowship from GE. Additional support provided by Air Force Contract AFOSR-86-0078, and by an NSF PYI awarded to David Shmoys, with matching funds from IBM, Sun Microsystems, and UPS.     

Topological numbering of features on a mesh

Assume we are given ann ×n binary image containing horizontally convex features; i.e., for each feature, each of its row's pixels form an interval on that row. In this paper we consider the problem of assigning topological numbers to such features, i.e., assign a number to every featuref so that all features to the left off in the image have a smaller number assigned to them. This problem arises in solutions to the stereo matching problem. We present a parallel algorithm to solve the topological numbering problem inO(n) time on ann ×n mesh of processors. The key idea of our solution is to create a tree from which the topological numbers can be obtained even though the tree does not uniquely represent the to the left of relationship of the features.The work of M. J. Atallah was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, and the National Science Foundation under Grant DCR-8451393, with matching funds from AT&T. Part of this work was done while he was a Visiting Scientist at the Center for Advanced Architectures project of the Research Institute for Advanced Computer Science, NASA Ames Research Center, Moffett Field, CA 94035, USA. S. E. Hambrusch's work was supported by the Office of Naval Research under Contracts N00014-84-K-0502 and N00014-86K-0689, and by the National Science Foundation under Grant MIP-87-15652. Part of this work was done while she was visiting the International Computer Science Institute, Berkeley, CA 94704, USA. The work of L. E. TeWinkel was supported by the Office of Naval Research under Contract N00014-86K-0689.     

Augmented infinitesimal perturbation analysis: An alternate explanation

Augmented infinitesimal perturbation analysis (APA) was introduced by Gaivoronski [1991] to increase the purview of the theory of Infinitesimal Perturbation Analysis (IPA). In reference [Gaivoronski 1991] it is shown that an unbiased estimate for the gradient of a class of performance measures of DEDS represented bygeneralized semi-Markov processes (GSMPs) (cf. [Glynn 1989] can be expressed as a sum of an IPA-estimate and a term that takes into account the event order changes. In this paper we present an alternate approach to establishing the result of Gaivoronski, and from this we derive a necessary and sufficient condition for the validity of the IPA algorithm for this class of performance measures. Finally we validate our results by simulation examples.This research was supported by the National Science Foundation under grant number ECS-85-15449, Office of Naval Research Grants Nos. N00014-90-K-1093 and N00014-89-J-1023 and by Army Grant No. DAAL-03-86-K-0171.     

Towards systolizing compilation

Summary A scheme for the compilation of imperative or functional programs into systolic programs is demonstrated on matrix composition/decomposition and Gauss-Jordan elimination. Using this scheme, programs for the processor network Warp and for several transputer networks have been generated. Christian Lengauer holds a Dipl. Math. (1976) from the Free University of Berlin, and an M.Sc (1978) and Ph.D. (1982) in Computer Science from the University of Toronto. He was an Assistant Professor of Computer Sciences at The University of Texas at Austin from 1982 to 1989 and is presently a Lecturer in Computer Science at the University of Edinburgh. His past research has been in the areas of systolic design, formal semantics and program construction, and automated theorem proving. Michael Barnett received a B.A. in Computer Science from Brooklyn College/City University of New York in 1985, and is currently a Ph.d. candidate at the University of Texas at Austin, where he has been since 1986. From 1985 to 1986 he worked at IBM's T.J. Watson Research Center. His current research interests include formal methods, programming methodology, and functional programming. Duncan G. Hudson III received the B.A. degree in computer sciences from The University of Texas at Austin in 1987 and the M.S.C.S. degree in computer sciences from The University of Texas at Austin in 1989. He has worked as a Graduate Research Assistant at The University of Texas at Austin in the areas of graphical parallel programming environments, parallel numerical algorithms, and objectoriented programming languages for parallel architectures and as a Software Design Engineer at Texas Instruments in the areas of objectoriented databases and parallel image understanding. He is currently a Ph.D. candidate in the Department of Computer Sciences at The University of Texas at Austin. His current research interests include parallel architectures and algorithms and parallelizing compilers.This research was supported in part by the following funding agencies: through Carnegie-Mellon University by the Defense Advanced Research Projects Agency monitored by the Space and Naval Warfare Systems Command under Contract N00039-87-C-0251 and by the Office of Naval Research under Contracts N00014-87-K-0385 and N00014-87-K-0533; through Oxford University by the Science and Engineering Research Council under Contract GR/E 63902; through the University of Texas at Austin by the Office of Naval Research under Contract N00014-86-K-0763 and by the National Science Foundation under Contract DCR-8610427     

Implementing a Scheme-based parallel processing system

The Scheme language can be converted into a parallel processing language by adding two new data types (placeholders andweak pairs), two processor synchronization primitives, and a task distribution mechanism. The mechanisms that support task creation, scheduling, and task synchronization are built using these extensions and features already present in the sequential language. Implementing the core of the parallel processing component in Scheme itself provides testbed for a variety of experiments and extensions.MultiScheme, the system resulting from these extensions, supports Halstead's future construct as the simple model for parallelism. By revealing the underlying placeholders on top of which this construct is built, Multischeme supports a variety of additional parallel programming techniques. It supports speculative computation through a simple procedural interface and the automatic garbage collection of tasks. The qlet and qlambda constructs of the QLisp language are also easily implemented in MultiScheme, as are the more familiar fork and join constructs of imperative programming.This research was supported in part by the Defense Advanced Research Projects Agency and was monitored by the Office of Naval Research under contract numbers N00014-83-K-0125, N00014-84-K0099, N00014-86-K-0180, and MDA903-84-C-0033. Additional funds and resources were provided by BBN Advanced Computers Inc., and the Hewlett-Packard Corporation. The work was performed as part of the author's dissertation research at the Massachusetts Institute of Technology.     

Emulating the human interpretation of line-drawings as three-dimensional objects

The human vision system has the ability to interpret two-dimensional images as three-dimensional objects. In this article, we present a program that emulates this ability for the case of images consisting of line-drawings. As a by-product of the approach, we provide an explanation of the Necker cube illusion.Support for the Artificial Intelligence Laboratory is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-85-K-0124.     

Systolic algorithms as programs

We represent a systolic algorithm by a program consisting of one multiple assignment statement that captures its operation and data flow. We use invariants to develop such programs systematically. We present two examples, matrix multiplication and LU-decomposition of a matrix.This work was supported in part by a grant from the Office of Naval Research under grant N00014-85-K-0057For photographs and biographics see Distributed Computing (1986) 1:40–52     

Optimizing discrete event dynamic systems via the gradient surface method

In this paper we propose a gradient surface method (GSM) for the optimization of discrete event dynamic systems. GSM combines the advantages of response surface methodology (RSM) and efficient derivative estimation techniques like perturbation analysis (PA) or likelihood ratio method (LR). In GSM, the gradient estimation is obtained by PA (or LR), and the performance gradient surface is obtained from observations at various points in a fashion similar to the RSM. Zero points of the successive approximating gradient surface are then taken as the estimates of the optimal solution. GSM is characterized by several attractive features: it is a single-run method and more efficient than RSM; it uses at each iteration step the information from all data points rather than just the local gradient; it tries to capture the global features of the gradient surface and thereby quickly arrives at the vicinity of the optimal solution. A number of examples are exhibited to illustrate this method.This work was supported by the Office of Naval Research Grants Nos. N00014-90-K-1093 and N00014-89-J-1023, by National Science Foundation Grant No. ECS-85-15449 and by Army Grant No. DAAL-03-86-K-0171.     

Addressing real-time constraints in the design of autonomous agents

The Phoenix project is an experiment in the design of autonomous agents for a complex environment. The project consists of a simulator of the environment, a basic agent architecture, and specific implementation of agents based on real-time techniques; the first two parts have been constructed, the third is on-going. The facets of Phoenix that facilitate real-time research are: a simulator parameterized for varying environmental conditions and instrumented to record behaviors, an agent architecture designed to support adaptable planning and scheduling, and methods for reasoning about real-time constraints.This research has been supported by DARPA, # F30602-85-C-0014; the Office of Naval Research, under a University Research Initiative grant, N00014-86-K-0764; the Office of Naval Research, # N00014-88-K0009, and a grant from the Digital Equipment Corporation. We wish to thank Mike Greenberg for his keen understanding of design issues and mastery of programming that made Phoenix what it is today. We also wish to thank Paul Silvey and David Westbrook for their help.     

The complexity of hashing with lazy deletion

We examine a version of the dynamic dictionary problem in which stored items have expiration times and can be removed from the dictionary once they have expired. We show that under several reasonable assumptions about the distribution of the items, hashing with lazy deletion uses little more space than methods that use eager deletion. The simple algorithm suggested by this observation was used in a program for analyzing integrated circuit artwork.Support for this author was provided in part by NSF research grants MCS-81-05324 and DCR-84-03613, by an IBM research contract, by an IBM Faculty Development Award, and by ONR and DARPA under Contract N00014-83-K-0146 and ARPA Order No. 4786.     

Clocked adversaries for hashing

A clocked adversary is a program that can time its operations and base its behavior on the results of those timings. While it is well known that hashing performs poorly in the worst case, recent results have proven that, for reference-string programs, the probability of falling into a bad case can be driven arbitrarily low. We show that this is not true for clocked adversaries. This emphasizes the limits on the appiicability of theorems on the behavior of hashing schemes on reference string programs, and raises a novel set of problems dealing with optimality of and vulnerability to clocked adversaries.Work was supported by DARPA and ONR Contracts N00014-85-C-0456 and N00014-85-K-0465, and by NSF Cooperative Agreement DCR-8420948.     

Programming language constructs for highly parallel operations on lists

A data structure called strips is described for representing linked lists, which enables unit time access of random list elements. Running parallel prefix on strips effectively converts a list into an array. When combined with nondeterministic statement sequencing and data operations, loops for performing iterations over lists, and insertions and deletions on lists can be parallelized yielding very efficient algorithms. The strips-based representation also allows efficient serial operations on lists, which is important both when loops cannot be parallelized or when there is more parallelism than processors.This work was supported in part under ONR Grant N00014-86-K-0215 and under NSF Grant DCR-8503610.     

Achieving speedups for APL on an SIMD distributed memory machine

The potential speedup for SIMD parallel implementations of APL programs is considered. Both analytical and (simulated) empirical studies are presented. The approach is to recognize that nearly 95% of the operators appearing in APL programs are either scalar primitive, reduction or indexing and so the performance of these operators gives a good estimate of the amount of speedup a full program might receive. Substantial speedups are demonstrated for these operators and the empirical evidence accords with the analytical estimates.This research has been funded by the Office of Naval Research Contract No. N00014-86-K-0264 and the National Science Foundation Grant No. DCR 8416878.     

Fast algorithms for bit-serial routing on a hypercube

In this paper we describe anO(logN)-bit-step randomized algorithm for bit-serial message routing on a hypercube. The result is asymptotically optimal, and improves upon the best previously known algorithms by a logarithmic factor. The result also solves the problem of on-line circuit switching in anO(1)-dilated hypercube (i.e., the problem of establishing edge-disjoint paths between the nodes of the dilated hypercube for any one-to-one mapping).Our algorithm is adaptive and we show that this is necessary to achieve the logarithmic speedup. We generalize the Borodin-Hopcroft lower bound on oblivious routing by proving that any randomized oblivious algorithm on a polylogarithmic degree network requires at least (log² N/log logN) bit steps with high probability for almost all permutations.This research was supported by the Defense Advanced Research Projects Agency under Contracts N00014-87-K-825 and N00014-89-J-1988, the Air Force under Contract AFOSR-89-0271, and the Army under Contract DAAL-03-86-K-0171. This work was completed while the third and fourth authors were at the Laboratory for Computer Science, Massachusetts Institute of Technology.     

Programming simultaneous actions using common knowledge

This work applies the theory of knowledge in distributed systems to the design of efficient fault-tolerant protocols. We define a large class of problems requiring coordinated, simultaneous action in synchronous systems, and give a method of transforming specifications of such problems into protocols that areoptimal in all runs: these protocols are guaranteed to perform the simultaneous actions as soon as any other protocol could possibly perform them, given the input to the system and faulty processor behavior. This transformation is performed in two steps. In the first step we extract, directly from the problem specification, a high-level protocol programmed using explicit tests for common knowledge. In the second step we carefully analyze when facts become common knowledge, thereby providing a method of efficiently implementing these protocols in many variants of the omissions failure model. In the generalized omissions model, however, our analysis shows that testing for common knowledge is NP-hard. Given the close correspondence between common knowledge and simultaneous actions, we are able to show that no optimal protocol for any such problem can be computationally efficient in this model. The analysis in this paper exposes many subtle differences between the failure models, including the precise point at which this gap in complexity occurs.This research was supported by the Office of Naval Research under contract N00014-85-K-0168, by the Office of Army Research under contract DAAG29-84-K-0058, by the National Science Foundation under Grant DCR-8302391, and by the Defense Advanced Research Projects agency (DARPA) under contract N00014-83-K-0125, and was performed while both authors were at MIT. A preliminary version of this work appeared in theProceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, Toronto, 1986.This author was primarily supported by an IBM postdoctoral fellowship.