Byzantium Distributed DNS
From HacDC Wiki
CJDNS - True DNS (i.e., port 53/UDP) with a DHT. I've played around with it a little and it seems to do what it says on the tin.
Distributed Hash Table (DHT) - Wikipeda page on DHTs. Has a decent overview of how they work.
Bamboo DHT - A DHT implementation in Java.
UpRight - A library for building fault-tolerant distributed systems. Incorporates innovations from modern solutions to Byzantine fault tolerance.
Gossip Protocols: Nodes in a network pseudorandomly select peers to exchange information with. Could be useful for distributing the contents of a DHT-based DNS implementation within a mesh network. Kademlia has an interesting way of handling the entry distribution problem. When inserting an entry, it iterates through the table to find suitable nodes in the network to hold that entry and propagates it to them as well as saving a copy locally.
CoDoNS paper - A very good paper from 2004 on a distributed DNS alternative. It still relies on centralized domain name registration. CoDoNS main page - It appears that CoDoNS is operational and running on PlanetLab. Unfortunately, I don't see any code. I see no reason why we can't simply hijack their design.
Intentional Naming System - "INS is a new naming system intended for naming and discovering a variety of resources in future networks of devices and services. It has the following interesting characteristics about the way it names resources and the way names are resolved."