Distributed Data and Structures Records of the 2nd International Meeting Introduction This volume contains the records of the 2nd Research Meeting on Distributed Data and Structures. sponsored by DIMACS under the auspices of the special year on Massive Data Sets, it was held at Princeton University on May 10-11, 1999. This year's workshop continues the series successfully started with WDAS '98, which was held in Orlando as a satellite workshop of IPPS '98. Currently, the research on distributed data structures is carried out in many fields, from parallel systems to distributed computing, from AI to GIS. Their systematic design and analysis has just started: in the database literature, dynamic file structures for distributed object management have attracted some attention, and in the algorithms literature, data structures have been studied from a complexity oriented point of view. However, this research is mostly ``hidden,'' relegated to the side of each field, obscured by the weight of the application domain, especially in databases but also in the algorithms community. In fact, there is not even a definitive acceptance of its existence as a research field. This is surprising, especially in the light of the following two important developments. 1. As databases steadily grow, applications become more and more demanding, and distributed computer systems become rather easily available, the problem of how to efficiently maintain large datasets gains importance. An important aspect of this problem is the design, implementation, and operation of a data structure in a distributed system. 2. At the same time, in the constantly expanding net-centric universe, an increasing amount of data becomes available, distributed among many sites. The structuring of the data for access, manipulation, and processing is a crucial task that can ultimately affect the performance, integrity, and usefulness of the entire system. These two developments bring the research on distributed data and structures to the forefront. The absence of a specific focus on this subject is an anomaly in the status of the current research efforts; at the same time, this situation opens an exceptional opportunity for researchers. The purpose of this meeting on Distributed Data and Structures was to bring together application-oriented developers and theoretical researchers, who are concerned with the maintenance of distributed data and the organization of the interaction among computing nodes, along with researchers from different but related backgrounds. These participants have set as their goal the ``defining'' of the field across all the application areas. This involves assessing and characterizing the common elements in all the unco-ordinated research efforts that have been carried out in so many different domains, and to ``visualize'' the field with respect to new computing paradigms (e.g., mobile, wireless, etc.). The meeting was successful in both respects. It comprised of both formal presentations, with the idea of giving a picture of some aspects of the field, and open time and space to discuss, analyze, and characterize the many facets of the field. This year the program included 18 presentations, either invited or contributed in response to the call for papers. A large majority of the talks addressed issues related to the design, analysis, implementation, application, and testing of distributed data structures. Other topics covered were algorithms and data allocation problems for parallel disk systems, novel interconnection structures, and basic algorithmic primitives of distributed computing. This volume is based entirely on the talks, discussions, and results of the meeting. Its small size is due to the fact that most of the contributions came as discussion and have not yet found their form as a written text. Still, we hope this volume will convey to the reader at least part of the interest, excitement and visions experienced by the participants. We are confident it will provide useful tools for a unified view of this emerging research area, so important from both an applicative and a theoretical viewpoint. We would like to thank all the participants to the meeting for their enthusiasm and contributions, DIMACS for their strong support, Princeton University for proiding the local organization, Konrad Schlude for the excellent organizational work, and Steve Izma for his editorial efforts. We also gratefully acknowledge the support of the two parent institutions: Carleton University and ETH Zurich. - Yuri Breitbart, Sajal K. Das, Nicola Santoro, and Peter Widmayer