During the following weeks, while Belisarius remained in Carthage strengthening its walls, Gelimer established himself and the remnant of his army at Bulla Regia. By distributing money he had managed to cement the loyalty of the locals to his cause, and sent messages recalling Tzazon and his men from Sardinia, where they had been successful in re-establishing Vandal authority and killing Godas. While waiting for Tzazon's arrival, the Vandal king's army also increased by the arrival of more and more fugitives from the battle of Ad Decimum, as well as by a contingent of his Moorish allies. Most of the Moorish tribes of Numidia and Byzacena, however, sent embassies to Belisarius, pledging allegiance to the Empire. Some even offered hostages and asked for the insignia of office traditionally awarded to them by the emperor: a gilded silver staff and a silver crown, a white cloak, a white tunic, and a gilded boot. Belisarius had been furnished by Justinian with these items in anticipation of this demand, and duly dispatched them along with sums of money. Nevertheless, it was clear that, as long as the outcome of the war remained undecided, neither side could count on the firm loyalty of the Moors. During this period, messengers from Tzazon, sent to announce his recovery of Sardinia, sailed into Carthage unaware that the city had fallen and were taken captive, followed shortly after by Gelimer's envoys to Theudis, who had reached Spain after the news of the Roman successes had arrived there and hence failed to secure an alliance. Belisarius was also reinforced by the Roman general Cyril with his contingent, who had sailed to Sardinia only to find it once again in possession of the Vandals.