PAN: A portable,parallel Prolog: Its design,realisation and performance

PAN is a general purpose, portable environment for executing logic programs in parallel. It combines a flexible, distributed architecture which is resilient to software and platform evolution with facilities for automatically extracting and exploiting AND and OR parallelism in ordinary Prolog programs. PAN incorporates a range of compile-time and run-time techniques to deliver the performance benefits of parallel execution while rertaining sequential execution semantics. Several examples illustrate the efficiency of the controls that facilitate the execution of logic programs in a distributed manner and identify the class of applications that benefit from distributed platforms like PAN. George Xirogiannis, Ph.D.: He received his B.S. in Mathematics from the University of Ioannina, Greece in 1993, his M.S in Artificial Intelligence from the University of Bristol in 1994 and his Ph.D. in Computer Science from Heriot-Watt University, Edinburgh in 1998. His Ph.D. thesis concerns the automated execution of Prolog on distributed heterogeneous multi-processors. His research interests have progressed from knowledge-based systems to distributed logic programming and data mining. Currently, he is working as a senior IT consultant at Pricewaterhouse Coopers. He is also a Research Associate at the National Technical University of Athens, researching in knowledge and data mining. Hamish Taylor, Ph.D.: He is a lecturer in Computer Science in the Computing and Electrical Engineering Department of Heriot-Watt University in Edinburgh. He received M.A. and MLitt degrees in philosophy from Cambridge University and an M.S. and a Ph.D. degree in computer science from Heriot-Watt University, Scotland. Since 1985 he has worked on research projects concerned with implementing concurrent logic programming languages, developing formal models for automated reasoning, performance modelling parallel relational database systems, and visualisizing resources in shared web caches. His current research interests are in applications of collaborative virtual environments, parallel logic programming and networked computing technologies.     

Constructive negation and constraint logic programming with sets

The aim of this paper is to extend theConstructive Negation technique to the case ofCLP(SεT), a Constraint Logic Programming (CLP) language based on hereditarily (and hybrid) finite sets. The challenging aspects of the problem originate from the fact that the structure on whichCLP(SεT) is based is notadmissible closed, and this does not allow to reuse the results presented in the literature concerning the relationships betweenCLP and constructive negation. We propose a new constraint satisfaction algorithm, capable of correctly handling constructive negation for large classes ofCLP(SεT) programs; we also provide a syntactic characterization of such classes of programs. The resulting algorithm provides a novel constraint simplification procedure to handle constructive negation, suitable to theories where unification admits multiple most general unifiers. We also show, using a general result, that it is impossible to construct an interpreter forCLP(SεT) with constructive negation which is guaranteed to work for any arbitrary program; we identify classes of programs for which the implementation of the constructive negation technique is feasible. Agostino Dovier, Ph.D.: He is a researcher in the Department of Science and Technology at the University of Verona, Italy. He obtained his master degree in Computer Science from the University of Udine, Italy, in 1991 and his Ph.D. in Computer Science from the University of Pisa, Italy, in 1996. His research interests are in Programming Languages and Constraints over complex domains, such as Sets and Multisets. He has published over 20 research papers in International Journals and Conferences. He is teaching a course entitled “Special Languages and Techniques for Programming” at the University of Verona. Enrico Pontelli, Ph.D.: He is an Assistant Professor in the Department of Computer Science at the New Mexico State University. He obtained his Laurea degree from the University of Udine (Italy) in 1991, his Master degree from the University of Houston in 1992, and his Ph.D. degree from New Mexico State University in 1997. His research interests are in Programming Languages, Parallel Processing, and Constraint Programming. He has published over 50 papers and served on the program committees of different conferences. He is presently the Associate Director of the Laboratory for Logic, Databases, and Advanced Programming. Gianfranco Rossi, Ph.D.: He received his degree in Computer Science from the University of Pisa in 1979. From 1981 to 1983 he was employed at Intecs Co. System House in Pisa. From November 1983 to February 1989 he was a researcher at the Dipartimento di Informatica of the University of Turin. Since March 1989 he is an Associate Professor of Computer Science, currently with the University of Parma. He is the author of several papers dealing mainly with programming languages, in particular logic programming languages and Prolog, and extended unification algorithms. His current research interests are (logic) programming languages with sets and set unification algorithms.     

Proving termination of GHC programs

