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     

Queaps

A new priority queue structure, the queap, is introduced. The queap executes insertion in O(1) amortized time and extract-min in O(log (k+2)) amortized time if there are k items that have been in the heap longer than the item to be extracted. Thus if the operations on the queap are first-in first-out, as on a queue, each operation will execute in constant time. This idea of trying to make operations on the least recently accessed items fast, which we call the queueish property, is a natural complement to the working set property of certain data structures, such as splay trees and pairing heaps, where operations on the most recently accessed data execute quickly. However, we show that the queueish property is in some sense more difficult than the working set property by demonstrating that it is impossible to create a queueish binary search tree, but that many search data structures can be made almost queueish with a O(log logn) amortized extra cost per operation.     

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     

Relaxed multi-way trees with group updates

Data structures with relaxed balance differ from standard structures in that rebalancing can be delayed and interspersed with updates. This gives extra flexibility in both sequential and parallel applications. We study the version of multi-way trees called (a,b)-trees (which includes B-trees) with the operations insertion, deletion, and group insertion. The latter has applications in for instance document databases, WWW search engines, and differential indexing. We prove that we obtain the optimal asymptotic rebalancing complexities of amortized constant time for insertion and deletion and amortized logarithmic time in the size of the group for group insertion. These results hold even for the relaxed version. This is an improvement over the existing results in the most interesting cases.     

Distributed deadlock detection

We describe a simple and efficient algorithm to detect deadlocks in distributed systems. In our model, processes requestN resources from a pool of sizeM. This is a generalization of the well-knownAND-OR request model. The algorithm is incrementally derived and proven correct. Its communication, computational, and space requirements are lower than those of the best previously known algorithms for the simplerAND-OR model.Gabriel Bracha received his B.Sc. Degree in Mathematics (Computer Science option) from Tel-Aviv University, Israel, in 1980, and his Ph.D. degree in Computer Science from Cornell University, Ithaca, NY, in 1985.In 1985, he joined Daisy System, in Tel-Aviv, Israel, where he is currently a Senior Researcher His current research interests include computational geometry, distributed computing, and fault-tolerance.Partial support for this work was provided by the National Science Foundation under grant MCS 83-03135For photograph and biography see Distributed Computing (1987) 2:80–94     

Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure

In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves O(n ²) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. We observe that fully dynamic transitive closure algorithms with O(1) query time maintain explicitly the transitive closure of the input graph, in order to answer each query with exactly one lookup (on its adjacency matrix). Since an update may change as many as Ω(n ²) entries of this matrix, no better bounds are possible for this class of algorithms. This work has been partially supported by the Sixth Framework Programme of the EU under contract number 507613 (Network of Excellence “EuroNGI: Designing and Engineering of the Next Generation Internet”), and number 001907 (“DELIS: Dynamically Evolving, Large Scale Information Systems”), and by the Italian Ministry of University and Research (Project “ALGO-NEXT: Algorithms for the Next Generation Internet and Web: Methodologies, Design and Experiments”). Portions of this paper have been presented at the 41st Annual Symp. on Foundations of Computer Science, 2000.     

Rehabilitation of an unloved child: semi‐splaying

Splay trees are widely considered as the classic examples of self‐adjusting binary search trees and are part of most courses on data structures and algorithms. Already in the first seminal paper on splay trees (J. Assoc. Comput. Mach. 1985; 32(3):652–686) alternative operations were introduced, among which is semi‐splaying. On the one hand, the analysis of semi‐splaying gives a smaller constant for the amortized complexity, but on the other hand the authors write: Whether any version of semi‐splaying is an improvement over splaying depends on the access sequence. Semi‐splaying may be better when the access pattern is stable, but splaying adapts much faster to changes in usage. Maybe this sentence was the reason that nobody seriously ran tests to compare the performance of semi‐splaying and splaying. Semi‐splaying is conceptually simpler than splaying, has the same asymptotic amortized complexity and, as will be clear from empirical data presented in this paper, the practical performance is better for a very broad variety of access patterns. Therefore, its efficiency is a good reason to use semi‐splaying for applications instead of its more prominent brother. Moreover, its simplicity also makes it very attractive for teaching purposes. Copyright © 2008 John Wiley & Sons, Ltd.     

