A recent article in Nano Letters describes an experimental nanotechnology-based storage device that could last for a billion years and store up to one terabyte per square inch.
Read more about it at "New Memory Material May Hold Data For One Billion Years."
