The concepts around which mDNS and DNS-SD/zeroconf revolve are simple: some devices offer services on a network, and by broadcasting their names and services, other machines on the network can access with their name.
This has the practical advantage of a "Plug and Play" method: there's no need to find out one computer's IP Address anymore. Services can be accessed by name. You may know these protocols by the name of Zeroconf.

Enter Avahi, the Linux daemon which controls service publishing and discovery. Avahi's standard configuration for Debian- and Ubuntu-based Linux distributions is highly problematic, since it broadcasts the machine name (service type _workstation._tcp) on each network it is connected to, even if no actual service is published or wanted.

This behavior can be easily exploited, in order to map a network or profile and track users joining a network or even receive a passive portscan, for the sake of a feature that not many users need anyway.

If you feel this is wrong you can still disable the publishing options from /etc/avahi/avahi-daemon.conf.
Be sure that the following parameters of the [publish]section are configured this way:

[publish]
# Do not publish a record with this machine's name.
publish-workstation=no

# Disable the broadcast of OS and CPU information
publish-hinfo=no

# Disable the broadcast of the local IP addresses
publish-addresses=no

# Disable the broadcast of the locally used domain name
publish-domain=no

# If enabled, no user service will ever be published
disable-user-service-publishing=yes

# The safest option, puts Avahi in a browse-only mode
disable-publishing=yes

Note that enabling the highlighted options (lines 15 and 18) could mean the disruption of mDNS services, since no services would be published. If you don't plan to use your linux box as a server and know your own IP address, you should be fine.

Not enough

You have successfully disabled mDNS services and maybe Avahi itself, and yet there's another commonly used service which boradcasts your hostname too.

I'm talking about DHCP, of course. The standard configuration on Ubuntu/Debian systems broadcasts your hostname as soon as you join a network as well. Luckily, you can prevent dhclient from broadcasting your hostname too.