Mapping image processing operations onto a linear systolic machine

A high-performance systolic machine, called Warp, is operational at Carnegie Mellon. The machine has a programmable systolic array of linearly connected cells, each capable of performing 10 million floating-point operations per second. Many image processing operations have been programmed on the machine. This programming experience has yielded new insights in the mapping of image processing operations onto a parallel computer. This paper identifies three major mapping methods that are particularly suited to a Warp-like parallel machine using a linear array of processing elements. These mapping methods correspond to partitioning of input dataset, partitioning of output dataset, and partitioning of computation along the time domain (pipelining). Parallel implementations of several important image processing operations are presented to illustrate the mapping methods. These operations include the Fast Fourier transform (FFT), connected component labelling, Hough transform image warping and relaxation.H.T. Kungjoined the faculty of Carnegie Mellon University in 1974 after receiving his Ph.D. degree there. Appointed to Profesor in 1982, he is currently holding Shell Distinguished Chair in Computer Science at Carnegie Mellon. He was Guggenheim Fellow in 1983–84, and a full time Architecture Consultant to ESL, Inc., a subsidiary of TRW, in 1981. Dr. Kung's current research interests are in high-performance computer architectures and their applications. He has served on editorial boards of several journals and program committees of numerous conferences in VLSI and computer science.Jon A. Webbreceived the Ph.D. degree in computer science from The University of Texas at Austin in 1980. From 1981 he has worked on the faculty of the Department of Computer Science at Carnegie-Mellon University, where he is currently a Research Computer Scientist. His research interests include the theory of vision and parallel architectures for vision. He has published papers on the recovery of structure from motion, the shape of subjective contours, the design and use of a parallel architecture for low-level vision, and experiments in the visual control of a robot vehicle. Dr. Webb is a member of the IEEE Computer Society and the Association for Computing Machinery.The research was supported in part by Defense Advanced Research Projects Agency (DOD), monitored by the Air Force Avionics Laboratory under Contract F33615-84-K-1520, and Naval Electronic Systems Command under Contract N00039-85-C-0134, in part under ARPA Order number 5147, monitored by the US Army Engineer Topographic Laboratories under contract DACA 76-85-C-0002, and in part by the Office of Naval Research under Contracts N00014-80-C-0236, NR 048-659, and N00014-85-K-0152, NR SDRJ-007     

Asymptotically optimal algorithms for approximate agreement

This paper introduces some algorithms to solve crash-failure, failure-by-omission and Byzantine failure versions of the Byzantine Generals or consensus problem, where non-faulty processors need only arrive at values that are close together rather than identical. For each failure model and each value ofS, we give at-resilient algorithm usingS rounds of communication. IfS=t+1, exact agreement is obtained. In the algorithms for the failure-by-omission and Byzantine failure models, each processor attempts to identify the faulty processors and corrects values transmited by them to reduce the amount of disagreement. We also prove lower bounds for each model, to show that each of our algorithms has a convergence rate that is asymptotic to the best possible in that model as the number of processors increases. Alan Fekete was born in Sydney Australia in 1959. He studied Pure Mathematics and Computer Science at the University of Sydney, obtaining a B.Sc.(Hons) in 1982. He then moved to Cambridge, Massachusetts, where he obtained a distributed Ph.D. degree, awarded by Harvard University's Mathematics department for work supervised by Nancy Lynch in M.I.T.'s Laboratory for Computer Science. He spend the year 1987–1988 at M.I.T. as a postdoctoral Research Associate, and is now Lecturer in Computer Science at the University of Sydney. His research concentrates on understanding the modularity in distributed algorithms, especially those used for concurrency control in distributed databases.A preliminary version of this paper has appeared in the Proceedings of the 5th ACM Symposium on Principles of Distributed Computing (August 1986). This work was begun in the Department of Mathematics, Harvard University, and completed at the Laboratory for Computer Science at Massachusetts Institute of Technology. The work was supported in part (through Professor N. Lynch) 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 Grants MCS-8306854, DCR-83-02391, and CCR-8611442, and by the Defense Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125     

Transaction commit in a realistic timing model

