SToN: A New Fundamental Trade-off for Distributed Data Storage Systems

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.