Embodiments of the invention are directed assessing reliability between two computing devices. A distributed database may maintain reliability associations between pairs of computing devices. Each reliability association may indicate a particular device has determined (e.g., locally) that another device is reliable. In order to determine an amount of reliability between a first computing device and a second computing device, an ordered combination of the reliability associations may be determined utilizing the distributed database. The ordered combination of reliability associations may identify a reliability path between the first computing device and the second computing device. An amount of reliability may be determined based on the reliability path. An interaction between the devices may be allowed or restricted based at least in part on the amount of reliability between the computing devices.