Not particularly. They're all in fixed known orbits so each satellite would know at any given time where all the other satellites in it's constellation will be

Not particularly. They're all in fixed known orbits so each satellite would know at any given time where all the other satellites in it's constellation will be so it can know what satellites will have the best signal between it and the downlink. With that all you really need is for the phones to ping the satellites every couple minutes while on to update the what satellites are over head of phone X. (You could even be clever and cheat a little by figuring out the rough coordinates of each handset and then figure out roughly what satellites would be near overhead too since handsets generally don't move very quickly.)