I'm working on a large network of servers sitting on EC2, and need a way for the servers to know about each other's locations in the cloud. I thought the simplest way would be to use DNS, because if I replace the EC2 instance, I simply update the DNS record, and the rest of the servers will know about it (with names like users.db.mysoft.com, routing.mysoft.com, cluster1.memcached.mysoft.com). I'm considering setting up a master DNS server on a micro/small instance to accommodate this.

I'd preferably need something that's as simple as a key-value store (hostname -> IP) into which the platform could remotely add/remove entries. Can I do this with BIND? Or is there a better solution?