O caminho mais simples seria usar o mDNS para fazer a resolução de DNS "ad-hoc" entre as máquinas no mesma sub-rede. Isto é, basicamente, tão simples quanto instalar avahi-daemon e libnss-mdns (nomes de pacotes Debian; ajustar conforme apropriado) e assegurar que seu firewall não esteja bloqueando 5353/udp . Isso abrangerá as entradas DNS diretas e reversas e criará nomes resolvíveis do formulário <hostname>.local para todas as outras máquinas na sub-rede local.
Se você precisar de uma nomenclatura disponível além do domínio multicast local, provavelmente desejará configurar um servidor DNS em algum lugar da Internet que aceite TSIG -authenticated UPDATE queries e, em seguida, configure as máquinas clientes para enviar atualizações usando nsupdate (ou algum outro meio equivalente).