The Equivalence Between Processor Sharing and Service in Random Order

In this note we explore a useful equivalence relation for the delay distribution in the G/M/1 queue under two different service disciplines: (i) PS (Processor Sharing); and (ii) ROS (Random Order of Service). We provide a direct probabilistic argument to show that the sojourn time under PS is equal (in distribution) to the waiting time under ROS of a customer arriving to a non-empty system.