We actually use syslog-ng + Loggly for distributed Loggly. We partially solve the transaction problem by slapping a request ID on every action that's initiated by a web request. We then carry this request ID from service to service, which gives us the ability to trace exceptions cross-service. It's obviously not the perfect solution, but it has helped us many times when debugging customer-facing 500 exceptions.
We solved the service discovery problem by simply using DNS. Every service runs behind an (internal) Elastic Load Balancer, and we let the load balancer configuration figure out which instance is up and which one is down. Again, not the perfect solution, but it works great for now and is very easy to setup/maintain.
The other halves: distributed logging (how do you trace a 'transaction' that is being executed against multimachines/multiplaths?)
What about rolling releases? what about versioning?
What about service discovery (still immature field, look at how many products/tools out there trying to be THE service discovery choice).