Animportant problem in the construction of fault-tolerant distributed database systems is the design of nonblocking transaction commit protocols. This problem has been extensively studied for synchronous systems (i.e., systems where no messages ever arrive late). In this paper, the synchrony assumption is relaxed. A new partially synchronous timing model is described. Developed for this model is a new nonblocking randomized transaction commit protocol, which incorporates an agreement protocol of Ben-Or. The new protocol works as long as fewer than half the processors fail. A matching lower bound is proved, showing that the number of processor faults tolerated is optimal. If half or more of the processors fail, the protocol degrades gracefully: it blocks, but no processor produces a wrong answer. A notion of asynchronous round is defined, and the protocol is shown to terminate in a small constant expected number of asynchronous rounds. In contrast it is shown that no protocol in this model can guarantee that a processor terminates in a bounded expected number of its own steps, even if processors are synchronous. Brian A. Coan received the B.S.E. degree in electrical engineering and computer science from Princeton University, Princeton, New Jersey, in 1977; the M.S. degree in computer engineering from Stanford University, Stanford, California, in 1979; and the Ph.D. degree in computer science from the Massachusetts Institute of Technology, Cambridge, Massachusetts, in 1987. He has worked for Amdahl Corporation and AT & T Bell Laboratories. Currently he is a member of the technical staff at Bellcore. His main research interest is fault tolerance in distributed systems. Jennifer Lundelius 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 respecively. She was a member of technical staff at GTE Laboratories Incorporated in Waltham, Massachusetts, from 1988 to 1989. She is currently an assistant professor at the University of North Carolina in Chapel Hill. Her research interests include algorithms and lower bounds for distributed computing.The authors were with the MIT Laboratory for Computer Science when the bulk of this work was done. This work was supported in part by the Advanced Research Projects Agency of the Department of Defense under Contract N00014-83-K-0125, the National Science Foundation under Grant DCR-83-02391, the Office of Army Research under Contract DAAG29-84-K-0058, and the Office of Naval Research under Contract N00014-85-K-0168. A preliminary version of this paper appears in theProceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing [2]     

Some impossibility results in interprocess synchronization

Summary In this paper we construct a formal specification of the problem of synchronizing asynchronous processes under strong fairness. We prove that strong interaction fairness is impossible for binary (and hence for multiway) interactions and strong process fairness is impossible for multiway interactions. Yih-Kuen Tsay received his B.S. degree form National Taiwan University in 1984 and his M.S. degree from UCLA in 1989. He is currently a Ph.D. candidate in the UCLA Computer Science Department. His research interests include distributed algorithms, fault-tolerant systems, and specification and verification of concurrent programs. Rajive L. Bagrodia received the B. Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay in 1981 and the M.A. and Ph.D. degrees in Computer Science from the University of Texas at Austin in 1983 and 1987 respectively. He is currently an Assistant Professor in the Computer Science Department at UCLA. His research interests include parallel languages, distributed algorithms, parallel simulation and software design methodologies. He was selected as a 1991 Presidential Young Investigator by NSF.This research was partially supported by NSF PYI Award number ASC9157610 and by ONR under grant N00014-91-J1605     

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     

Highly concurrent logically synchronous multicast

We define thelogically synchronous multicast problem which imposes a natural and useful structure on message delivery order in an asynchronous system. In this problem, a computation proceeds by a sequence ofmulticasts, in which a process sends a message to some arbitrary subset of the processes, including itself. A logically synchronous multicast protocol must make it appear to every process as if each multicast occurs simultaneously at all participants of that multicast (sender plus receivers). Furthermore, if a process continually wishes to send a message, it must eventually be permitted to do so.We present a highly concurrent solution in which each multicast requires at most 4|S| messages, whereS is the set of participants in that multicast. The protocol's correctness is shown using a careful problem specification stated in the I/O automaton model. We conclude the paper by describing how the logically synchronous multicast protocol can be used for distributed simulation of algorithms expressed as I/O automata. Kenneth J. Goldman received the Sc.B. degree in Computer Science from Brown University in 1984, the S.M. degree in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology in 1987, and the Ph.D. degree in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology in 1990. As part of his doctoral work, he designed and implemented the Spectrum Simulation System, a distributed algorithm development tool based on the I/O automaton model of Lynch and Tuttle. His publications include papers in the areas of models for distributed computing, database concurrency control, human interfaces, and image processing. He is currently Assistant Professor in the Department of Computer Science at Washington University in St. Louis.A preliminary version of this paper appeared in the Proceedings of the 3rd International Workshop on Distributed Algorithms, Lecture Notes in Computer Science 392, Bermond and Raynal, Eds., Springer-Verlag, Berlin, 1989, pp 94–109.This research was conducted at the Massachusetts Institute of Technology Laboratory for Computer Science and was supported in part by the National Science Foundation under Grant CCR-86-11442, by the Office of Naval Research under Contract N00014-85-K-0168, by the Defense Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125, and by an Office of Naval Research graduate fellowship     

