Overlay networks are logical networks embedded in physical substrate networks. They are useful for supporting specialized applications involving computation and information exchange among subsets of users. This paper examines the characteristics of overlays that make them suitable for different applications in dynamic, distributed database environments. One such characteristic is the ease with which distances between nodes can be calculated. Examples of overlay graph structures that exhibit certain desirable characteristics include the hypercube, toroidal grid graph and the Kautz graph. Applications involving mobile elements are examined, and a system designed to support comparative analysis of the performance of different overlay structure...