A number of studies have shown the abundance of unused spectrum in the TV bands. This is in stark contrast to the overcrowding of wireless devices in the ISM bands. A recent trend to alleviate this disparity is the design of Cognitive Radios, which constantly sense the spectrum and opportunistically utilize unused frequencies in the TV bands. In this paper, we introduce the concept of a time-spectrum block to model spectrum reservation, and use it to present a theoretical formalization of the spectrum allocation problem in cognitive radio networks. We present a centralized and a distributed protocol for spectrum allocation and show that these protocols are close to optimal in most scenarios. We have implemented the distributed protocol in QualNet and show that our analysis closely matches the simulation results.