Sleep and deep sleep
First of all it's important to distinguish between sleep, deep sleep and doze.
In Android terms, "sleep" means the screen is turned off. "Deep sleep" means the phone has gone into a power-saving mode that's roughly equivalent to "suspend" on mainstream Linux: most of the peripherals are powered down and the CPU halts until it receives an interrupt from one of the remaining peripherals (wifi/mobile radios, power button, realtime clock, etc).
The phone will try to go into deep sleep as soon as the screen is turned off. If it wakes up to process an interrupt then it will go back into deep sleep as soon as possible. If you come from a Linux background like me, it's hard to adjust to the idea that during normal operation, the phone is constantly dropping in and out of suspend.
An app can prevent sleep by holding a full wake lock, which keeps the screen on, or allow sleep but prevent deep sleep by holding a partial wake lock, which allows the screen to turn off but keeps the CPU and peripherals awake. There are also wifi locks to keep the wifi radio awake.
Apps can schedule alarms to wake the phone from deep sleep at specified times. Network traffic including push notifications can also wake the phone from deep sleep. There are various work-scheduling APIs that use different combinations of alarms and push notifications to perform background work at scheduled times.
A typical phone has dozens of apps doing little bits of background work at different times, so if you create an app that logs the current time in a loop, you'll see that there are lots of little gaps in your log, corresponding to short deep sleeps interspersed with short wakeups. If the phone is unusually "clean", with only a few apps performing background work, you might see longer gaps in your log. If your app holds a partial wake lock then the gaps should disappear.
(Side note: be careful which clock you use for this. Android has an "uptime" clock that records the time since boot excluding deep sleep, and an "elapsed realtime" clock that records the time since boot including deep sleep. If you use the uptime clock for logging then deep sleep will still happen but no gaps will show up in your log.)
As far as I know there's no way for unprivileged native code to schedule alarms or hold wake locks. You have to use the Java API.
In theory you can keep a TCP connection open during deep sleep. The phone will briefly wake up when data arrives, giving you a chance to grab a short-lived wake lock, process the data and respond if needed. But you won't be woken if the connection's lost. You may need to hold a wifi lock if the connection uses wifi.
If you're using Java sockets, deep sleep prevents socket timeouts from working: if the phone is in deep sleep when the timeout's due, the timeout won't fire when the phone eventually wakes. The socket will be dead but the read operation will just block indefinitely without throwing an exception. I don't know if the same is true for native sockets.
Changes in API 19 (Android 4.4)
In API 19 the alarm API was changed so that alarm deadlines are inexact by default, allowing the system to batch alarms together and reduce the number of wakeups.
Changes in API 23 (Android 6): Doze and app standby
Doze mode was added in API 23. The basic assumption behind doze is that apps don't need to do frequent background work when the user's asleep or away from their phone. This assumption is true for many apps, but doze causes problems for apps that don't fit the assumption, such as sleep trackers and P2P messengers.
The phone enters doze when it's spent a long period of time running on battery, stationary, with the screen turned off. While the phone is in doze, wake locks and alarms are ignored and apps lose network access.
Doze is a separate concept from deep sleep, but when the phone is in doze it's likely to spend a lot of time in deep sleep, as there will be fewer wake locks and alarms and less network traffic.
During doze the phone occasionally enters a maintenance window where the doze restrictions are lifted. Alarms that were due to fire while the restrictions were in place fire during the maintenance window instead. Maintenance windows get further apart the longer the phone is in doze.
API 23 added new types of alarm that can fire during doze (setAndAllowWhileIdle and setExactAndAllowWhileIdle). An app can only fire one such alarm every 9 minutes while the phone's in doze (or up to 15 minutes on some phones).
There's one other type of alarm that's unaffected by doze: setAlarmClock. This is intended for setting alarms that notify the user about something, as opposed to alarms that schedule background work. As far as I know there are no limits on how frequently an app can use this type of alarm in doze, but a notification will appear in the status bar while an alarm's pending. I wouldn't be surprised if misusing this method to perform background work got you banned from the Play Store.
Along with doze, API 23 added another power saving feature, app standby. App standby applies to apps the user hasn't interacted with recently. An app that's in standby loses network access while the phone's running on battery, except for a daily maintenance window. Wake locks and alarms continue to work, however. The app is removed from standby when the user interacts with it.
If an app is running a foreground service, its wake locks are supposed to keep working in doze. But there's a bug in the implementation of this rule on Android 6.0, such that if the foreground service is running in the same process as the app's UI, and the UI is in the foreground, then the rule isn't applied and the wake lock is ignored. So if you want to make use of this rule you have to launch your foreground service in a separate process from the UI.
An app can ask to be exempted from doze by adding the REQUEST_IGNORE_BATTERY_OPTIMIZATIONS permission to its manifest and asking the user to approve the exemption via an ACTION_REQUEST_IGNORE_BATTERY_OPTIMIZATIONS intent. But there are Play Store policies governing the use of this permission.
An app that's exempt from doze can hold wake locks and use the network while the phone is in doze, but its alarms are subject to the same restrictions as other apps. A perverse effect of this is that if an exempted app wants to perform background work every few minutes, it can't use alarms so it has to hold a permanent wake lock, which uses much more power than firing an alarm every few minutes would have done.
I don't know if the doze exemption also applies to app standby. But if you run a foreground service then app standby won't affect you anyway, as the user is considered to be interacting with your app.
Changes in API 24 (Android 7)
Starting from API 24, certain broadcasts that could previously be received by registering a receiver in the app's manifest can only be received by registering a BroadcastReceiver programmatically. This saves power because receivers that are registered programmatically are unregistered when the app's process is killed, and don't get registered again until the app is relaunched.
Changes in API 26 (Android 8)
Starting from API 26, wake locks are released when the app enters the cached state, which happens when it doesn't have any visible activities, foreground services, or recently started background services. Apps that are running in the background can't start new background services. Foreground service notifications must have at least PRIORITY_LOW and IMPORTANCE_LOW so they're visible to the user, and must provide a way for the user to stop the background work.
Changes in API 28 (Android 9)
API 28 added "app standby buckets", which are an extension of the app standby mechanism from API 23. The system uses these buckets to apply graduated restrictions to infrequently used apps. The user can also apply these restrictions manually.
In 2017 the Play Store introduced Android Vitals, a system that monitors apps for performance problems such as "excessive wakeups" and "stuck partial wake locks". Apps that exhibit these problems may be demoted in Play Store listings. Despite Briar's heavy use of wake locks, the Play Store console hasn't so far shown an issue with stuck wake locks. So who knows what the criteria are.
The current state of play
On stock Android, the current state of play is that an app can stay running in the background if it asks the user for a doze exemption, runs a foreground service, and holds a wake lock. But holding a wake lock will cause a lot of battery drain.
If you only need to perform work every 15 minutes or so then you could use an alarm to schedule a wakeup and briefly use a foreground service and wake lock while doing the work. If you want to perform work more often but every 15 minutes is OK when the user's asleep or away from their phone, this approach could also work. Just set your alarm to the preferred interval and the system will apply a longer interval during doze.
If you need to perform work more often than every 15 minutes but can tolerate an occasional 15-minute gap, a TCP connection with keepalives may work, with an alarm as backup in case the connection's lost. Some ISPs are aggressive about killing idle connections, so sending frequent enough keepalives may be a problem if the device on the other end of the connection is also running Android.
Outside of the relatively simple and predictable world of stock Android, anything can happen to anyone at any time. Alarms may fire late or not at all. Wake locks may be ignored, or apps may be killed for holding them. Many phones have multiple power saving modes, each with its own restrictions. There's a cottage industry of libraries that help you detect what manufacturer-specific restrictions might be in place and guide the user to disable them.