The torus routing chip

The torus routing chip (TRC) is a selftimed chip that performs deadlock-freecut-through routing ink-aryn-cube multiprocessor interconnection networks using a new method of deadlock avoidance calledvirtual channels. A prototype TRC with byte wide self-timed communication channels achieved on first silicon a throughput of 64 Mbits/s in each dimension, about an order of magnitude better performance than the communication networks used by machines such as the Caltech Cosmic Cube or Intel iPSC. The latency of the cut-through routing of only 150 ns per routing step largely eliminates message locality considerations in the concurrent programs for such machines. The design and testing of the TRC as a self-timed chip was no more difficult than it would have been for a synchronous chip. Bill Dally received his B. S. degree in Electrical Engineering from the Virginia Polytechnic Institute in 1980 and his M.S. degree in Electrical Engineering from Stanford University in 1981. From 1980 to 1982 he worked at Bell Telephone Laboratories, where he contributed to the design of the BELLMAC-32 microprocessor. From 1982 to 1983 he worked as a consultant in the area of digital systems design. Since 1983 he has been a graduate student in Computer Science at Caltech, and is expected to complete his Ph.D. studies in the spring 1986. His current research interests include computer architecture, computer aided design, VLSI, design, and concurrent systems. Chuck Seitz earned B.S., M.S., and Ph.D. degrees from M.I.T. Before joining the Computer Science faculty at Caltech in 1977, he worked as a member of the technical staff of the Evans & Sutherland Computer Corporation from 1969 to 1971, as an Assistant Professor of Computer Science at the University of Utah from 1970 to 1972, and as a consultant to Burroughs Corporation from 1971 to 1978. He is currently a Professor of Computer Science at Caltech, where his research and teaching activities are in the areas of VLSI architecture and design, concurrent computation, and self-timed systems.The research described in this paper was sponsored in part by the Defense Advanced Research Projects Agency, ARPA Order number 3771, and monitored by the Office, of Naval Research under contract number N 00014-79-C-0597, in part by Intel Corporation, and in part by an AT & T Ph.D. fellowship     

Atomic snapshots using lattice agreement

Summary Thesnapshot object is an important tool for constructing wait-free asynchronous algorithms. We relate the snapshot object to thelattice agreement decision problem. It is shown that any algorithm for solving lattice agreement can be transformed into an implementation of a snapshot object. The overhead cost of this transformation is only a linear number of read and write operations on atomic single-writer multi-reader registers. The transformation uses an unbounded amount of shared memory. We present a deterministic algorithm for lattice agreement that usedO (log² n) operations on 2-processorTest & Set registers, plusO (n) operations on atomic single-writer multi-reader registers. The shared objects are used by the algorithm in adynamic mode, that is, the identity of the processors that access each of the shared objects is determined dynamically during the execution of the algorithm. By a randomized implementation of 2-processorsTest & Set registers from atomic registers, this algorithm implies a randomized algorthm for lattice agreement that uses an expected number ofO (n) operations on (dynamic) atomic single-writer multi-reader registers. Combined with our transformation this yields implementations of atomic snapshots with the same complexity.Cambridge Research Laboratory, Digital Equipment Corporation Hagit Attiya received the B.Sc. degreeiin Mathematics and Computer Science from the Hebrew University of Jerusalem, in 1981, the M.Sc. and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem, in 1983 and 1987, respectively. She is presently a senior lecturer at the departtment of Computer Science at the Technion, Israel Institute of Technology. Prior to this, she has been a post-doctoral research associate at the Laboratory for Computer Science at M.I.T. Her general research interests are distributed computation and theoretical computer science. More specific interests include fault-tolerance, timing-based and asynchronous algorithms. Maurice Herlihy received the A.B. degree in Mathematics from Harvard University, and the M.S. and the Ph.D. degrees in Computer Science from M.I.T. From 1984 to 1989 he was a faculty member in the Computer Science Department at Carnegie Mellon University in Pittsburgh, PA. In 1989 he joined the research staff at the Digital Equipment Corporation's Cambridge Research Laboratory in Cambridge MA. Since 1994, he has been on the faculty at the Computer Science Department at Brown University. Dr. Herlihy's research interests encompass practical and theoretical aspects of distributed and concurrent computation. Ophir achman received a B.A. in computer science from the Technion, Haifa, Israel in 1989 and M.Sc. in computer science from the Technion, Haifa, Israel, in 1992. He is now studying for a D.Sc. in computer science at the Technion. His currentarea of research is distributed computing, and in particular, asynchronous shared memory systems.This work appeared in preliminary form in proceedings ofthe 6th International Workshop on Distributed Algorithms [12]. This research was partially supported by grant No. 92-0233 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Technion V.P.R. funds — B. and G. Greenberg Research Fund (Ottawa), and the fund for the promotion of research in the TechnionPart of the work of this author was performed while visiting DEC Cambridge Research Laboratory     