A transformational approach for proving termination of parallel logic programs such as GHC programs is proposed. A transformation from GHC programs to term rewriting systems is developed; it exploits the fact that unifications in GHC-resolution correspond to matchings. The termination of a GHC program for a class of queries is implied by the termination of the resulting rewrite system. This approach facilitates the applicability of a wide range of termination techniques developed for rewrite systems in proving termination of GHC programs. The method consists of three steps: (a) deriving moding information from a given GHC program, (b) transforming the GHC program into a term rewriting system using the moding information, and finally (c) proving termination of the resulting rewrite system. Using this method, the termination of many benchmark GHC programs such as quick-sort, merge-sort, merge, split, fair-split and append, etc., can be proved. This is a revised and extended version of Ref. 12). The work was partially supported by the NSF Indo-US grant INT-9416687 Kapur was partially supported by NSF Grant nos. CCR-8906678 and INT-9014074. M. R. K. Krishna Rao, Ph.D.: He currently works as a senior research fellow at Griffith University, Brisbane, Australia. His current interests are in the areas of logic programming, modular aspects and noncopying implementations of term rewriting, learning logic programs from examples and conuterexamples and dynamics of mental states in rational agent architectures. He received his Ph.D in computer science from Tata Institute of Fundamental Research (TIFR), Bombay in 1993 and worked at TIFR and Max Planck Institut für Informatik, Saarbrücken until January 1997. Deepak Kapur, Ph.D.: He currently works as a professor at the State University of New York at Albany. His research interests are in the areas of automated reasoning, term rewriting, constraint solving, algebraic and geometric reasoning and its applications in computer vision, symbolic computation, formal methods, specification and verification. He obtained his Ph.D. in Computer Science from MIT in 1980. He worked at General Electric Corporate Research and Development until 1987. Prof. Kapur is the editor-in-chief of the Journal of Automated Reasoning. He also serves on the editorial boards of Journal of Logic Programming, Journal on Constraints, and Journal of Applicable Algebra in Engineering, Communication and Computer Science. R. K. Shyamasundar, Ph.D.: He currently works as a professor at Tata Institute of Fundamental Research (TIFR), Bombay. His current intersts are in the areas of logic programming, reactive and real time programming, constraint solving, formal methods, specification and verification. He received his Ph.D in computer science from Indian Institute of Science, Bangalore in 1975 and has been a faculty member at Tata Institute of Fundamental Research since then. He has been a visiting/regular faculty member at Technological University of Eindhoven, University of Utrecht, IBM TJ Watson Research Centre, Pennsylvania State University, University of Illinois at Urbana-Champaign, INRIA and ENSMP, France. He has served on (and chaired) Program Committees of many International Conferences and has been on the Editorial Committees.     

Inductive logic programming for relational knowledge discovery

Inductive logic programming (ILP) is concerned with the induction of logic programs from examples and background knowledge. In ILP, the shift of attention from program synthesis to knowledge discovery resulted in advanced techniques that are practically applicable for discovering knowledge in relational databases. This paper gives a brief introduction to ILP, presents selected ILP techniques for relational knowledge discovery and reviews selected ILP applications. Nada Lavrač, Ph.D.: She is a senior research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1978) and a visiting professor at the Klagenfurt University, Austria (since 1987). Her main research interest is in machine learning, in particular inductive logic programming and intelligent data analysis in medicine. She received a BSc in Technical Mathematics and MSc in Computer Science from Ljubljana University, and a PhD in Technical Sciences from Maribor University, Slovenia. She is coauthor of KARDIO: A Study in Deep and Qualitative Knowledge for Expert Systems, The MIT Press 1989, and Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994, and coeditor of Intelligent Data Analysis in Medicine and Pharmacology, Kluwer 1997. She was the coordinator of the European Scientific Network in Inductive Logic Programming ILPNET (1993–1996) and program cochair of the 8th European Machine Learning Conference ECML’95, and 7th International Workshop on Inductive Logic Programming ILP’97. Sašo Džeroski, Ph.D.: He is a research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1989). He has held visiting researcher positions at the Turing Institute, Glasgow (UK), Katholieke Universiteit Leuven (Belgium), German National Research Center for Computer Science (GMD), Sankt Augustin (Germany) and the Foundation for Research and Technology-Hellas (FORTH), Heraklion (Greece). His research interest is in machine learning and knowledge discovery in databases, in particular inductive logic programming and its applications and knowledge discovery in environmental databases. He is co-author of Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994. He is the scientific coordinator of ILPnet2, The Network of Excellence in Inductive Logic Programming. He was program co-chair of the 7th International Workshop on Inductive Logic Programming ILP’97 and will be program co-chair of the 16th International Conference on Machine Learning ICML’99. Masayuki Numao, Ph.D.: He is an associate professor at the Department of Computer Science, Tokyo Institute of Technology. He received a bachelor of engineering in electrical and electronics engineering in 1982 and his Ph.D. in computer science in 1987 from Tokyo Institute of Technology. He was a visiting scholar at CSLI, Stanford University from 1989 to 1990. His research interests include Artificial Intelligence, Global Intelligence and Machine Learning. Numao is a member of Information Processing Society of Japan, Japanese Society for Artificial Intelligence, Japanese Cognitive Science Society, Japan Society for Software Science and Technology and AAAI.     