Multi-writer composite registers

Summary Acomposite register is an array-like shared data object that is partitioned into a number of components. An operation of such a register either writes a value to a single component, or reads the values of all components. A composite register reduces to an ordinary atomic register when there is only one component. In this paper, we show that a composite register with multiple writers per component can be implemented in a wait-free manner from a composite register with a single writer per component. It has been previously shown that registers of the latter kind can be implemented from atomic registers without waiting. Thus, our results establish that any composite register can be implemented in a wait-free manner from atomic registers. We show that our construction has comparable space compexity and better time complexity than other constructions that have been presented in the literature. James H. Anderson received the B.S. degree in Computer Science from Michigan State University in 1982, the M.S. degree in Computer Science from Purdue University in 1983, and the Ph.D. degree in Computer Sciences from the University of Texas at Austin in 1990. He recently joined the Computer Science Department at the University of North Carolina at Chapel Hill, where he is now an Assistant Professor. Prior to joining the University of North Carolina, he was an Assistant Professor of Computer Science for three years at the University of Maryland at College Park. Professor Anderson's main research interests are within the area of concurrent and distributed computing. His current interests primarily involve the implementation of resilient and scalable synchronization mechanisms.Preliminary version was presented at the Ninth Annual ACM Symposium on Principles of Distributed Computing [2]Much of the work described herein was completed while the author was with the University of Texas at Austin and the University of Maryland at College Park. This work was supported at the University of Texas by ONR Contract N00014-89-J-1913, and at the University of Maryland by NSF Contract CCR 9109497 and by an award from the University of Maryland General Research Board     

One-bit algorithms

Many algorithms in distributed systems assume that the size of a single message depends on the number of processors. In this paper, we assume in contrast that messages consist of a single bit. Our main goal is to explore how the one-bit translation of unbounded message algorithms can be sped up by pipelining. We consider two problems. The first is routing between two processors in an arbitrary network and in some special networks (ring, grid, hypercube). The second problem is coloring a synchronous ring with three colors. The routing problem is a very basic subroutine in many distributed algorithms; the three coloring problem demonstrates that pipelining is not always useful. Amotz Bar-Noy received his B.Sc. degree in Mathematics and Computer Science in 1981, and his Ph.D. degree in Computer Science in 1987, both from the Hebrew University of Jerusalem, Israel. Between 1987 and 1989 he was a post-doctoral fellow in the Department of Computer Science at Stanford University. He is currently a visiting scientist at the IBM Thomas J. Watson Research Center. His current research interests include the theoretical aspects of distributed and parallel computing, computational complexity and combinatorial optimization. Joseph (Seffi) Naor received his B.A. degree in Computer Science in 1981 from the Technion, Israel Institute of Technology. He received his M.Sc. in 1983 and Ph.D. in 1987 in Computer Science, both from the Hebrew University of Jerusalem, Israel. Between 1987 and 1988 he was a post-doctoral fellow at the University of Southern California, Los Angeles, CA. Since 1988 he has been a post-doctoral fellow in the Department of Computer Science at Stanford University. His research interests include combinatorial optimization, randomized algorithms, computational complexity and the theoretical aspects of parallel and distributed computing. Moni Naor received his B.A. in Computer Science from the Technion, Israel Institute of Technology, in 1985, and his Ph.D. in Computer Science from the University of California at Berkeley in 1989. He is currently a visiting scientist at the IBM Almaden Research Center. His research interests include computational complexity, data structures, cryptography, and parallel and distributed computation.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731Supported by contract ONR N00014-88-K-0166 and by a grant from Stanford's Center for Integrated Systems. This work was done while the author was a post-doctoral fellow at the University of Southern California, Los Angeles, CAThis work was done while the author was with the Computer Science Division, University of California at Berkeley, and Supported by NSF grant DCR 85-13926     

