Frankly my dear, I don't give a damn
King Theuderic had the misfortune to inherit a sprawling state built upon loose foundations, and this issue would preoccupy his early reign. Stretching from Hispania to Saxony, this "Greater Francia" that was his father's making was perhaps more accurately described as a rough union of the various Romanized Germanic peoples who had brought down the western half of the first Roman Empire. However, what legitimacy he had had been won by his father at sword-point, and brute military force would be necessary to maintain his state. Though the core of his army was centralized and professional, the legacy of Clovis' reforms and the great estates of central Francia, Theuderic also depended on the various ranking nobles, the Dukes who were effectively lesser Kings and the Counts who, though not hereditary, nevertheless possessed extraordinary power. Beneath these mighty figures were the lesser nobility, divided into the Frankish fief-holding landlords (or "riders") who lacked hereditary title to their lands, and the hereditary estates of Roman origin, largely preserved throughout Aquitaine and Hispania. While the Frankish "rider" was assured that his sons would almost certainly follow in his footsteps, he was never tied to the land in the same way that his Gallo-Roman counterpart was. He was tied to the crown and to his lord or King, and this goes a long way to explain the number of Frankish aristocrats that travelled East - they sought more permanent wealth and had little to lose back home.
However, the Gallo-Romans, a class which also includes many Franks and Goths who found themselves with similarly hereditary and ancient estates, lacked this sense of loyalty, and as the Franks streamed East, many of these Romans saw opportunities. Rebellions wracked the south, and Theuderic spent little of his reign at peace. These rebellions however were uncoordinated, and saw the large-scale decline of the traditional aristocracy in favor of these new "riders" who were granted mass holdings carved out of the newly conquered estates.
By the time that the situation began to settle down around the turn of the century, the Pope in Rome was making new appeals to the unity of the Universal Church against the heathens. The loss of Jerusalem in 793 saw renewed calls for Votive Soldiers to take up arms, but Theuderic was himself a cynical man, and refused the call, which he saw as yet another attempt by the Papacy to enrich Rome at the cost of his own Empire. Despite condemnation by local bishops and holy men, few Franks went east, and those who did largely went as mercenaries in the Roman armies. Those with little to lose and everything to gain had already gone East in the first waves and stayed there. Those who returned from the Votive War had gained little and were unlikely to desire another protracted conflict in the East. Furthermore, Frankish manpower was low. Theuderic made extensive use of small, elite, mounted forces. The tactics his advisors taught him had been learned in battle against the Avar-Xasars and similar steppe foes, and the Franks shifted further and further away from their infantry-based shield walls in favor of heavy or medium horse as the decisive factor in warfare.
Meanwhile, to their south, the Roman Empire found itself massively overstretched. Roman Asia in particular was practically autonomous, with the local cities there unwilling to negotiate away the privileges they had gained under the Eftal for any price. The resurgent Xasar, after defeating the Duchy of Srem had begun to raid into the Balkans once more. The Roman armies were atrophied by constant campaigning, and despite, or perhaps due to, their professional nature, fresh reinforcements were difficult to come by. The military-bureaucratic system cultivated by the Isidorians had been ideal for defending Italia and some peripheral territories, but it fell apart when it came to securing the newly doubled territory. This massive expansion strained the Imperial treasury to the breaking point. Needing money and manpower, Severus sought to extract both from Asia, sending large garrisons to the local cities and appointing strict magistrates who ensured levies and taxes flowed back to the capital.
Emperor Severus was in many ways a victim of his own successes. Just as he found it difficult to govern his new conquests he found it difficult to shake the image of himself as a usurper. He was convinced that a decent number of his high ranking officers secretly despised him, and he knew that the Slavic lords of the Balkans definitely did. When the Emperor died in 803, despite his advanced age, it was not hard to suspect foul play, and those closest to the Emperor definitely did so, turning on each other rapidly. Severus had but a single son and several sons-in-law, but "coincidentally" by the time his body was cooling the young son was dead and the eldest of the sons-in-law, the Legate Valerian, was the prime suspect. The Magister Militium, Asterius, moved to have Valerian arrested, but the wily Legate escaped. Fleeing with a cabal of loyal officers and as much of the royal treasury as he could load onto a boat, Valerian escaped to the Balkans where he sought to raise an army with the help of a group of influential local magistrates. The Roman cities of Asia, meanwhile, realized that Severus' death was an excellent opportunity to renegotiate their position. In the Kingdom of Asia, King Helinand had recently passed away, succeeded by his son Mansuetus. Mansuetus was seen as a temperate, reasonable man, and the Roman cities sent delegates to Nicomedia, where during a three week council the cities managed to extract many concessions in exchange for swearing fealty to the Frankish King of Asia. Shortly thereafter, these same delegates, as part of the pre-arranged agreement, proclaimed Mansuetus Emperor to the cheering of his retainers and soldiers. Crossing the straits, they met with the Patriarch of Constantinople at the Chapel of St. Maria and Mansuetus was officially crowned as "Emperor of the Romans". Meanwhile, back in Florentia, Magister Asterius set aside his wife with Papal blessing and married Severus' youngest daughter, Theodora, thirteen years old, seeking to enhance his own dynastic legitimacy in a bid to be proclaimed Emperor. Asterius, however, was not popular with the rank and file. He had not fought in the Votive War and his promotion to the position was largely seen as a consequence of his political ability but as his ties to Severus. It was only with the spreading stories of a Frankish "Emperor" in the East that Asterius finally took action, being enthroned in a majestic ceremony. The Pope condemned the new Frankish Emperor as illegitimate and in return the Patriarch of Constantinople condemned the Pope as a puppet. Emperor Mansuetus was the bulwark of Europe against the heathens! The usurpers of the West were the true illegitimate ones, the Severian dynasty being no more than upjumped farmers from Illyria and Asterius himself was committing an act of adultery by marrying into it.
Valerian, proclaimed Emperor by his troops, found himself in the worst position of any of the Imperial claimants. He was dependent on the Slavic aristocracy, who had little love for him, and had mostly understrength units under his command. Furthermore, the resurgent Xasars looked greedily on his territories, which included several exposed stretches of the Danube. However, despite his weakness, no-one acted against him. Mansuetus was preoccupied with the Aghatsaghids and the remaining Eftal, and Asterius faced a rebellion in Sicily among the remaining Mauri merchant-princes which lasted four years between 811-815. As such, he had the better part of two decades to secure his position. Hiring Turkish and Bulgar mercenaries to his cause, by 820 he felt safe enough to invade Italy in force. Asterius fell back in the face of this new threat, raising fresh forces and knowing that Italy would be a tough nut to crack in the interim. Without a fleet of his own, Valerian had no way of taking Ravenna, and he squandered several years reducing the cities of the Po valley. By the time he was ready to march on Florentia, Asterius was ready. He let Valerian encircle the well-fortified and well-provisioned city and then enveloped Valerian in turn. Valerian, with the help of his mercenaries managed to fight his way out of the encirclement, but it was a close-run thing indeed. He suffered a minor wound and later that year in 821, he would pass away, his army largely disintegrating and turning to banditry until Asterius finally restored order to the Balkans in 824.
The Frankish Kingdom itself chose to sit out this massive succession crisis. Theuderic for the first time found his Empire relatively calm. The Slavic marches were quiet, and for the first time no nobles hinted at rebellion. Theuderic could rest in Paris for the first time in decades. And indeed, the Franks had their own crisis brewing. Theuderic was growing older, and he had four sons - inevitably, it seemed, his kingdom would be divided upon his death. Unwilling to see this happen, in 807 he adopted a more Roman style system of succession - naming his eldest son, Clovis, Co-King, and granting the others Palatine titles - ensuring that they would be kept close to crown. Going forwards, this would prevent the anarchic succession practices that historically had ensured the collapse of any large Frankish Kingdom.
North Africa - the Free People
It was not until 800 that the trade routes between the Mediterranean world and North Africa truly began to recover from the collapse of the Mauri. It was not that the Berber people did not understand the value of trade, but climate shifts and urban decline made the sort of bulk trade that would be genuinely profitable difficult. Merchants operating on East-West trade lanes could move bulk products to a degree which the Berbers simply could not - dependent as they were upon attenuate trade lanes manned by Taureg caravans.
The gold, spices, and ivory of Ghana would however ultimately begin to trickle northwards, catching the attention of the Latin world. Rumors of golden kingdoms and shimmering palaces of solid gold spread like wildfire. Africa beyond the great desert became a land of mystery and magic in the collective imagination of the Christian world. However, it was also unreachable. Few travelers crossed the great desert due to the extraordinary number of middlemen facilitating the trade - countless local Amazigh and Tuareg tribes stood between the iron kingdoms of the continent and the ambitious Mediterranean merchants.
These tribes did not develop the same central cohesion that had characterized their Mauri predecessors. Where the Mauri embraced the legacy of the Roman Empire, the Berber successor states tended to repudiate this legacy in favor of their own mythic heritage. Accordingly they did not form major polities, creating at best loose alliances when it was expedient to do so. In the far west, the Masamida were perhaps the most united of the tribes, and then only because such unity was required to effectively raid Iberia.
The religious makeup of the region favored paganism. The Nicene Church in Africa had always been somewhat schismatic and perhaps less organized than many of its counterparts - heretical tendencies here were part of a broad historic trend. As such with the collapse of centralized Mauri authority the Church fell into relative anarchy as well. The heretical gnostic ideas of organizations such as the "Tinanians" divided the Church and encouraged various sects to flee into the wilderness and isolate themselves rather than actively proselytize. The indigenous Jewish populations (including many Jews who had fled from Spain) had more success, gaining converts among some local clans, but this too was a limited phenomenon. Local cults retained their strength. Prominent gods such as Idir, the living god, and Gurzil, a warrior deity, might have enjoyed some universal appeal, but generally speaking day-to-day veneration was confined to local spirits and minor deities associated with landmarks. The one commonality between tribes was the worship of celestial bodies, especially the Sun.
The Berbers however kept few written records. What we do know of them comes mostly from the Christian communities huddled along the coast, and these communities had a conflicted relationship with their neighbors. On one hand the Berbers maintained the great trade routes across the continent - on the other hand they had destroyed the Mauri civilization and with it much of the region's historic prosperity. The Berbers also left little in terms of a visible legacy. Architecturally they either maintained Mauri buildings or left uninspiring but functional fortified towns. They lacked the capacity or interest in the construction of massive projects. They however did leave many elaborate finished goods - ornate polished beads, gold and iron jewelry, intricately carved furniture, proof of an advanced and technically skilled culture.
It is a matter of some historical curiosity why the Berber invaders never assimilated as so many other peoples did. Most of their immediate neighbors lived in the shadow of the Roman Empire - Roman was almost a byword for prestige and power. The Mauri, the Italians, even some Eftal... many disparate peoples considered themselves Roman or the inheritors of Roman glory. It is easy to cast the Berber disdain for that tradition as provincialism or barbarism. However, those peoples who brought down the Mauri had never been even at the periphery of the Roman world. Its heritage was irrelevant to them, and their main association with it was the Mauri. The divided, squabbling Christian religion of Africa was not as impressive or influential as the unified Latin Church whose emissaries the Western Slavs would encounter.
Accordingly, the growth of Christianity among the Amazigh people would be a slow process, prone to syncretic tendencies. Churches where Christ is represented as haloed by the radiant sun were not uncommon. Libyan deities became angels, and the polytheism of the Berbers endured despite regular missionary and mercantile adventures into the North African interior.