Is it possible to connect Joomla and Moodle with Joomdle when they are on different servers? And, if so, are there any additional requirements for that?
Yes, you can do that. There are no additional requirements, only one limitation: it is not possible to use redirect-less SSO with different servers, so you need to use redirect-based SSO (the default method in Joomdle)