Pre-Scheduling

Static scheduling has been well accepted for its predictability and online simplicity. Traditional static schedule generation techniques are usually based on the assumption of constant rate of resource supply known at design time. Under resource composition schemes, however, this assumption may not be valid for a workload to be statically scheduled. A pre-schedule is a static schedule without assuming constant and completely predictable rate of resource supply. In this paper, concepts of supply function and supply contract are introduced to define the actual online resource supply rate and the constraints to this rate known off-line. Based on these concepts, this paper defines the pre-scheduling problem, and presents a sound, complete, and PTIME pre-scheduler.This research is supported partially by grants from the Office of Naval Research under ONR contract N00014-03-1-0705 and the National Science Foundation under NSF grant CCR0207853.Weirong Wang received B.E. in computer engineering from Beijing University of Technology, M.A. and Ph.D. in computer science from the University of Texas at Austin. He is currently an automation engineer in Intel. His research interests include real-time and embedded systems, software engineering and algorithms.Aloysius K. Mok Aloysius K. Mok is Quincy Lee Centennial Professor in Computer Science at the University of Texas at Austin. He received the S.B. in electrical engineering, the S.M. in electrical engineering and computer science and the Ph.D. degrees in computer science, all from the Massachusetts Institute of Technology. Since 1983, Dr. Mok been on the faculty of the Department of Computer Sciences at the University of Texas at Austin. Professor Mok has done extensive research on computer software systems and is internationally known for his work in real-time systems. He is a past Chairman of the Techni- cal Committee on Real-Time Systems of the Institute of Electrical and Electronics Engineers, and has served on numerous national and international research and advisory panels. His current interests include real-time and embed- ded systems, robust and secure network-centric computing and real-time knowledge-based systems. Dr. Mok received in 2002 the IEEE TC on Real-Time Systems Award for his outstanding technical contributions and leadership achievements in real-time systems.Gerhard Fohler is Professor and leader of the predictably flexible real-time systems group at SDL. He received his Ph.D. from Vienna University of Technology in 1994 for research towards flexibility for offline scheduling in the MARS system. He then worked at the University of Massachusetts at Amherst as postdoctoral researcher within the SPRING project. During 1996–97, he was a researcher at Humboldt University Berlin, investigating issues of adaptive reliability and real-time. Gerhard Fohler is currently chairman of the Technical Committee on Real-Time Systems of EUROMICRO.     

Composite registers

Summary We introduce a shared data object, called acomposite register, that generalizes the notion of an atomic register. A composite register is an array-like shared data object that is partitioned into a number of components. An operation of a composite register either writes a value to a single component or reads the values of all components. A composite register reduces to an ordinary atomic register when there is only one component. In this paper, we show that multi-reader, singlewriter atomic registers can be used to implement a composite register in which there is only one writer per component. In a related paper, we show how to use the composite register construction of this paper to implement a composite register with multiple writers per component. These two constructions show that it is possible to implement a shared memory that can be read in its entirety in a single snapshot operation, without using mutual exclusion. James H. Anderson received the B.S. degree in Computer Science from Michigan State University in 1982, the M.S. degree in Computer Science from Purdue University in 1983, and the Ph.D. degree in Computer Sciences from the University of Texas at Austin in 1990. Since August 1990, he has been with the University of Maryland at College Park, where he is now an Assistant Professor of Computer Science. Since January 1992, he has been a staff scientist at NASA's Center of Excellence in Space Data and Information Sciences, located at the Goddard Space Flight Center in Greenbelt, Maryland. Professor Anderson's primary research interests are within the area of concurrent and distributed computing.Preliminary version presented at theNinth Annual ACM Symposium on Principles of Distributed Computing [2]Work supported, in part, at the University of Texas at Austin by Office of Naval Research Contract N00014-89-J-1913, and at the University of Maryland by an award from the University of Maryland General Research Board     

A note on weighted distributed match-making

