He entrusted its conquest to the 70-year-old "qadi", Asad ibn al-Furat. The Muslim force numbered 10,000 infantry, 700 cavalry, and 100 ships, reinforced by the fleet of Euphemius and, after the landing at Mazara del Vallo, by knights. The first battle against Byzantine troops occurred on July 15, 827, near Mazara, resulting in an Aghlabid victory. Asad subsequently conquered the southern shore of the island and laid siege to Syracuse. After a year of siege and an attempted mutiny, his troops were able to defeat a large army sent from Palermo backed by a Venetian fleet led by doge Giustiniano Participazio. However, the Muslims retreated to the castle of Mineo when a plague killed many of their troops and Asad himself. They later returned to the offensive but failed to conquer Castrogiovanni (the modern Enna, where Euphemius died), retreating back to Mazara. In 830, they received a strong reinforcement of 30,000 African and Spanish troops. The Spanish Muslims defeated the Byzantine commander Theodotus in July and August of that year, but a plague once again forced them to return to Mazara and then to Africa. The African Berber units sent to besiege Palermo captured it in September 831 after a year-long siege. Palermo, renamed al-Madinah, became the Muslim capital of Sicily. In February 832, Ziyadat Allah sent his cousin Abu Fihr Muhammad ibn Abd-Allah to the island and appointed him as the "wāli" of Sicily. He defeated the Byzantines in early 834, and in the following year his troops reached as far as Taormina. The war dragged on for several years with minor Ahglabid victories, while the Byzantines resisted in their strongholds of Castrogiovanni and Cefalù. New troops arrived in the island from the new Emir Al-Aghlab Abu Affan and occupied Platani, Caltabellotta, Corleone, Marineo, and Geraci, granting the Muslims total control of western Sicily. In 836, Muslim ships helped their ally, Andrew II of Naples, when he was besieged by Beneventan troops, and with Neapolitan support Messina was also conquered in 842 by Muhammad Abul Abbas of Sicily, who later established the Emirate of Bari. In 845, Modica also fell, and the Byzantines suffered a crushing defeat near Butera, losing about 10,000 men.