A couple of years ago I read a great sci-fi book... one of the characters needed to leave msg that she knew would not be read for millions of years. She carved the msg in stone.

It was read millions of years into the future, the rocks buried deeply in the soil.

With all the tech they had at their disposal, carving a rock was the only thing that made sense.