Succinct representation of dynamic trees

We study the problem of maintaining a dynamic ordered tree succinctly under updates of the following form: insertion or deletion of a leaf, insertion of a node on an edge (edge subdivision) or deletion of a node with only one child (the child becomes a child of its former grandparent). We allow satellite data of a fixed size to be associated to the nodes of the tree.We support update operations in constant amortized time and support access to satellite data and basic navigation operations in worst-case constant time; the basic navigation operations include parent, first/last-child, previous/next-child. These operations are moving from a node to its parent, leftmost/rightmost child, and its previous and next child respectively.We demonstrate that to efficiently support more extended operations, such as determining the i-th child of a node, rank of a child among its siblings, or size of the subtree rooted at a node, one requires a restrictive pattern for update strategy, for which we propose the finger-update model. In this model, updates are performed at the location of a finger that is only allowed to crawl on the tree between a child and a parent or between consecutive siblings. Under this model, we describe how the named extended operations are performed in worst-case constant time.Previous work on dynamic succinct trees (Munro et al., 2001 [17]; Raman and Rao, 2003 [19]) is mainly restricted to binary trees and achieves poly-logarithmic (Munro et al., 2001 [17]) or “poly-log-log” (Raman and Rao, 2003 [19]) update time under a more restricted model, where updates are performed in traversals starting at the root and ending at the root and queries can be answered when the traversal is completed. A previous result on ordinal trees achieves only sublinear amortized update time and “poly-log-log” query time (Gupta et al., 2007 [11]). More recently, the update time has been improved to O(logn/loglogn) while queries can be performed in O(logn/loglogn) time (Sadakane and Navarro, 2010 [20]).     

An array language for data parallelism: Definition,compilation, and applications

The programming of SIMD machines that strongly support data parallelism, such as the Connection Machine, ¹ presents new challenges for language, compiler, and algorithm designers. We propose an array language that captures many of the abstractions that are necessary for the effective programming of such machines, thereby liberating the user from having to specify low-level details. Consequently, this new language, ALP, allows for efficient compilation using state-of-the-art techniques, achieving hand-code quality. We demonstrate the effectiveness of our approach by two examples which show that despite being an array language, ALP does not restrict expressiveness to rigidly regular computational structures.Work supported in part by ONR grant number N00014-89-J-1906 while on sabbatical leave at the Department of Computer Science, Yale University.Work supported in part by NSF grant number DCR-8405478 while on sabbatical leave at the Department of Computer Science, Yale University.     

A fast,scalable mutual exclusion algorithm