Learning Horn definitions: Theory and an application to planning

A Horn definition is a set of Horn clauses with the same predicate in all head literals. In this paper, we consider learning non-recursive, first-order Horn definitions from entailment. We show that this class is exactly learnable from equivalence and membership queries. It follows then that this class is PAC learnable using examples and membership queries. Finally, we apply our results to learning control knowledge for efficient planning in the form of goal-decomposition rules. Chandra Reddy, Ph.D.: He is currently a doctoral student in the Department of Computer Science at Oregon State University. He is completing his Ph.D. on June 30, 1998. His dissertation is entitled “Learning Hierarchical Decomposition Rules for Planning: An Inductive Logic Programming Approach.” Earlier, he had an M. Tech in Artificial Intelligence and Robotics from University of Hyderabad, India, and an M.Sc.(tech) in Computer Science from Birla Institute of Technology and Science, India. His current research interests broadly fall under machine learning and planning/scheduling—more specifically, inductive logic programming, speedup learning, data mining, and hierarchical planning and optimization. Prasad Tadepalli, Ph.D.: He has an M.Tech in Computer Science from Indian Institute of Technology, Madras, India and a Ph.D. from Rutgers University, New Brunswick, USA. He joined Oregon State University, Corvallis, as an assistant professor in 1989. He is now an associate professor in the Department of Computer Science of Oregon State University. His main area of research is machine learning, including reinforcement learning, inductive logic programming, and computational learning theory, with applications to classification, planning, scheduling, manufacturing, and information retrieval.     

GigaE PM: a high performance communication facility using a Gigabit Ethernet

A high performance communication facility, called theGigaE PM, has been designed and implemented for parallel applications on clusters of computers using a Gigabit Ethernet. The GigaE PM provides not only a reliable high bandwidth and low latency communication, but also supports existing network protocols such as TCP/IP. A reliable communication mechanism for a parallel application is implemented on the firmware on a NIC while existing network protocols are handled by an operating system kernel. A prototype system has been implemented using an Essential Communications Gigabit Ethernet card. The performance results show that a 58.3 μs round trip time for a four byte user message, and 56.7 MBytes/sec bandwidth for a 1,468 byte message have been achieved on Intel Pentium II 400 MHz PCs. We have implemented MPICH-PM on top of the GigaE PM, and evaluated the NAS parallel benchmark performance. The results show that the IS class S performance on the GigaE PM is 1.8 times faster than that on TCP/IP. Shinji Sumimoto: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. He received BS degree in electrical engineering from Doshisha University. His research interest include parallel and distributed systems, real-time systems, and high performance communication facilities. He is a member of Information Processing Society of Japan. Hiroshi Tezuka: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His research interests include real-time systems and operating system kernel. He is a member of the Information Processing Society of Japan, and Japan Society for Software Science and Technology. Atsushi Hori, Ph.D.: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His current research interests include parallel operating system. He received B.S. and M.S. degrees in Electrical Engineering from Waseda University, and received Ph.D. from the University of Tokyo. He worked as a researcher in Mitsubishi Research Institute from 1981 to 1992. Hiroshi Harada: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His research interests include distributed/parallel systems and distributed shared memory. He received BS degree in physics from Science University of Tokyo. He is a member of ACM and Information Processing Society of Japan. Toshiyuki Takahashi: He is a Researcher at Real World Computing Partnership since 1998. He received his B.S. and M.S. from the Department of Information Sciences of Science University of Tokyo in 1993 and 1995. He was a student of the Information Science Department of the University of Tokyo from 1995 to 1998. His current interests are in meta-level architecture for programming languages and high-performance software technologies. He is a member of Information Processing Society of Japan. Yutaka Ishikawa, Ph.D.: He is the chief of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. He is currently temporary retirement from Electrotechnical Laboratory, MITI. His research interests include distributed/parallel systems, object-oriented programming languages, and real-time systems. He received the B.S., M.S. and Ph.D degrees in electrical engineering from Keio University. He is a member of the IEEE Computer Society, ACM, Information Processing Society of Japan, and Japan Society for Software Science and Technology.     

