OMG CORBA applications require a distributed naming service in order to install and to retrieve object references. High availability of the naming service is important as most CORBA applications need to access it at least once during their lifetime. Unfortunately, the OMG standards do not deal with availability issues, and the naming services of many of the commercially available CORBA object request brokers introduce single points of failure. In this paper we describe the design and implementation of a replicated, highly-available CORBA name server that adheres to the OMG Common Object Services Specification. Our naming service can be replicated at run-time, while many applications are installing and retrieving object references. We compare our approach with the approaches taken by the ILU, NEO, Orbix, and DOME object request brokers. The performance of our name server is measured for various replication degrees.