During the fourth and fifth centuries the Empire was had one of his worst time, the Eastern Roman Empire managed to eliminate many of the non-roman generals, which where ruling its counterpart in the West.
After Theodosius the Great, the two halves began drifting apart, while the West kept a strong Roman indentity, the East found itself identifying more and more with the ancient heritage of Greece. Hellenism and been a powerful influence in the Orient ever since the time of Alexander and as time progressed Greek culture gradually supplanted the Latin. This is not to say that the Empire ceased to be a Roman one. Quite to the contrary, the people around the Mediterranean, in West and East Europe continued to refer to themselves as Roman citzens long after the time Rome as the centre of trade and power had lost its role.
The tide was turning, the reign of Justinian saw his Reconquest (often known as the "Justianian Renconquest") in which the Empire regained portions of the West including Italy, North Africa and southern Iberia (modern day Spain).
This was continued by Heraclius, the Emperor who signed a permanent peace with the Sassanid Persia, which later felt due to the islamic conquests.
Britannia, Gallia and most of Iberia accepted again the formal supremacy of the Empire again.
The advent of Islam which began in Heraclius' final years, brought a new and even more problem, while as dangerous enemy it was diverted to the East against the Sassanid Persia, the following emperors had to accept them as foederati of the Empire leaving to them the indirect control of many of its territories. Egypt, North Africa, the Levant and Syria, and parts of Spain provinces that had been Christian for centuries, converted helped also by muslim Emperors.
With muslim emperors the Roman Empire had to experience the cultural and intellectual deprivations that of many religious wars in Western Europe. The seventh through ninth centuries saw the Roman Empire ruled by nominal emperors while struggling ceaselessly against their new enemies Slavs from the north. The year 800 saw the rebirth of a Christian Roman Empire, thanks to Charlemagne, he married the Empress Irene (Eastrn Roman Empire) at the hands of the Pope, this preserved the long held notions of the essential unity of the Roman Empire.
The tenth centuries saw Roman Empire fortunes again in danger, a series struggles for the Emperor title put strong leaders and able generals one against the other, the Empire sit on the defensive with the the Islamic world and the Barbarians.
Thanks to A History of Byzantium-Preface by VILenin for some preface ideas
These eight men, anonymous generals of the Roman Empire, made an alliance to keep the Roman Empire alive, they took the name of historical Roman Emperors dynasties and its roman culture, split the Empire in areas of influence, and elected one of them as new Emperor.
For the first time the Empire had a defined succession law, the elective law of the strongest will be respected? Will Iulius have the skills and not only the name of Iulius Caesar?
The first move was to keep and extent the old imperial/republican provinces where possible, while aknowleging the feudal right and the new cultures and religions of the Empire. The two two administrative halves of the Empire were kept with a preference for a strong Eastern Empire (Greece and Anatolia) and a weak Western Empire (Parts of Italy and North Africa)
Emir of Palestine et Arabia
Principe of Thracia et Moesia
Dux of Gallia Cisalpina
Dux of Gallia Narbonensis
Dux of Gallia Aquitania
High Chief of Noricum et Pannonia
Dux of Africa Proconsularis