In many distributed computing environments, processes are concurrently executed by nodes in a store-and-forward network. Distributed control issues as diverse as name-server, mutual exclusion, and replicated data management, involve making matches between processes. The generic paradigm is a formal problem called “distributed match-making.” We define multidimensional and weighted versions, and the relations between the two, and develop a very general method to prove lower bounds on the complexity as a tradeoff between number of messages and “distributedness.” The resulting lower bounds are tight in all cases we have examined. We present a success-stop version of distributed match-making that is analysed in terms of a weight distribution that in all cases results in approximately halving the (expected) number of messages required in the corresponding strategy that does not use these weights. The second author did part of this work at the Laboratory for Computer Science, M.I.T., Cambridge, MA. He was supported in part 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-83-02391, and by the Defence Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125. A preliminary version of this paper appeared inProc. VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing (AWOC 88), Lecture Notes in Computer Science, vol. 319, Springer-Verlag, Berlin, 1988, pp. 361–368.     

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.     

Recognizing safety and liveness

A formal characterization for safety properties and liveness properties is given in terms of the structure of the Buchi automaton that specifies the property. The characterizations permit a property to be decomposed into a safety property and a liveness property whose conjunction is the original. The characterizations also give insight into techniques required to prove a large class of safety and liveness properties.Bowen Alpern was born in 1952. He received a Ph.D. in Computer Science from Cornell University in 1986. Currently, he is a Research Staff Member in the Mathematics Department of the IBM T.J. Watson Research Center.Fred B. Schneider is an associate professor in the Computer Science Department at Cornell University. He received a Ph.D. in Computer Science from S.U.N.Y. at Stony Brook in 1978 and a B.S. from Cornell in 1975. Schneider is a member of the editorial boards of Distributed Computing and Information Processing Letters. He is also a member of the U.S. Army Committee on Recommendations for Basic Research, the College Board Committe for Advanced Placement Computer Science, IFIP Working Group 2.3 (Programming Methodology), and the Standing Organizing Committee for Principles of Distributed Computing Conferences. He has served on the program committee for PODC, POPL, SOSP, and FTCS.This work is supported, in part, by NSF Grant DCR-8320274 and Office of Naval Research contract N00014-86-K-0092     

Efficient algorithms for optimistic crash recovery

Summary Recovery from transient processor failures can be achieved by using optimistic message logging and checkpointing. The faulty processorsroll back, and some/all of the non-faulty processors also may have to roll back. This paper formulates the rollback problem as a closure problem. A centralized closure algorithm is presented together with two efficient distributed implementations. Several related problems are also considered and distributed algorithms are presented for solving them. S. Venkatesan received the B. Tech. and M. Tech degrees from the Indian Institute of Technology, Madras in 1981 and 1983, respectively and the M.S. and Ph.D. degrees in Computer Science from the University of Pittsburgh in 1985 and 1988. He joined the University of Texas at Dallas in January 1989, where he is currently an Assistant Professor of Computer Science. His research interests are in fault-tolerant distributed systems, distributed algorithms, testing and debugging distributed programs, fault-tolerant telecommunication networks, and mobile computing. Tony Tony-Ying Juang is an Associate Professor of Computer Science at the Chung-Hwa Polytechnic Institute. He received the B.S. degree in Naval Architecture from the National Taiwan University in 1983 and his M.S. and Ph.D. degrees in Computer Science from the University of Texas at Dallas in 1989 and 1992, respectively. His research interests include distributed algorithms, fault-tolerant distributed computing, distributed operating systems and computer communications.This research was supported in part by NSF under Grant No. CCR-9110177 and by the Texas Advanced Technology Program under Grant No. 9741-036     

Adaptive solutions to the mutual exclusion problem

Summary Algorithms for mutual exclusion that adapt to the current degree of contention are developed. Afilter and a leader election algorithm form the basic building blocks. The algorithms achieve system response times that are independent of the total number of processes and governed instead by the current degree of contention. The final algorithm achieves a constant amortized system response time. Manhoi Choy was born in 1967 in Hong Kong. He received his B.Sc. in Electrical and Electronic Engineerings from the University of Hong Kong in 1989, and his M.Sc. in Computer Science from the University of California at Santa Barbara in 1991. Currently, he is working on his Ph.D. in Computer Science at the University of California at Santa Barbara. His research interests are in the areas of parallel and distributed systems, and distributed algorithms. Ambuj K. Singh is an Assistant Professor in the Department of Computer Science at the University of California, Santa Barbara. He received a Ph.D. in Computer Science from the University of Texas at Austin in 1989, an M.S. in Computer Science from Iowa State University in 1984, and a B.Tech. from the Indian Institute of Technology at Kharagpur in 1982. His research interests are in the areas of adaptive resource allocation, concurrent program development, and distributed shared memory.A preliminary version of the paper appeared in the 12th Annual ACM Symposium on Principles of Distributed ComputingWork supported in part by NSF grants CCR-9008628 and CCR-9223094     