Summary This paper is concerned with synchornization under read/write atomicity in shared memory multi-processors. We present a new algorithm forN-process mutual exclusion that requires only read and write operations and that hasO(logN) time complexity, where time is measured by counting remote memory references. The time complexity of this algorithm is better than that of all prior solutions to the mutual exclusion problem that are based upon atomic read and write instructions; in fact, the time complexity of most prior solutions is unbounded. Performance studies are presented that show that our mutual exclusion algorithm exhibits scalable performance under heavy contention. In fact, its performance rivals that of the fastest queue-based spin locks based on strong primitives such as compare-and-swap and fetch-and-add. We also present a modified version of our algorithm that generates onlyO(1) memory references in the absence of contention. Jae-Heon Yang received the B.S. and M. S. degrees in Computer Engineering from Seoul National University in 1985 and 1987, respectively, and the Ph.D. degree in Computer Science from the University of Maryland at College Park in 1994. Since June 1994, he has been an Assistant Professor of Computer Science at Mills College in Oakland, California. From 1987 to 1989, he was a junior researcher at the Korea Telecommunication Authority Research Center. His research interests include distributed computing and operating systems. James H. Anderson received the M. 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 1993, he has been an Assistant Professor of Computer Science at the University of North Carolina at Chapel Hill. 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 coneurrent and distributed computing. His current interests include wait-free algorithms, scalabde synchronization mechanisms for shared-memory systems, and object-sharing strategies for hard real-time applications.Preliminary version was presented at the Twelfth Annual ACM Symposium on Principles of Distributed Computing Ithaca, New York, August 1993 [15]. Work supported, in part, by NSF Contracts CCR-9109497 and CCR-9216421 and by the Center for Excellence in Space Data and Information Sciences (CESDIS)     

Constants and label-equivalence: A decision procedure for reflexive regular splicing languages

A structural characterization of reflexive splicing languages has been recently given in [P. Bonizzoni, C. De Felice, R. Zizza, The structure of reflexive regular splicing languages via Schützenberger constants, Theoretical Computer Science 334 (2005) 71-98] and [P. Bonizzoni, G. Mauri, Regular splicing languages and subclasses, Theoretical Computer Science 340 (2005) 349-363] showing surprising connections between long standing notions in formal language theory, the syntactic monoid and Schützenberger constant and the splicing operation.In this paper, we provide a procedure to decide whether a regular language is a reflexive splicing language, based on the above-mentioned characterization that is given in terms of a finite set of constants for the language. The procedure relies on the notion of label-equivalence that induces a finite refinement of the syntactic monoid of a regular language L. A finite set of representatives for label-equivalent classes of constant words in L is defined and it is proved that such a finite set provides the splice sites of splicing rules generating language L.     

Generating fixed density bracelets of arbitrary base

Bracelets are lexicographically minimal k-ary strings symmetric under rotation and reversal. In this paper, we present an algorithm for lexicographic listing of bracelets with fixed density. Our algorithm works for arbitrarily large alphabet size and each successive bracelet is generated in constant amortized time.     

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.     

Mutual exclusion in partitioned distributed systems

A network partition can break a distributed computing system into groups of isolated nodes. When this occurs, a mutual exclusion mechanism may be required to ensure that isolated groups do not concurrently perform conflicting operations. We study and formalize these mechanisms in three basic scenarios: where there is a single conflicting type of action; where there are two conflicting types, but operations of the same type do not conflict; and where there are two conflicting types, but operations of one type do not conflict among themselves. For each scenario, we present applications that require mutual exclusion (e.g., name servers, termination protocols, concurrency control). In each case, we also present mutual exclusion mechanisms that are more general and that may provide higher reliability than the voting mechanisms that have been proposed as solutions to this problem. Daniel Barbara is a graduate student in the Computer Science Department at Princeton University and expects to receive his Ph.D. Degree by July 1985. He obtained his BS in Electrical Engineering at the Universidad Metropolitana, Caracas, Venezuela in 1975. His research interests are Distributed Systems, Databases and Computer Networks. He is a member of IEEE and ACM. Hector Garcia-Molina is associate professor in the Department of Computer Science at Princeton University, Princeton, New Jersey. His research interests include distributed computing systems and database systems. He received a BS in electrical engineering from the Instituto Tecnologico de Monterrey. Mexico, in 1974. From Stanford University, Stanford, California, he received in 1975 a MS in electrical engineering and a PhD in computer science in 1979. Garcia-Molina is a member of the ACM and IEEE.     

Distributed optimistic concurrency control with reduced rollback

