  Locating data efficiently is a key process in every distributed data storage
solution and particularly those deployed in multi-site environments, such as
found in Cloud and Fog computing. Nevertheless, the existing protocols
dedicated to this task are not compatible with the requirements of the
infrastructures that underlie such computing paradigms. In this paper, we
initially review three fundamental mechanisms from which the existing protocols
are used to locate data. We will demonstrate that these mechanisms all face the
same set of limitations and seem to have a trade-off in three distinct domains
of interest, namely, i) the scalability, ii) the ability to deal with the
network topology changes and iii) the constraints on the data naming process.
After laying out our motivation and identifying the related trade-offs in
existing systems, we finally propose a conjecture (and provide a proof for this
conjecture) stating that these three properties cannot be met simultaneously,
which we believe is a new fundamental trade-off the distributed storage systems
using the three fundamental mechanisms have to face. We conclude by discussing
some of the implications of this novel result.