A parallel copying garbage collection scheme for shared-memory multiprocessors

Earlier work on parallel copying garbage collection is based on parallelization of sequential schemes with breadth-first traversing of live data. Recently it has been demonstrated that sequential copying schemes with depth-first traversing of live data are more flexible and more efficient than the corresponding ones with breadth-first traversal. A clear advantage of the former is that they work with no extra space overheads on non-contiguous memory blocks, which allows more flexible implementation. This paper shows how to parallelize an efficient depth-first copying scheme while retaining its high efficiency and flexibility. Research interests: His research interests include techniques for parallel and distributed implementation of functional, logic, concurrent constraints and object-oriented programming systems. He is also interested in performance analysis and garbage collection. His current interest is efficient techniques for distributed implementation of the concurrent programming language Oz.     

Flat Concurrent Prolog on transputers

Flat Concurrent Prolog (FCP) is a general purpose logic programming language designed for concurrent programming and parallel execution. Staring with a concise introduction of the language and its underlying computational model we describe how to implement a distributed FCP interpreter on a transputer environment using OCCAM. Basic techniques we used for exploiting and controlling parallelism are explained in terms of an abstract architecture. The result of mapping this abstract model on transputers is presented as concrete architecture. Substantial design issues are considered in detail.     

Secure software infrastructure in the internet age

The rapid growth and penetration of the Internet are now leading us to a world where networks are ubiquitous and everything is connected. Breaking the distance barrier by the ubiquitous connection, however, is a two-edged sword. Our network infrastructure today is still fragile and thus “everything is connected” may simply mean “everything can be attacked from whatever place on the earth.” In this paper, we first point out the importance and inherent problems of software systems that underlay open and extensible networks, especially the Internet. We put emphasis on software since software vulnerabilities account for most attacks, incidents, or even disasters on the Internet today. Next we present general ideas of promising techniques in defense of software systems, including theoretical, language-based, and runtime solutions. Finally, we show our experience in developing a secure mail system. Etsuya Shibayama, D.Sc.: He is a professor of the Graduate School of Information Science and Engineering at Tokyo Institute of Technology. He received B.Sc. and M.Sc. in mathematical sciences from Kyoto University in 1981 and 1983, respectively, and D.Sc. in information science from the University of Tokyo in 1991. He is interested in various topics in software including design and implementation of textual and visual programming languages, system software, and user interface software. Recently, he has been doing research on language-based software security and methodologies for building secure software. Akinori Yonezawa, Ph.D.: He is a Professor of computer science at Department of Computer Science, the University of Tokyo. He received his Ph.D. in Computer Science form the Massachusetts Institute of Technology in 1977. His current major research interests are in the areas of concurrent/parallel computation models, programming languages, object-oriented computing and distributed computing. He is the designer of and object-oriented concurrent language ABCL/1 and the editor of several books and served as an associate editor of ACM Transaction of Programming Language and Systems (TOPLAS). Since 1998, he has been an ACM Fellow.     

Atomicm-register operations

Summary We investigate systems where it is possible to access several shared registers in one atomic step. We characterize those systems in which the consensus problem can be solved in the presence of faults and give bounds on the space required. We also describe a fast solution to the mutual exclusion problem using atomicm-register operations. Michael Merritt received a B.S. degree in Philosophy and in Computer Science from Yale College in 1978, the M.S. and Ph. D. degrees in Information and Computer Science in 1980 and 1983, respectively, from the Georgia Institute of Technology. Since 1983 he has been a member of technical staff at AT&T Bell Laboratories, and has taught as an adjunct or visiting lecturer at Stevens Institute of Technology and Columbia University. In 1989 he was program chair for the ACM Symposium on Principles of Distributed Computing. His research interests include distributed and concurrent computation, both algorithms and formal methods for verifying their correctness, cryptography, and security. He is an editor for Distributed Computing and for Information and Computation, recently coauthored a book on database concurrency control algorithms, and is a member of the ACM and of Computer Professionals for Social Responsibility. Gadi Taubenfeld received the B.A., M.Sc. and Ph.D. degrees in Computer Science from the Technion (Israel Institute of Technology), in 1982, 1984 and 1988, respectively. From 1988 to 1990 he was a research scientist at Yale University. Since 1991 he has been a member of technical staff at AT&T Bell Laboratories. His primary research interests are in concurrent and distributed computing.A preliminary version of this workappeared in theProceedings of the Fifth International Workshop on Distributed Algorithms, Delphi, Greece, October 1991, pp 289–294     

