What is a Hostname?

A name is a label that is used to distinguish one thing from another. A person's name, for instance, comprises a set of alphabetic characters that allows a person to be individually addressed. Computers are also named to differentiate one machine from another and to allow for such activities as network communication.
Computers have always needed unique addresses to talk to each other. With the advent of the Internet, the requirements for enabling computers to communicate with each other on a network included the concept of the hostname. The hostname began as a simple string of alphanumeric characters (and possibly a hyphen) and has evolved to its current definition, where hostname means a Fully Qualified Domain Name (FQDN) that absolutely and uniquely identifies every computer hooked up to the Internet via the Domain Name Service (DNS) naming hierarchy.
The true "name" a computer needs in order to communicate on a network is actually a set of numbers. The original computers connected as the Internet used small integers as the host number. For TCP/IP, the main protocol used by the Internet, each computer has a network IP address that follows a specific set of rules to assure its uniqueness and validity. (Additionally, port numbers further specify the access points for particular services on a computer).
It has always been user friendly to associate a host name with a computer (while the computer maintained its internal numerical host number or network address). One of the initial Internet RFCs, "Standardization of Host Mnemonics" lists the table that associated host numbers with their corresponding host names for the first Internet computers. This table was kept in a file called HOST.TXT that was stored on every computer that wished to communicate.
While the original file was not so daunting at 20 entries, it became quickly apparent that this solution was not scalable or flexible enough as the number of host computers connected to the Internet exploded. In order to accommodate the problem of connecting all of the new computers being added to the Internet, a hierarchical database of host names was created called DNS. DNS associates host names with their IP addresses. A complete domain name (that is, an FQDN) includes the name of the host concatenated with its domain name. This naming convention allows for a hierarchy of domain names with the host name being the most specific (and "left-most") part.
The rules for a host name were first standardized in the original host name specification, "DoD Internet Host Table Specification". It states that the name should be a text string consisting of the letters A through Z (upper or lower case), digits 0 through 9, the minus sign (-), and the period (.). Note, the period is only allowed as the last character of the host name if it is the delimiter of the full domain name (FQDN). No spaces are permitted as part of a name. The first character must be an alphabetic character and the last character must not be a minus sign or period. It was also recommended that the host name be no longer than 24 characters in length. Subsequently, in "Requirements for Internet Hosts - Application and Support", the host name rules were updated. The first character could now be either a letter or a digit and software dealing with host names must handle names up to 63 characters in length.
In common usage today, hostname refers specifically to the FQDN that comprises the name of the host, a period, and the domain name. The domain name is composed of labels that begin with the top-level domain and are arranged right to left for the second and, possibly, third level labels. The host name and the domain labels are separated by periods. The total length of the hostname as an FQDN cannot exceed 255 character with each domain name label having a maximum length of 63 characters. For example, if a company's domain name is "example.com." and a particular computer in the company has been named "plato", the hostname for that computer will be "plato.example.com.". Note, that technically FQDNs end in a period to unambiguously define the hostname and to be sure that it is not part of a longer domain name. (although in common usage this final period is often omitted).
The exact rules for the new hostname definition that has evolved is also more rigorous than that of the related original host name specification. The DNS naming rules are explained in "Domain Names - Concepts and Facilities", "Domain Names - Implementation and Specification", and "Clarifications to the DNS Specification".
To summarize, a hostname is a Fully Qualified Domain Name that uniquely and absolutely names a computer. It is composed of the host name and the domain name. The domain name in turn is one or more domain labels that place the computer in the DNS naming hierarchy. The host name and the domain name labels are separated by periods and the total length of the hostname cannot exceed 255 characters.
Now that the syntax of the name of the host as part of the hostname is understood, how does one choose a good name for their computer? Several web sites offer suggestions and the choice is up to the system administrator whose whimsy is only limited to the fact that no two computers in one domain space can have the same host name (because the two computers would have the same hostname!).
RFC 1178, "Choosing a Name for Your Computer" contains several guidelines on how to name - and how not to name - your computers.
A summary of sample guidelines for good host names:
Use words/names that are rarely used.
Use theme names.
Use real words.
Don't worry about reusing someone else's hostname.
There is always room for an exception.
And some sample guidelines for not so good host names:
Don't overload other terms already in common use.
Don't choose a name after a project unique to that machine.
Don't use your own name.
Don't use long names.
Avoid alternate spellings.
Avoid domain names.
Avoid domain-like names.
Don't use antagonistic or otherwise embarrassing names.
Don't use digits at the beginning of the name.
Don't use non-alphanumeric characters in a name.
Don't expect case to be preserved
As a final note, the terms "host name" and "hostname" are often used interchangeably, so be sure to clarify when the term is being used as to whether just the name of the host or the computer's FQDN is being referenced. To see this on a Linux system, by example, the hostname command returns the FQDN while adding the -s option (i.e., hostname -s) returns just the name of the host.