Do you think this problem could be solved by having the backend service randomly redistribute packets? That is, if each service kept/processed a percent of the packets and randomly forwarded the remainder to other 'backend' service computers.

Membership and status would be easy: are they forwarding random packets to me? Then they're up and running. New computer sends packets? New service member, so tell them about members you know of. This would also allow multiple public ingress points (like running multiple simple load balancers) so clients could change which computer they send to, and bandwidth would be ~balanced.