Temporal disjunctive logic programming

In this paper we introduce the logic programming languageDisjunctive Chronolog which combines the programming paradigms of temporal and disjunctive logic programming. Disjunctive Chronolog is capable of expressing dynamic behaviour as well as uncertainty, two notions that are very common in a variety of real systems. We present the minimal temporal model semantics and the fixpoint semantics for the new programming language and demonstrate their equivalence. We also show how proof procedures developed for disjunctive logic programs can be easily extended to apply to Disjunctive Chronolog programs. Manolis Gergatsoulis, Ph.D.: He received his B.Sc. in Physics in 1983, the M.Sc. and the Ph.D. degrees in Computer Science in 1986 and 1995 respectively all from the University of Athens, Greece. Since 1996 he is a Research Associate in the Institute of Informatics and Telecommunications, NCSR ‘Demokritos’, Athens. His research interests include logic and temporal programming, program transformations and synthesis, as well as theory of programming languages. Panagiotis Rondogiannis, Ph.D.: He received his B.Sc. from the Department of Computer Engineering and Informatics, University of Patras, Greece, in 1989, and his M.Sc. and Ph.D. from the Department of Computer Science, University of Victoria, Canada, in 1991 and 1994 respectively. From 1995 to 1996 he served in the Greek army. From 1996 to 1997 he was a visiting professor in the Department of Computer Science, University of Ioannina, Greece, and since 1997 he is a Lecturer in the same Department. In January 2000 he was elected Assistant Professor in the Department of Informatics at the University of Athens. His research interests include functional, logic and temporal programming, as well as theory of programming languages. Themis Panayiotopoulos, Ph.D.: He received his Diploma on Electrical Engineering from the Department of Electrical Engineering, National Technical Univesity of Athens, in 1984, and his Ph.D. on Artificial Intelligence from the above mentioned department in 1989. From 1991 to 1994 he was a visiting professor at the Department of Mathematics, University of the Aegean, Samos, Greece and a Research Associate at the Institute of Informatics and Telecommunications of “Democritos” National Research Center. Since 1995 he is an Assistant Prof. at the Department of Computer Science, University of Piraeus. His research interests include temporal programming, logic programming, expert systems and intelligent agent architectures.     

A simple generational real-time garbage collection scheme

This paper presents and empirically evaluates a generational real-time garbage collection scheme, which is based on combining Baker’s real-time scheme with a simple generational scheme by Andrew W. Appel. Real World Computing Partnership. Khayri A. M. Ali, Ph.D.: He currently works as Dean of the Faculty of Computer Science at October University for Modern Sciences and Arts, Egypt. He received his B. Sc. (1970) in Electronics, his M. Sc. (1977) in Automatic Control, both from Egypt. He received his Ph.D. in Computer Systems from the Royal Institute of Technology, Stockholm, in 1984. His research interests are in developing parallel and distributed logic, functional, object-oriented, and constraints programming systems.     

Knowledge in shared memory systems

Summary We study the relation between knowledge and space. That is, we analyze how much shared memory space is needed in order to learn certain kinds of facts. Such results are useful tools for reasoning about shared memory systems. In addition we generalize a known impossibility result, and show that results about how knowledge can be gained and lost in message passing systems also hold for shared memory systems. Michael Merritt received a B.S. degree in Philosophy and in Computer Science from Yale College in 1978, the M.S. and Ph.D. degrees in Information and Computer Science in 1980 and 1983, respectively, from the Georgia Institute of Technology. Since 1983 he has been a member of technical staff at AT & T Bell Laboratories, and has taught as an adjunct or visiting lecturer at Stevens Institute of Technology, Massachusetts Institute of Technology, and Columbia University. In 1989 he was program chair for the ACM Symposium on Principles of Distributed Computing. His research interests include distributed and concurrent computation, both algorithms and formal methods for verifying their correctness, cryptography, and security. He is an editor for Distributed Computing and for Information and Computation, recently co-authored a book on database concurrency control algorithms, and is a member of the ACM and of Computer Professionals for Social Responsibility. Gadi Taubenfeld received the B.A., M.Sc. and Ph.D. degrees in Computer Science from the Technion (Israel Institute of Technology), in 1982, 1984 and 1988, respectively. From 1988 to 1990 he was a research scientist at Yale University. Since 1991 he has been a member of technical staff at AT & T Bell Laboratories. His primary research interests are in concurrent and distributed computing.A preliminary version of this work appeared in the Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, pages 189–200, Montreal, Canada, August 1991     

