How can I discover the hostnames for all the machines on my lan?

Solution 1:

Avahi tools

There also are tools from the Avahi package to list services.

  • avahi-browse (from avahi-utils)
    Command line tool that browses the network for any services used by Avahi.

      avahi-browse -at
    
  • avahi-discover
    Is a GUI to display all Avahi services available:

    enter image description here

Solution 2:

nbtscan

A good tool to scan all hostnames on a network is nbtscan.

$ nbtscan 192.168.1.0/24                                                                                                  
Doing NBT name scan for addresses from 192.168.1.0/24

IP address       NetBIOS Name     Server    User             MAC address      
------------------------------------------------------------------------------
192.168.1.0     Sendto failed: Permission denied
192.168.1.162    CLEMENTINA          <server>  CLEMENTINA          00:00:00:00:00:00
192.168.1.205    CLEMENTINA          <server>  CLEMENTINA          00:00:00:00:00:00
192.168.1.255   Sendto failed: Permission denied
  • Note: This is for NetBIOS, not for mDNS.
  • Official site

You can install it in the Software Center by searching for 'nbtscan', through their website, or via Terminal:

sudo apt-get install nbtscan