During the period of the decay of the Abbasid Khalifate the Fatimids were able to seize an important part of the Abbasid dominions and make themselves rulers of Palestine and Syria, with more or less intermittent control over Arabia. At this time the three leading powers in the Near East were the Khalifate of Baghdad, the Fatimid Khalifate of Egypt, and the Byzantine Empire, but of these three the Fatimid Khalifate of Egypt was the most vigorous and aggressive. Under Karl the Great the Western Empire had assumed a kind of protectorate over the Christians in Palestine, but in Fatimid times this had become obsolete. The two rival Khalifates were separated by a wide gulf of religious difference, how wide cannot be appreciated without following the history of the formation and development of the Fatimid Khalifate. Both made overtures to the Greeks, but the relations of Byzantium with the Muslim world generally turned on questions connected with Fatimid rule: Fatimids and Greeks faced one another in North West Syria, and it was only in Sicily that the Greeks had to deal with the Baghdad Khalifate. Before the beginning of this period Crete which had fallen into the hands of the Muslims in A.D. 825, was recovered (in A.D. 961): Sicily, conquered by the Muslims between A.D. 827 and 878, remained in their hands but, after the Fatimid conquest of North Africa it revolted and gave in its allegiance to the Khalifate of Baghdad. North Africa was divided amongst various Muslim groups, and Spain was fully occupied with its own problems. In A.D. 1038 Byzantium lost control over North Syria, so that on the whole the Greeks were receding before the Muslims. In A.D. 1029 (= A.H. 419) there was, however, a _modus vivendi_ reached between the Fatimids and the Greeks by which, in return for help during famine, the Muslims were allowed to have a mosque in Constantinople provided prayer was offered there for the Fatimid Khalif, and, apparently, the Christians were allowed freedom to visit Jerusalem. The persecution of Christians under Hakim had culminated in the destruction of the church of the Holy Sepulchre in A.D. 1009, but this was re-built soon afterwards: the persecution was an isolated incident: in Muslim lands generally neither Christians nor Jews suffered any serious disabilities, the penal laws were long obsolete, and the only penalty enforced was against a Muslim who became a convert to another religion. An additional tax had to be paid by non-Muslims, but this was in lieu of military service from which they were exempt.