When a device is switched off, all messages for that device are stored in different distributed service centers. For example, the message from user A may be stored in SMSC A and a message from user B in SMSC B where both subscribers and respective SMSCs can even belong to different networks. When the device is switched on again it notifies its presence to the network (performed by the MSC indicating this to the HLR). As a result of this alert, different service centers that have messages pending for that device will be notified that the device has come on-line again (performed by the HLR notifying SMSC A and SMSC B). Instead of directly sending out all messages, as in the prior art, each service center instead schedules the messages in an internal queue for delivery according to a local control scheme, which achieves synchronized delivery from multiple distributed SMSCs even though there is no centralised control. Each service center maps the ‘age’ of the message on its time axis as the time-to-deliver the message to the device. The deliveries are then sent out according to the derived schedule. As independent service centers all will base their decisions on the same length of the delivery schedule and same maximum retention time, the message deliveries of the different service centers will be interleaved with one another. This ensures that for significant time differences, messages from different service centers will still arrive in order at the device.