In the vision of ubiquitous computing, there are billions of context sources that continuously publish their contextual information, and even more user agents that search for and consume such information. These context producers and consumers form a largescale, wide-area, context-aware network which is both dynamic and heterogeneous. Existing service discovery mechanisms do not address the unique challenges imposed by such environments. In this paper we identify these challenges and propose a large scale context service discovery infrastructure for contextaware computing. We describe an approach for context service discovery and description that addresses these challenges.