This is a quasi-review paper which defines and then places Computational Air Traffic Management (CATM) in a historical context. CATM is presented as the natural convergence of many, seemingly disparate, air traffic technologies that have evolved over the past two decades. It is the emergent order which is derived from the collective behaviour of a number of interacting systems. A distinction is initially made between strategic air traffic management (ATM) and tactical air traffic control (ATC). This distinction ebbs in CATM and the intimately intertwined relationship between ATM and ATC is accentuated. The features of an ideal ATC system are discussed and developed objectively in contrast to current systems. The requirements are based on a high level top-down approach, but also look at the time-proven characteristics that allow the current ATC system to function so surprisingly well. An inventory of the interesting research questions in the overall CATM picture is therefore gradually drawn-up along the discussion to indicate areas with insufficient research coverage. In the second part of the paper, a clean sheet approach for devising an operational concept for a streamlined CATM system is proposed and discussed. This example describes an airborne, decentralized, fault-tolerant paradigm for a continental (and perhaps global) ATC system that readily scales up (perhaps linearly) to accommodate projected future aircraft densities. The system is broadly consistent with the proposed objectives as put forward in both NextGen (Next Generation Air Transportation System) and SESAR (Single European Sky ATM Research). Practical algorithms for several subsystems are classified, and discussed in the context of emerging computational hardware. The case is then made for a new breed of grid-oriented avionics hardware that will enable aircraft to take CATM to the skies by leveraging on the many benefits brought by pervasive inter-aircraft ad-hoc communication networks and heterogeneous, high performance grid-computing.