Final Evaluation of ESPRIT LTR 20244 ALCOM-IT Dr. Thierry Duhamel, Matra Marconi Space, Toulouse Prof. Dr. Gerhard Goos, Universität Karlsruhe, Karlsruhe Prof. Dr. Neil D. Jones, DIKU, Copenhagen June 9, 1999 ALCOM-IT, Esprit Long Term Research project 20244, is a continuation of the two BRA projects 3075 and 7141, ALCOM I and II. This review corresponds to the final milestone, covering January 1 ,1998 - June 31, 1999. General ALCOM-IT has devoted approximately 180 person-years of work during its three-year period, work only partially paid from project 20244. ALCOM-IT links the 10 participating institutions together, so that the project produces added value across Europe which none of those institutions could achieve on its own. All partners were active in Work Area 3, Foundations and Methods. The other work areas were more dispersed. All involve several partners in an active way. ALCOM-IT in its final period has been quite successful in many respects: Foundations and Methods: This has been a particular stronghold of ALCOM since its beginning. ALCOM-IT combined has shown itself to be quite competitive against similar groups in the US. The area has made several very interesting advances during the given period. Libraries: Several software libraries and other software tools developed within the project are now maturing to the level of professional usability. Others are on their way to this level. The partners are exchanging algorithms and programs among themselves on a fairly large scale, which greatly extends their development capacity. Some libraries have already an impressive list of licensees worldwide; this has been helped by the effort made for portability of the software tools on a large number of H/W platforms. The productivity of the ALCOM-IT team in terms of size and quality of code has also been remarkable. Software Development for Specific IT Demands: Strong progress has been made in several areas during 1998/9 in developing effective state-of-the-art software for industrial applications. This performance was also revealed by the 10 software demonstrations shown during the review, some of these demos at a quite professional standard. They show the applicability and usefulness of the ideas and methods developed in this project. Some of them also show a beginning mastery of the packaging needed to bridge the gap between scientific methods and their industrial applications in the project. We repeat, however, from our last review, that such productisation is not the task of ALCOM itself. The purpose of a possible successor to ALCOM -IT should be rather to develop state-of-the-art algorithmic software which can then be taken up by industry or commercial vendors. It is better not to concentrate too much on commercialisation aspects within the project itself. Overall Appraisal The workshop at Barcelona went quite well without any organisational or practical problems. The workshop presentations were interesting and useful to assess the work done during 1998/9. The Progress Report covered the right material, and was received by mail in time. The reviewers also appreciated receiving during this past period the reports produced within ALCOM-IT. Level of activity A very large number of researchers are working as part of the ALCOM-IT project, many with partial or total support from their ``home'' institutions. 19 PhD degrees have been awarded in 1998/9 with direct connection to the ALCOM-IT project. The Progress Report lists 208 reports, 106 articles in international journal and 174 international conference contributions and 3 online documents. This is a 40% increase above the already very excellent performance achieved in 1997. Even when considering the high amount of money spent on the project these are extremely impressive numbers. An indication of the quality of the research is the fact that about 30 % of the reports made it to journals. Industrial relations This is an area where improvement over the previous years has been obvious and characterised by: - the interest manifested by many companies for the software products developed within ALCOM-IT, - the successful collaboration with industrial partners in several areas where ALCOM-IT partners have shown to be able to provide useful solutions to practical problems. We encourage all partners of the project to continue the effort in that direction. In addition two software companies in Europe can be considered as spin-offs of the ALCOM-IT project. Summary The reviewers acknowledge that about 50% of the users, both scientific and industrial, of some packages developed in ALCOM-IT are in the US. For the LEDA package there is even an American distributor. At the end of the project these facts testify that ALCOM-IT has achieved the goal to significantly contribute to the worldwide state of the art in algorithm design and to take a lead in composing packages of algorithms and data structures for industrial use. The future must show how the partners of ALCOM-IT can continue their cooperation in order to maintain their lead, especially how they avoid their packages being overtaken by inferior (both in quality, depth and size) but more fashionable American developments written, say in Java. Remarks on the Work Areas Work Area 3, Foundations and Methods This is quite solid work, and well-established in the academic scientific literature. Consequently we do not discuss it in detail here, although noteworthy results have certainly been achieved. Most of the publications of the project stem from this area. 1.1: LEDA The LEDA library constitutes an impressive and world leading achievement of ALCOM-IT. About 50% of its users, both scientific and industrial, are now in the US and about 3 LEDA licences are sold per month which is an excellent achievement. For the future worldwide marketing of this library must still be improved. The much delayed book on LEDA is now in the printing stage and will be an excellent advertising tool. The number of LEDA extension packages (LEPs) has considerably increased; LEPs are now covering many application areas of scientific and also of commercial interest. LEPs at present seem to be a good means for avoiding an unhealthy growth of the base library which otherwise may lead to confusion and other difficulties amongst users. Clearly LEDA has been a precursor and set a world standard; nervetheless this leadership can be challenged by initiatives in the US. In addition, the rise of Java as the language of choice for many applications, also outside the networking area, is raising the question how LEDA, being written in C++, may maintain its lead under changing boundary conditions. This may require investments in labour which go beyond the abilities and desires of the academic institutions who created LEDA. Besides further evolution of LEDA and its LEPs any possible successor project must address this problem. 1.2 and 4.4: Graph drawing The reviewers acknowledge that this area has continued its technical progress during the review period. The packages GDToolkit and AGD, both based on LEDA but targeted towards different application areas are now reusable and distributable libraries based on LEDA. A book on graph drawing to which also authors from overseas have contributed has been published and will contribute to the further propagation of ALCOM-IT achievements. From the last review we repeat our judgement that currently considering also other projects in which the Saarbrücken and Köln site of ALCOM-IT and other universities are engaged Europe has a lead in graph drawing algorithms worldwide. Overall, the graph drawing work now seems much better integrated, e.g. more solidly based on LEDA than before; it has also drawn more interpartner usage of the packages. This evaluation applies to the graph drawing activities led by the Rome, Saarbrücken and Köln site. As already noted at the last review the graph drawing package Pigale developed at EHESS seems to have very little connection with the rest of the project despite interesting talks and demonstrations at the review about a quite unconventional and efficient method of graph representation. All groups have continued and partially considerably extended their industrial cooperations for using the libraries for commercial applications. 1.3 and 4.3: ABACUS, Logistics and Resource Management The development of the ABACUS library has made further rapid progress during the review period. ABACUS is now distributed and in use at many academic and some commercial sites. Half of the commercial users are in the US; nevertheless the marketing of the package needs closer attention in the future. Algorithms developed for ABACUS have been included in the packages for graph drawing. Many other applications ranging from tomography and frequency assignment in cellular phone networks to transportation of airline parts have been developed inside and outside of ALCOM-IT. The practical usefulness of ABACUS is definitely and firmly established by all these applications. Goals of further development must include the improvement of packaging applications such that they can be used with only minor modifications outside of the project, and work on making the library more accessible to the non-specialist. The practical work on Logistics and Resource Management at several sites has made good progress and is obviously producing benefits for the industrial partners involved. Most of this applied work is heavily based on ABACUS and has also provided feedback for the further development of the library. In summary, through its rapid development ABACUS has become one of the major achievements of ALCOM-IT. 2.1: FRAMES This library together with associated tools has made good progress, as could be seen from the presentation given and from the software demonstration. The present applications are mainly targeted towards scientific computing. It is suggested also to look for other application areas, e.g., in the field of parallelising database transactions. Further developments in this area should address the issue of who is the target user of the library: today clearly it cannot be used by application engineers but by knowledgeable programmers. 2.2, 4.2: DSP and DSS Despite the criticism and suggestions which we voiced during the last review, we did not see much progress in the development of DSS. Especially the continuing concentration on Intracom as the sole industrial partner has limited the scope of workplan item 4.2 considerably. On the other hand, the development of DSP has made good progress. It is now a viable tool for investigating distributed protocols, also in practice. It is, however, targeted towards an audience interested in the algorithmic aspects of distributed computing. The development may have a great potential in the telematics industry, but the DSP work does not yet reach engineers in that industry because "they speak a different language". There is now a book in the writing stage which may partially help to cure this problem. 2.3: PRAM Algorithms and Data Structures The development of the PAD library has been terminated at the end of the last review period due to the main investigator leaving the project. 4.1: Paros This workplan item suffered from a switch of the industrial partner and a corresponding new setting of its internal goals. Currently the partners are developing new methods in the areas of load balancing, data management in networks, BSP-algorithms and especially for using SCI-technology. This work has lead to a number of libraries easing the work of users who want to place their programs on supported parallel or distributed computer systems. A difficulty for a wide disssemination of the Paros developments is that the programming tools, in order to be efficient, need to take into account the specific hardware architectures and applications. 4.5: Computer Algebra and Combinatorial Models (LUO) The work in this area has continued to be at an excellent level and has led to a new package Encyclopedia of Combinatorial Structures on top of the Maple system and to extensions and increases of robustness, correctness and efficiency of various other Maple libraries developed within ALCOM-IT. The progress report is mentioning various cooperations with the Swiss partner from ETH Zürich. For the reviewers nevertheless there remained open questions concerning the cooperation with this partner. The main financial beneficiary of this project is presently Maple Inc., now at Waterloo, Ontario, Canada. The relationship with Maple Inc. should not be one-sided considering the practical commercial benefit to be gained from the ALCOM-IT funded developments of this Work Package. But the potential benefits received by the ALCOM-IT partners remained unclear. Management aspects and partnership cooperation The project as whole seems quite well-managed. There are many good signs of this, including the fact that almost all the planned deliverables were available at the end of the year. We appreciate the smooth management of this large project, and the substantial cooperation occurring among the partners, especially in consideration of the numerous participating sites and the wide spectrum of scientific areas that ALCOM-IT covers. The work of INRIA is seen by many partners as being extremely important as a general basis in the algorithm field; but the progress report does not show cooperations between INRIA and other partners on concrete ALCOM-IT targets. Dissemination and Take-up of Results Dissemination of project results and viewpoints was excellent, as is usual in the academic community. In particular, the products LEDA, ABACUS and the graph drawing libraries are spreading into a variety of user communities. This worthwhile effort should be maintained also in the future. We acknowledge the many books on ALCOM-IT developments which have been published or are in preparation, and we hope that they will further help in disseminating the results of this project. Concluding Statements We assess, without reservation, that the ALCOM-IT project has been a great success and having achieved its goals in full measure. The achievements have been impressive in all three areas of work: - in Foundations and Methods, it has brought together and demonstrated the leadership of the European algorithms community. - in Algorithms Software Libraries, it has developed several state-of-the-art products which have met commercial success. - in the Development of Software for Specific IT Demands, the project has conducted successful developments in collaboration with industry. ALCOM-IT has demonstrated that algorithms theory could be translated into efficient implementations which had practical industrial applications. Many ALCOM-IT developments, particularly in the Libraries area need to be pursued in some way or other, to keep the European momentum and leadership in the field. As was mentioned in several points above, in a possible successor project, some areas would significantly benefit from some refocussing. As already mentioned in previous reviews, a necessary improvement in a son-of- ALCOM-IT project would be to provide better quantitative evaluation of the impacts of better algorithms for the end-user applications. Also, in some areas, contacts with industrial users would need to be extended to provide more feedback as to where better algorithms are needed and what needs to be improved in the algorithms delivered by the project team. Many areas, some of them already addressed in part in ALCOM-IT, will continue to need practical combinatorial algorithms developments, among others: communications networks, mobile communications, Internet, the field of logistics, computational biology.