Abd Al-Malik was the Umayyad caliph from 685–705. Until 692, he was preoccupied with internal rebellions.
Justinian II took advantage of this by unleashing on Syria the Christian bandits called Mardaites, and by sending an army under Leontios into Armenia. The resulting treaty of 688 was favorable to Byzantium, requiring the caliph to pay tribute and dividing with Byzantium the revenues from Cyprus, Armenia, and Georgia. In 692 the caliph was able to turn his attention to military expansion. He defeated Justinian II in Asia Minor in 693, forcing the emperor to abandon Armenia (which the Arabs) subsequently conquered in 703). In the West, the Arabs conquered Carthage in 698, extinguishing what was left of Byzantine authority in North Africa. The caliph tried to remove vestiges of Byzantine influence within the caliphate, e.g., by issuing the first purely Arab coinage without Greek inscriptions or imagery, and by making Arabic the official language. Nevertheless, in Jerusalem he used Byzantine mosaicists to decorate the great Dome of the Rock.
(Source: «Historical Dictionary of Byzantium», by John H. Rosser)