Distributed Data and Structures Records of the 4th International Meeting Introduction Les données et les structures distribuées ont un rôle majeur en Informatique moderne. Les progrès dans cette direction sont essentiels pour l'amélioration des performances et du dimensionnement, tant des systèmes de stockage et de gestion des bases de données actuels que des systèmes émergents tels que ``  P2P  '' ou des grilles d'ordinateurs. Le séminaire WDAS 2002 a fourni l'occasion de faire l'état des recherches et réalisations dans ce domaine : y étaient abordés non seulement les aspects théoriques fondamentaux, mais aussi de nouvelles méthodes d'accès et plusieurs prototypes. WDAS 2002 est le quatrième Séminaire d'une série. Les précédents se sont tenus à Aquila (Italie, 2000), Princeton (1999) et Orlando (1998). Le programme scientifique de WDAS 2002 comprend 17 articles, qui ont été retenus parmi les 35 qui ont lui été soumis. Le Docteur Jim Gray, Directeur du Centre de Recherches de Microsoft à Bay Area, et lauréat du prix Turing 1998, était le conférencier invité du Colloque. Il a parlé d'un projet de télescope panoramique virtuel, capable d'intégrer les vues réelles prises par de multiples télescopes. Les exposés et discussions ont été suivis d'une session de posters, au cours de laquelle ont été effectuées des démonstrations de prototypes, qui préfigurent les prochains logiciels. WDAS-2002 a également comporté une session de présentations par résumé étendu et une session de démonstrations de prototypes. Le CERIA a présenté notamment son système SDDS-2000 : un gestionnaire de Structures de Données Distribuées et Scalables pour un réseau local de stations de travail Win NT, 2000 et XP. Ce prototype est gratuit pour un usage non-commercial. Il est disponible pour téléchargement à http://ceria.dauphine.fr/. La deuxième démonstration concernait la SDDS LH*$_{RS, }$qui fournit une haute disponibilité scalable de données à travers l'utilisation des codes Reed Salamon. Le but de WDAS 2000 était principalement de discuter en profondeur les travaux présentés. Ainsi, 45 minutes ont été consacrées pour chaque participant afin de présenter son article, en plus des 15 minutes réservées pour les discussions. Pour cette raison également, que nous n'avons pas prévu de sessions parallèles, et nous avons limité l'assistance à 40 participants. Les badges des participants indiquaient notamment leurs domaines des recherches et leurs données de contact: émail et la page Web personnelle. Les résumés étendus des communications présentées ont été publiées dans les actes du séminaire distribuées aux participants. La procédure de sélection a été fondée sur les recommandations par les présidents de sessions des présentations qui ont tenu également compte des commentaires des participants. Ces derniers exprimaient leurs avis en remplissant des formulaires de revue. Les résumés étendus publiés dans les actes de WDAS-2002 sont également disponibles sur le site du CERIA précité. Le séminaire WDAS 2002 n'aurait certainement pas pu être organisé sans l'aide et l'appui de nombreuses personnes et institutions. Nous tenons à remercier particulièrement Monsieur le Professeur Bernard de Montmorillon, Président de l'Université Paris Dauphine, Monsieur le Professeur Vangelis Paschos, vice - Président, responsable du Conseil Scientifique de notre Université, Monsieur Yves Gauffriau, Conseiller auprès de l'Ambassade de France au Sénégal, Monsieur Pierre-Yves Santoyant, responsable des relations entre Microsoft et les Universités. Nous adressons également tous nos remerciements aux membres du comité de programme et du comité d'organisation, et enfin à tous les chercheurs du CERIA. Les organisateurs : Pr. Gérard Lévy et Pr. Witold Litwin. Distributed data and structures are the basis of the modern computer science. Advances in the domain are fundamental to performance and scalability of various types of storage and database systems, as well as to emerging P2P and Grid Computing technologies. The WDAS workshops examine the state-of-the-art in the area: fundamental theoretical advances, access methods, prototypes and applications. WDAS-2002 is the 4th workshop in the WDAS series. Previous workshops took place in Aquilla (Italy, 2000), Princeton (1999) and Orlando (1998). The WDAS-2002 scientific program included 17 presentations selected from 35 submissions. Doctor Jim Gray, the 1998 recipient of the ACM Turing Award, leading the Bay Area Microsoft Research Center, delivered the Keynote Address. His talk featured the fascinating problem of building a worldwide virtual telescope. This tool aims on merging data from a large number of observation points to provide yet untapped viewing power. Few years back, it was just a science fiction. With the progress in our domain it will soon be the reality. WDAS-2002 also featured the poster session with abstracts in the proceedings and demos. The session was intended as the forum for the discussion between the authors and the interested participants. The demos showed prototypes and algorithms for the management of various Scalable Distributed Data Structures. In particular, CERIA presented its SDDS-2000 system for local networks of Windows NT, 2000 and XP workstations. This prototype is free for non-commercial download at its Web site http://ceria.dauphine.fr/. Another demonstration featured variants of LH*$_{RS}$ SDDS scheme. This scheme provides the scalable high-availability of its data server sites through novel erasure correction codes. Finally, the session included the presentation of the trie hashing based schemes for the scalable distributed range partitioning. These schemes achieve particularly compact indexing which potentially allows in turn for a very large number of the data server nodes supporting the SDDS. For us, the opportunity of ample discussions is the main goal of a workshop. We aimed the WDAS-2002 organization at this purpose. The time for a paper presentation time was longer than usual, being of 45 min. with ample 15 min for the discussions, instead of total 30 min. for a typical conference. This was also why we have avoided parallel sessions. We have also limited the attendance under 40 participants. The badges displayed also the participants' research domains and contact data: the email and the web page especially. The papers were published at the workshop by extended abstract only. The full papers, including the Keynote speech, appear in this volume. The selection process was based on the presentation reviews by Session Chairs. They were helped by the review forms at the audience free disposal. The PC made the final choice. The extended abstract of all the papers, included from the poster session remain available at the CERIA site http://ceria.dauphine.fr/. The WDAS-2002 was possible only because numerous persons joined their forces. We thank Jim Gray for accepting our invitation. We are also grateful to the Program Committee members for their time devoted to numerous reviews. Likewise, we thank the Organizing Committee members for their commitment to set up the workshop to the best of their ability. The WDAS-2002 workshop was made possible also through the support of Dauphine University provided by its Conseil Scientifique. We thank the President of the University, Professor Bernard de Montmorillon, and the Vice-President, Professor Vangelis Paschos, head of Conseil Scientifique. We also thank Le Conseiller Scientifique Yves Gauffriau from La Mission Mission Culturelle Française in Dakar for the contribution to the travel support of participants from Senegal. Microsoft Research also provided the support for the workshop, in the wake of its long lasting commitment to help the SDDS research at CERIA. We thank Dr. Pierre-Yves Saintoyant, Director of Microsoft Research University Relations for this effort. The Academia and the Industry joining their efforts in our domain in this way, we believe that its practical use is coming soon. The organizers : Prof. Witold Litwin, Prof. Gérard Lévy Table of Contents for Distributed Data 4