Dhu Nuwas left two inscriptions, neither of them making any reference to fiery pits. Byzantium had to act or lose all credibility as protector of eastern Christianity. It is reported that Byzantium Emperor Justin I sent a letter to the Aksumite King Kaleb, pressuring him to "attack the abominable Hebrew". A tripartite military alliance of Byzantine, Aksumite and Arab Christians successfully defeated Yousef around 525–527 and a Christian client king was installed on the Himyarite throne. Esimiphaios was a local Christian lord, mentioned in an inscription celebrating the burning of an ancient Sabaean palace in Marib to build a church on its ruins. Three new churches were built in Najran alone. Many tribes did not recognize Esimiphaios's authority. Esimiphaios was displaced in 531 by a warrior named Abraha, who refused to leave Yemen and declared himself an independent king of Himyar. Emperor Justinian I sent an embassy to Yemen. He wanted the officially Christian Himyarites to use their influence on the tribes in inner Arabia to launch military operations against Persia. Justinian I bestowed the dignity of king upon the Arab sheikhs of Kinda and Ghassan in central and north Arabia. From early on, Roman and Byzantine policy was to develop close links with the powers of the coast of the Red Sea. They were successful in converting Aksum and influencing their culture. The results with regard to Yemen were rather disappointing. A Kindite prince called Yazid bin Kabshat rebelled against Abraha and his Arab Christian allies. A truce was reached once The Great Dam of Marib had suffered a breach. Abraha died around 555–565 AD; no reliable sources regarding his death are available. The Sasanid empire annexed Aden around 570. Under their rule, most of Yemen enjoyed great autonomy except for Aden and Sana'a. This era marked the collapse of ancient South Arabian civilization, since the greater part of the country was under several independent clans until the arrival of Islam in 630. Middle Ages Advent of Islam and the three Dynasties Prophet Mohammed sent his cousin Ali to Sana'a and its surroundings around 630. At the time, Yemen was the most advanced region in Arabia. The Banu Hamdan confederation were among the first to accept Islam. Mohammed sent Muadh ibn Jabal as well to Al-Janad in present-day Taiz, and dispatched letters to various tribal leaders. The reason behind this was the division among the tribes and the absence