Verification of multiprocess probabilistic protocols

In this paper we demonstrate the utility of temporal logic to the formal verification of probabilistic distributed programs. The approach taken is to represent the quantitative notion of probabilistic computations by the qualitative abstraction ofextreme fairness. The method is illustrated first on the dining philosophers problem [3] and then on a new probabilistic symmetric solution to then-processes mutual exclusion problem. Two related solutions are presented corresponding to different assumptions about the granularity of a compound test.Amir Pnueli, graduated at the Technion, Haifa, Israel 1962. Received a Ph.D. degree in Applied Mathematics at the Weizmann Institute, Rehovot, Israel, 1967.He is currently a Professor of Computer Science at the Weizmann Institute. His research interests include the Semantics, Verification, Specification and Development of Concurrent and Distributed Systems using Temporal Logic and other Formalisms.Lenore Zuck was born in Tel Aviv, Israel, on September 26, 1958. She received her B.Sc. degree in Computer Science from the Technion, Haifa, Israel in 1979, and the M.Sc. degree in Computer Science at the Weizmann Institute of Science, Rehovot, Israel, in 1983, where she is currently completing her Ph.D. studies. Her areas of interest include the Analysis and Verification of Distributed and Probabilistic Systems and Pre-Classic Music.The work of this author was supported by the Eshkol Fund     

Preference queries in deductive databases

Traditional database query languages such as datalog and SQL allow the user to specify only mandatory requirements on the data to be retrieved from a database. In many applications, it may be natural to express not only mandatory requirements but also preferences on the data to be retrieved. Lacroix and Lavency¹⁰⁾ extended SQL with a notion of preference and showed how the resulting query language could still be translated into the domain relational calculus. We explore the use of preference in databases in the setting of datalog. We introduce the formalism of preference datalog programs (PDPs) as preference logic programs without uninterpreted function symbols for this purpose. PDPs extend datalog not only with constructs to specify which predicate is to be optimized and the criterion for optimization but also with constructs to specify which predicate to be relaxed and the criterion to be used for relaxation. We can show that all of the soft requirements in Reference¹⁰) can be directly encoded in PDP. We first develop anaively-pruned bottom-up evaluation procedure that is sound and complete for computing answers to normal and relaxation queries when the PDPs are stratified, we then show how the evaluation scheme can be extended to the case when the programs are not necessarily stratified, and finally we develop an extension of themagic templates method for datalog¹⁴) that constructs an equivalent but more efficient program for bottom-up evaluation. Kannan Govindarajan, Ph.D.: He obtained his bachelors degree in Computer Science and Engineering from the Indian Institute of Technology, Madras, and he completed his Ph.D. degree in Computer Science from the State University of New York at Buffalo. His dissertation research was on optimization and relaxation techniques for logic languages. His interests lie in the areas of programming languages, databases, and distributed systems. He currently leads the trading community effort in the E-speak Operation in Hewlett Packard Company. Prior to that, he was a member of the Java Products Group in Oracle Corporation. Bharat Jayaraman, Ph.D.: He is a Professor in the Department of Computer Science at the State University of New York at Buffalo. He obtained his bachelors degree in Electronics from the Indian Institute of Technology, Madras (1975), and his Ph.D. from the University of Utah (1981). His research interests are in programming languages and declarative modeling of complex systems. Dr. Jayaraman has published over 50 papers in refereed conferences and journals. He has served on the program committees of several conferences in the area of programming languages, and he is presently on the Editorial Board of the Journal of Functional and Logic Programming. Surya Mantha, Ph.D.: He is a manager in the Communications and Software Services Group of Pittiglio Rabin Todd & McGrath (PRTM), a management consulting firm serving high technology industries. He obtained a bachelors degree in Computer Science and Engineering from the Indian Institute of Technology, Kanpur, an MBA in Finance and Competitive Strategy from the University of Rochester, and a Ph.D. in Computer Science from the University of Utah (1991). His research interests are in the modeling of complex business processes, inter-enterprise application integration, and business strategy. Dr. Mantha has two US patents, and has published over 10 research papers. Prior to joining PRTM, he was a researcher and manager in the Architecture and Document Services Technology Center at Xerox Corporation in Rochester, New York.     

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