Parallel depth first search. Part II. Analysis

This paper presents the analysis of a parallel formulation of depth-first search. At the heart of this parallel formulation is a dynamic work-distribution scheme that divides the work between different processors. The effectiveness of the parallel formulation is strongly influenced by the work-distribution scheme and the target architecture. We introduce the concept of isoefficiency function to characterize the effectiveness of different architectures and work-distribution schemes. Many researchers considered the ring architecture to be quite suitable for parallel depth-first search. Our analytical and experimental results show that hypercube and shared-memory architectures are significantly better. The analysis of previously known work-distribution schemes motivated the design of substantially improved schemes for ring and shared-memory architectures. In particular, we present a work-distribution algorithm that guarantees close to optimal performance on a shared-memory/-network-with-message-combining architecture (e.g. RP3). Much of the analysis presented in this paper is applicable to other parallel algorithms in which work is dynamically shared between different processors (e.g., parallel divide-and-conquer algorithms). The concept of isoefficiency is useful in characterizing the scalability of a variety of parallel algorithms.This work was supported by Army Research Office Grant No. DAAG29-84-K-0060 to the Artificial Intelligence Laboratory, and Office of Naval Research Grant N00014-86-K-0763 to the Computer Science Department at the University of Texas at Austin.     

Appraising fairness in languages for distributed programming

The relations among various languages and models for distributed computation and various possible definitions of fairness are considered. Natural semantic criteria are presented which an acceptable notion of fairness should satisfy. These are then used to demonstrate differences among the basic models, the added power of the fairness notion, and the sensitivity of the fairness notion to irrelevant semantic interleavings of independent operations. These results are used to show that from the considerable variety of commonly used possibilities, only strong process fairness is appropriate forCSP if these criteria are adopted. We also show that under these criteria, none of the commonly used notions of fairness are fully aceptable for a model with an n-way synchronization mechanism. The notion of fairness most often mentioned for Ada is shown to be fully acceptable. For a model with nonblockingsend operations, some variants of common fairness definitions are appraised, and two are shown to satisfy the suggested criteria. Krzysztof R. Apt was born in 1949 in Poland. Received his Ph.D. in 1974 from Polish Academy of Sciences in Warsaw in mathematical logic. From 1974 until 1981 worked at various scientific institutions in the Netherlands and from 1981 until 1987 at C.N.R.S. in Paris, France. Spent 1985 as a visiting scientist at IBM Research Centre in Yorktown Heights, U.S.A. Currently holding an Endowed Professorship at the Department of Computer Sciences at the University of Texas at Austin; also a senior research scientist at the Centre for Mathematics and Computer Science in Amsterdam, the Netherlands. His research interests include program correctness and semantics, methodology of distributed computing, use of logic as a programming language and non-standard forms of reasoning. He has served on editorial boards of a number of journals and program committees of numerous conferences in computer science. Lectured in a dozen countries on four continents. Also, he has run two marathons and crossed Sumatra on a bicycle. Shmuel Katz received his B.A. in Mathematics and English Literature from U.C.L.A., and his M.Sc. and Ph.D. in Computer Science (1976) from the Weizmann Institute in Rehovot, Israel. From 1976 to 1981 he was a researcher at the IBM Israel Scientific Center. Presently, he is a Senior Lecturer in the Computer Science Department at the Technion in Haifa, Israel. In 1977–78, he visited for a year at the University of California, Berkeley, and in 1984–85 was at the University of Texas at Austin. He has also been a consultant for the MCC Software Technology Program. His research interests include the methodology of programming, specification methods, program verification and semantics, distributed programming, data structures, and programming languages. Nissim Francez received his B.A. in Mathematics and Philosophy from the Hebrew University in Jerusalem, and his M.Sc. and Ph.D. in computer science (1976) from the Weizmann Institute of Science, Rehovot, Israel. In 1976–77 he spent a postdoctoral year at Queen's university, Belfast, where he was introduced by C.A.R. Hoare to CSP. In 1977–78 he was an assistant professor at USC, Los Angeles. From 1978 he is with the Computer Science Department at the Technion. In 1982–83 he was on a sabbatical leave at IBM T.J. Watson Research Center. He has been a consultant for MCC's software technology program, working on multiparty activities in distributed systems. He had summer appointments in Harvard University, IBM T.J. Watson Research Center, Utrecht University, CWI (Amsterdam) and at MCC. He also served in several program committees. His research interests include program verification and the semantics of programming languages, mainly for concurrent and distributed programming. Is also interested in logic programming and recursive query evaluation and in compiler constration. He is the author of the first book onFairness. Unfortunately, he is incapable of Marathon running...     

