O comando dpkg -S
sugere que seja de coreutils
anwar@anwarpc:~$ dpkg -S $(which tail)
coreutils: /usr/bin/tail
Verifique também dpkg -L
anwar@anwarpc:~$ dpkg -L coreutils | grep tail
/usr/bin/tail
/usr/share/man/man1/tail.1.gz
coreutils
vem pré-instalado, por isso já estava lá. Como o nome sugere, esses são core para qualquer sistema linux.