I think it would be possible for BitDNS to be a completely separate network and separate block chain, yet share CPU power with Bitcoin. The only overlap is to make it so miners can search for proof-of-work for both networks simultaneously.
The networks wouldn't need any coordination. Miners would subscribe to both networks in parallel. They would scan SHA such that if they get a hit, they potentially solve both at once. A solution may be for just one of the networks if one network has a lower difficulty.
This sounds very very interesting, something to explore.
Can you elaborate on how would it work in practice? Separate networks and block chains implies hashing one block header for each network, with different resulting hashes, does it not?
The only thing I can come up with is the completely naive and slightly cache-unfriendly implementation...
while (nonce < 0xffffff)
nonce++
for each network
data_block[nonce_offset] = nonce // ie. our nonce
scanhash(data_block)
or
for each network
while (nonce < 0xffff)
data_block[nonce_offset]++
scanhash(data_block)
I could easily update cpuminer to poll multiple RPC endpoints for 'getwork'...