This paper presents TrickleDNS, a decentralized system for proactive dissemination of DNS data. Unlike prior solutions, which depend on the complete deployment of DNSSEC standard to preserve data integrity, TrickleDNS offers an incrementally deployable solution with a probabilistic guarantee on data integrity that becomes stronger as the adoption of DNSSEC increases. TrickleDNS provides resilience from data corruption attacks and denial of service attacks, including sybil attacks, using three key steps. First, TrickleDNS organizes participating nameservers into a well-connected peer-to-peer Secure Network of Nameservers (SNN) using two types of trust links: (a) strongly trusted social relationships across DNS servers (which exist today); (b) random yet constrained weak trust links between DNS servers, which it introduces. The SNN allows nameservers in the network to reliably broadcast their public-keys to each other without relying on a centralized PKI. Second, TrickleDNS reliably binds domains to their authoritative name servers through independent verification by multiple, randomly chosen peers within the SNN. Finally, TrickleDNS servers proactively disseminate self-certified versions of DNS records to provide faster performance, better availability, and improved security.