Nu'aym recaptured Hamadan after a bloody battle, and then proceeded to Rey. There too the Persians resisted but were defeated outside the fort, and the Muslims recaptured the city. The Persian citizens sued for peace, agreeing to pay the Jizya. From Rey, Nu'aym moved north to Tabaristan, south of the Caspian Sea. The ruler of Tabaristan then signed a peace treaty with the Caliphate. Conquest of Fars First Muslim invasion and the successful Sasanian counter-attack The Muslim invasion of Fars began in 638/9, when the Rashidun governor of Bahrain, al-'Ala' ibn al-Hadrami, having defeated some rebellious Arab tribes, seized an island in the Persian Gulf. Although al-'Ala' and the rest of the Arabs had been ordered to not invade Fars or its surrounding islands, he and his men continued their raids into the province. Al-'Ala quickly prepared an army which he divided into three groups, one under al-Jarud ibn Mu'alla, the second under al-Sawwar ibn Hammam, and the third under Khulayd ibn al-Mundhir ibn Sawa. When the first group entered Fars, it was quickly defeated and al-Jarud was killed. The same thing soon happened to the second group. Khulayd and the third group kept the defenders at bay, but were blocked from withdrawing to Bahrain by the Sasanians. Umar, having found out about al-'Ala's invasion of Fars, had him replaced with Sa'd ibn Abi Waqqas as governor. Umar then ordered Utbah ibn Ghazwan to send reinforcements to Khulayd. Once the reinforcements arrived, Khulayd and some of his men managed to withdraw to Bahrain, while the rest withdrew to Basra. Second and last Muslim invasion In ca. 643, Uthman ibn Abi al-As seized Bishapur, which signed a peace treaty. In 644, al-'Ala' once again attacked Fars from Bahrain, reaching as far as Estakhr, until he was repulsed by the Persian governor (marzban) of Fars, Shahrag. Some time later, Uthman ibn Abi al-As managed to establish a military base at Tawwaj, and soon defeated and killed Shahrag near Rew-shahr. Persian convert to Islam, Hormoz ibn Hayyan al-'Abdi, was then sent by Uthman ibn Abi al-As to attack a fortress known as Senez on the coast of Fars. After the accession of Uthman ibn Affan as the new Rashidun Caliph on 11 November, the inhabitants of Bishapur, under the leadership of Shahrag's brother, declared independence, but were defeated. The Persian historian al-Baladhuri said this occurred in 646. In 648, 'Abd-Allah ibn al-'Ash'ari forced