Randomization for robot tasks: Using dynamic programming in the space of knowledge states

This paper explores the use of randomization as a primitive action in the solution of robot tasks. An example of randomization is the strategy of shaking a bin containing a part in order to orient the part in a desired stable state with some high probability. Further examples include tapping, vibrating, twirling, and random search. For instance, it is sometimes beneficial for a system to execute random motions purposefully when the precise motions required to perform an operation are unknown, as when they lie below the available sensor resolution.The purpose of this paper is to provide a theoretical framework for the planning and execution of randomized strategies for robot tasks. This framework is built on the standard backchaining approach of dynamic programming. Specifically, a randomizing planner backchains from the goal in a state space whose states describe the knowledge available to the system at run-time. By choosing random actions in a principled manner at run-time, a system can sometimes obtain a probabilistic strategy for accomplishing a task even when no guaranteed strategy exists for accomplishing that task. In other cases, the system may be able to obtain a speedup over an existing guaranteed strategy.The main result of this paper consists of two examples. One example shows that randomization can sometimes speed up task completion from exponential time to polynomial time. The other example shows that such a speedup is not always possible.The author is now with the School of Computer Science and the Robotics Institute at Carnegie-Mellon University. The work reported here was performed while at the MIT Artificial Intelligence Laboratory. This work was supported in part by the Office of Naval Research under the University Research Initiative Program through Contract N00014-86-K-0685, by an NSF Presidential Young Investigator Award to Tomás Lozano-Pérez, by a fellowship from NASA's Jet Propulsion Laboratory, and by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research Contract N00014-85-K-0124. Additional support at CMU was provided under NSF grant IRI-9010686.     

Parallel depth first search. Part I. Implementation

This paper presents a parallel formulation of depth-first search which retains the storage efficiency of sequential depth-first search and can be mapped on to anyMIMD architecture. To study its effectiveness it has been implemented to solve the 15-puzzle problem on three commercially available multiprocessors—Sequent Balance 21000, the Intel Hypercube and BBN Butterfly. We have been able to achieve fairly linear speedup on Sequent up to 30 processors (the maximum configuration available) and on the Intel Hypercube andBBN Butterfly up to 128 processors (the maximum configurations available). Many researchers considered the ring architecture to be quite suitable for parallel depth-first search. Our experimental results show that hypercube and sharedmemory architectures are significantly better.At the heart of our parallel formulation is a dynamic work distribution scheme that divides the work between different processors. The effectiveness of the parallel formulation is strongly influenced by the work distribution scheme and architectural features such as presence/absence of shared memory, the diameter of the network, relative speed of the communication network, etc. In a companion paper,(¹) we analyze the effectiveness of different load-balancing schemes and architectures, and also present new improved work distribution schemes.This work was supported by Army Research Office Grant No. DAAG29-84-K-0060 to the Artificial Intelligence Laboratory, and Office of Naval Research Grant N00014-86-K-0763 to the Computer Science Department at the University of Texas ay Austin     

ParaGraph: Graph editor support for parallel programming environments

We report here on a graph editor, ParaGraph, that supports massively parallel programming. It provides a flexible mechanism for the concise specification of families of annotated graphs, addressing the problems of user annotation and scale independent graph manipulation. ParaGraph currently serves as the basis for tools supporting communication abstractions in program specification and debugging. Its foundation in an extended form of aggregate rewriting graph grammars makes its adaptation to other parallel programming environments straightforward.The Parallel Programming Environments Project at the University of Massachusetts is supported by the Office of Naval Research under Contract N000014-84-K-0647 and by the National Science Foundation under Grants DCR-8500332 and CCR-8712410.