There is provided a distributed database system comprising a plurality of participating nodes mutually interconnected via a communication network. The participating nods include a first subset of storage nodes and a second subset of interfacing nodes. The storage nodes are grouped into a plurality of slots, each storage node having stored therein addresses of substantially al other storage nodes in its particular slot. The storage nodes of each slot further have stored therein one or more addresses of storage nodes in all other of the slots of the system. The interfacing nodes each have stored therein addresses of one or more of the storage nodes. The storage nodes are operable to store one or more data records therein and/or retrieve one or more data records therefrom in response to instructions received from the interfacing nodes. The system is coordinated in operation in a decentralised manner.