Как получать уведомления (обновления данных) даже когда приложение закрыто?

Пример. Вот есть Вконтакте, которое отправляет уведомления о сообщении, даже когда приложение закрыто. Я подумал, что можно реализовать через Service, но так как их изменили (приложение закрывается и система их убивает) - не вариант. Как это можно сделать?