Paris Kanellakis

in Memoriam

PARIS KANELLAKIS’ RESEARCH: AN OVERVIEW

Paris Kanellakis’s research interests bridged theory and practice both within Brown’s Department of Computer Science, where he managed departmental research projects linking the two, and in the wider international research community. Paris contributed original research in areas as diverse as databases, programming languages, distributed computing, fault tolerance, complexity theory, combinatorial optimization, and lambda calculus models. Underlying those contributions was a unifying theme: the use of logic, complexity, and algorithms to understand the foundations of practical systems, analyze their efficiency, and improve their functionality.

The March issue of Computing Surveys, to which Paris had planned to contribute an article on database theory, has been dedicated to Paris and contains instead an article describing his accomplishments by five of his recent close collaborators. Moshe Vardi describes Paris’ work on deductive databases, Serge Abiteboul his work on object-oriented databases, Gabriel Kuper his work on constraint databases, Alex Shvartsman his work on fault-tolerant parallel computation, and Harry Mairson his work on complexity and type theory. In the rest of this article, we sketch some of these results (references can be found in the Computing Surveys article and in the Paris Kanellakis memorial page, accessible through http://www.cs.brown.edu/people/pck).

The first issue of the Journal of Logic Programming featured an article by Dwork, Kanellakis, and Mitchell entitled “On the Sequential Nature of Unification.” The paper shows that the decision problem “Do two terms unify?” is complete for PTIME; informally speaking, this means that unification cannot be speeded up with a polynomially bounded number of processors. Subsequently Kanellakis and Mitchell used the essential idea behind the proof to show that type inference in ML was PSPACE-hard, i.e., as hard as any problem that can be solved in polynomial space. This result contradicted the popular belief at the time that ML typing was algorithmically simple. His subsequent paper in collaboration with Mairson and Mitchell showed the problem to be complete for EXPTIME. Paris’s most recent work on the lambda calculus (with Hillebrand and Mairson) led to a new and elegant syntactic characterization of complexity classes in terms of the type of the lambda-calculus program, a result that emerged from their research on a functional programming foundation for a logic-based database query language.

Paris was a major contributor to the theory of deductive databases. Using tools from complexity theory, he and Cosmadakis investigated which classes of Datalog queries could be speeded up by parallel computation. Together with Cosmadakis, Gaifman, Hillebrand, Mairson, and Vardi, he studied the decidability of boundedness problem for various classes of Datalog queries (a Datalog query is bounded if its database complexity is O(1)), showing, in particular, that the boundary between the decidable and the undecidable lies between unary and binary queries. He also studied efficient bottom-up implementation of Datalog in a paper with Beeri, Bancilhon, and Ramakrishnan.

In 1989-89, Paris visited the Database Research Group at INRIA Rocquencourt and studied the foundations of object-oriented database systems, which were emerging during this period. His desire to understand the database system O2 led him to develop (in collaboration with Abiteboul, Bancilhon, Delobel, Hillebrand, Ramachandran, and Waller) an object-based data model, a new formalization of object identity, new programming tools, and new indexing algorithms. The book The Story of O2, edited jointly with Bancilhon and Delobel, remains a landmark study of the interconnection between theory and practice in the area of object-oriented databases.

Again in the area of databases, this time in collaboration with Kuper and Revesz, Paris developed the concept of constraint databases, in which the concept of tuples in the relational model is replaced by a conjunction of constraints. They investigated the query complexity of this scheme (which parallels in the database world the area of constraint logic programming) for various classes of constraints. Together with his colleagues and students, he was also engaged in long-term research on this topic. In particular, he and Dina Goldin were working on query algebras and indexing techniques for constraint databases to make this technology practical.

Paris was also interested in bridging the gap between abstract models of parallel computation and realizable architectures. Most parallel algorithms require a fault-free environment to perform correctly and efficiently. In collaboration with Shvartsman, and subsequently also with Buss, Michailidis, and Ragde, Paris proposed a formal notion of robustness that combines fault tolerance and efficiency and studied algorithms that remain efficient in presence of arbitrary dynamic processor failure patterns. This research demonstrates how theoretical work on parallel algorithms with speed-up close to linear in the number of processes can be made practically relevant.

Those of us who worked with Paris have lost not only an outstanding scientist but also an esteemed colleague and a dear friend. As a colleague, he had the poise, personality, and energy to rally communities behind him and he used these qualities to improve our academic and professional environment. We also mourn a friend with a charming and engaging personality and a Mediterranean passion; the warmth and hospitality of him and his family will be sorely missed.
To acknowledge Paris’ contributions to computer science and the deep sense of loss felt by many of us, the Association for Computing Machinery (ACM) plans to institute an award in his memory. To recognize Paris’s pragmatic approach to theoretical computer science, the award will be given for “a theoretical contribution with a significant impact on practice.” The endowment for the award is provided by ACM’s Special Interest Groups in Automata Theory and Databases (SIGACT and SIGMOD), from the Kanellakis family, and from individual contributions (see below).

PARIS KANELLAKIS AWARD
The Association for Computing Machinery plans to institute in Paris’s memory a “Paris Kanellakis Award,” provided that $100,000 can be raised to endow this award at a level of $5,000 per year. The award will be given for “a theoretical contribution to computer science with a significant impact on practice.” The winner of the award will be selected by a committee appointed by the ACM Awards Committee; the award will be given at the annual ACM awards ceremony or as determined by the ACM awards committee. The award may recognize either a specific contribution or a body of work performed no more than fifteen years before the date on which the prize will be awarded.
Two of ACM’s Special Interest Groups, SIGACT and SIGMOD, have contributed $10,000 each to this award and several other institutional contributions are probable. The Kanellakis family has also contributed most generously. We invite pledges to honor Paris and the tradition of scholarly excellence he embodied. The collection of the pledge will be handled by the ACM, who will be in touch with you concerning your (tax-deductible) contribution. Please indicate the amount you wish to pledge by sending email to sjh@cs.brown.edu or writing to the following address:

ACM Paris Kanellakis Award, c/o Susan Howe,

Box 1910, Dept. of Computer Science, Brown University, Providence RI 02912.

For further information you may contact:
Tom Leighton, ftl@math.mit.edu
Christos Papadimitriou, christos@CS.Berkeley.EDU
Moshe Vardi, vardi@cs.rice.edu