Concurrency control algorithms have traditionally been based on locking and timestamp ordering mechanisms. Recently optimistic schemes have been proposed. In this paper a distributed, multi-version, optimistic concurrency control scheme is described which is particularly advantageous in a query-dominant environment. The drawbacks of the original optimistic concurrency control scheme, namely that inconsistent views may be seen by transactions (potentially causing unpredictable behavior) and that read-only transactions must be validated and may be rolled back, have been eliminated in the proposed algorithm. Read-only transactions execute in a completely asynchronous fashion and are therefore processed with very little overhead. Furthermore, the probability that read-write transactions are rolled back has been reduced by generalizing the validation algorithm. The effects of global transactions on local transaction processing are minimized. The algorithm is also free from dedlock and cascading rollback problems. Divyakant Agrawal is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received his B.E. degree from Birla Institute of Technology and Science, Pilani, India in 1980. He worked with Tata Burroughs Limited, from 1980 to 1982. He completed his M.S. degree in Computer Science from SUNY at Stony Brook in 1984. His research interests include design of algorithms for concurrent systems, optimistic protocols and distributed systems. Arthur Bernstein is a Professor of Computer Science at the State University of New York at Stony Brook. His research is concerned with the design and verification of algorithms involving asynchronous activity and with languages for expressing such algorithms. Pankaj Gupta is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received M.S. degree in Electrical Engineering from SUNY at Stony Brook in 1982 and M.S. degree in Computer Science from SUNY at Stony Brook in 1985. His research interests include distributed systems, concurrency control, and databases. Soumitra Sengupta is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received his B.E. degree from Birla Institute of Technology and Science, Pilani, India in 1980. He worked with Tata Consultancy Services, from 1980 to 1982. He completed his M.S. degree in Computer Science from SUNY at Stony Brook in 1984. His research interests include distributed algorithms, logic databases and concurrency control.This work was supported by the National Science Foundation under grant, DCR-8502161 and the Air Force Office of Scientific Research under grant AFOSR 810197     

SMART: Speedup Job Completion Time by Scheduling Reduce Tasks

Journal of Computer Science and Technology - Distributed computing systems have been widely used as the amount of data grows exponentially in the era of information explosion. Job completion time...     

Fast and simple distributed consensus

Summary The problem of fault-tolerant agreement is fundamental to distributed computing. When agreement is to be reached in spite of arbitrary behavior by faulty processors, this problem is calledDistributed Consensus. By requiring that the number of faulty processors be , wheren is the number of processors in the system, we are able to derive two new protocols forDistributed Consensus. Both are simple and use messages that are only one bit in length, and both provide forearly stopping: the fewer failures there are, the fewer rounds of communication are required. One protocol is optimal with respect to the number of rounds of communication required, and the other is asymptotically optimal with respect to the total number of message bits exchanged. James E. Burns received the B.S. degree in mathematics from the California Institute of Technology, the M.B.I.S. degree from Georgia State University, and the M.S. and Ph.D. degrees in information and computer science from the Georgia Institute of Technology. He served on the faculty of Computer Science at Indiana University and the College of Computing at the Georgia Institute of Technology before joining Bellcore in 1993. He is currently a Member of Technical Staff in the Network Control Research Department, where he is studying the telephone control network with special interest in behavior when faults occur. He also has research interests in theoretical issues of distributed and parallel computing, especially relating to problems of synchronization and fault tolerance. Gil Neiger was born on February 19, 1957 in New York, New York. In June 1979, he received an A.B. in Mathematics and Psycholinguistics from Brown University in Proidence, Rhode Island. In February 1985, he spent two weeks picking cotton in Nicaragua in a brigade of international volunteers. In January 1986, he received an M.S. in Computer Science from Cornell University in Ithaca, New York and, in August 1988, he received a Ph.D. in Computer Science, also from Cornell University. On August 20, 1988, Dr. Neiger married Hilary Lombard in Lansing, New York. Since August 1988, he has been an Assistant Professor in the College of Computing (formely School of Information and Computer Science) at the Georgia Institute of Technology in Atlanta, Georgia. Dr. Neiger is a member of the editorial board of theChicago Journal of Theoretical Computer Science and theJournal of Parallel and Distributed Computing.This author was supported in part by the National Science Foundation under grants CCR-8909663, CCR-9106627, and CCR-9301454.