How to require one of many modules in your own module? Let's say my module needs functionality X. This functionality can be provided by two other modules. For example, front-end with two backends to store data, and at least one backend is needed for frontend to work. Is there a way in Drupal to mark it?

In GNU/Linux and BSD operating systems there usually is a marker like provides, for example Bison provides Yacc, and everything that would need a Yacc can work with only Bison installed. That's about what I'm looking for here.
One option is to feature detect the modules using function_exists() or class_exists(), and then use some logic to pick the one you want.

You can also wire up a hook_requirements() to hard fail in the $phase == 'install' step or soft fail in the $phase == 'runtime' step.

How you handle the failures really depends on your application.