There is a folk-tale still told in Tiree of how an islander, when crossing the machar near Kennavarra, came within sight of [a cu sith, or fairy dog] crouching by a sand-dune, and immediately altered the direction in which he was making for home. Reflecting on this sinister spectacle the following morning, he resolved to put his courage to the test, and re-visit the sand-dune. Upon the sand at this point he discovered the imprints of a dog's paws, "as large as the spread of his palm." The imprints he traced for some distance, until they came to an end. He saw no dog anywhere, nor any beast likely to have left marks of this kind; and so he concluded that the object he had seen the previous evening was not of earthly origin, and must have been a faery dog.
From The peat-fire flame by Alasdair Alpin MacGregor (1937). As he explains, they are a creature of ill omen and move swiftly and noiselessly. They bark three times, 'and there is usually a fair interval between each bark, which gives to the terror-stricken hearer a chance of making for safety before he hears the third bark. Otherwise he is liable to be overtaken and destroyed by the faery dog'. Just to warn you.
Canmore's record for the fort (in the area of Ceann a' Mhara) is here.