The dates and circumstances of the end of Byzantine rule in Sardinia are not known. Direct central control was maintained at least through c. 650, after which local legates were empowered in the face of the rebellion of Gregory the Patrician, Exarch of Africa and the first invasion of the Muslim conquest of the Maghreb. There is some evidence that senior Byzantine administration in the Exarchate of Africa retreated to Caralis following the final fall of Carthage to the Arabs in 697. The loss of imperial control in Africa led to escalating raids by Moors and Berbers on the island, the first of which is documented in 705, forcing increased military self-reliance in the province. Communication with the central government became daunting if not impossible during and after the Muslim conquest of Sicily between 827 and 902. A letter by Pope Nicholas I as early as 864 mentions the "Sardinian judges", without reference to the empire and a letter by Pope John VIII (reigned 872–882) refers to them as "principes" ("princes"). By the time of "De Administrando Imperio", completed in 952, the Byzantine authorities no longer listed Sardinia as an imperial province, suggesting they considered it lost.