Você precisa fornecer uma maneira de resolver nomes. Isso significa que eu) preencha /etc/hosts , ii) defina os nomes de host em seu servidor DNS (o que não requer que você instale um servidor DHCP) ou iii) use DNS de multidifusão. Então, tecnicamente sim, é possível configurar a resolução de nomes sem usar o nmap, instalando um servidor DHCP ou um avahi (basta inserir os registros em um servidor DNS ou preencher /etc/hosts ).
A solução mais simples é instalar avahi e libnss-mdns em todas as máquinas. Depois você deve poder acessá-los via $ hostname.local