  This paper explores a simple question: How would we provide a high-quality
search experience on Mars, where the fundamental physical limit is
speed-of-light propagation delays on the order of tens of minutes? On Earth,
users are accustomed to nearly instantaneous response times from search
engines. Is it possible to overcome orders-of-magnitude longer latency to
provide a tolerable user experience on Mars? In this paper, we formulate the
searching from Mars problem as a tradeoff between "effort" (waiting for
responses from Earth) and "data transfer" (pre-fetching or caching data on
Mars). The contribution of our work is articulating this design space and
presenting two case studies that explore the effectiveness of baseline
techniques, using publicly available data from the TREC Total Recall and
Sessions Tracks. We intend for this research problem to be aspirational and
inspirational - even if one is not convinced by the premise of Mars
colonization, there are Earth-based scenarios such as searching from a rural
village in India that share similar constraints, thus making the problem worthy
of exploration and attention from researchers.
