In computer networks with decentralized control, it is necessary to provide a directory service which enables users to discover dynamically the location of other users. In this paper, we examine the protocols for maintaining consistent directory information for "casually connected" users that may connect and disconnect from the network at will. We propose for both hierarchical and nonhierarchical directory systems. Our protocols do not rely on sequence numbers or time-stamps and do not require "safe store" at the user. We propose a definition of correctness in such an environment and prove that our protocols achieve this definition. © 1990.