The "Goodbye" Problem - Computerphile

Key Takeaways

have you uh ever heard it said sometimes it's hard to say goodbye if you're teenagers in love and you're chatting away on the phone at least when I was young you you'd be talking and a and you finish your phone call but you really like that person you're awkward you're an awkward teenager oh you say goodbye first no you say goodbye first oh no you say goodbye no are you still there have you said goodbye so now all right what's that got to do with computer science what's that got to do with networks when we are communicating with computers most of modern uh internet connections are using transmission control protocol TCP right we've talked about it a few times on the channel TCP I always told my students it's a polite protocol it begins with a hand hand shake a three-way handshake cuz we we establish a connection I don't just go hey get some data I go hey um uh can I can I give you some data yeah if you want to yeah I'm ready to give you some data ready so it's it's the three-way handshake so let's start off with saying hello the problem here is we need to be robust to failure it's the internet no matter how much you design it an individual message might be corrupted might just not get delivered so we want to set up a system where the client can connect to the server and know it's connected and the server also knows it's connected so say say hello it's fine we start off with a packet we call an Sy YN a sin packet so this is to create the TCP connection the S packet if it goes missing after a certain amount of time or another one but let's for the sake of simp say it hasn't and now the server should reply with a sin act so that act is an acknowledgement it's saying ah thank you for uh your interest in connecting with me today uh I would also like to connect to you and then the client is going to send back an act and it's going to send back some data as well so this is the data might be like please send me a web page or I would like to open an SSH session or something whatever it's the thing the client's going to send and that works really well and if one of these is lost you send it again H all fine but closing down it seems like it's going to be the same problem so Finn oh bye Sean see you see you okay uh so you're going to send back so I send a Finn finac and fin obviously cuz it's a fin no dare there that seems kind of symmetrical right but you also need to shut down the computer at some point and then what happens if a packet goes missing when we were opening up the connection it's easy the computer's still connected if something's not sent after a little bit of time send it again but here if something's not sent you've Switched Off you're not going to send it again now this is going to seem like a big segue big kind of jump of uh what we're doing let's Imagine This is called the two generals problem so here ah I am not a splendid digital artist here's a general with a sword so there's the purple General and there's the green General and they both want to attack this city here and they know if they attack together they win if only one of them attacks and the other one hasn't got a message they Le they're free to send messages but the messages might be intercepted by the enemy so attack green General sent a message to the purple General to attack H but it's going to go past the very thing they're trying to attack maybe it's going to be intercepted so you think when you first hear this it seems like child is she simple right right I mean what would you what would you do what sort of system might you set up well you got to you got to get somebody to do a bit like the hello the ACT send a message back saying okay got your message thank you yeah okay so he just going to send up uh okay yeah send an I will attack goodness me so he's sent back and I will attack all right so he sent an attack and they sent I will attack and if that happens oh that's great right we're both going to attack but any of these messages might go missing so let's imagine that message goes missing so he's sent out attack he sent I will attack but that's that message is died that messenger has been shot by the enemy City purple General charges in or confident green General hasn't got his receipt so green General sitting on the hillside going uh what can I do purple General's Ked and you can keep on going this you think the first time you hear this problem you think there's got to be a solution there's got to be some way of doing it provably provably this is impossible the sort of sketch proof is imagine there is some message MN so in a in a deterministic protocol some protocol where receipt of messages has a determined not a probabilistic meaning um if there some message MN that if it was received definitely means attack so MN received implies attack if that is the case then if m is received by a general it means attack the other General is therefore bound to attack but if that message is lost the general receiv receiving it won't attack so any message that you you say is going to be the last one which definitely means attack could be lost so this this problem exactly maps onto the TCP finish problem the general attacking it's a a committed irrevocable action just like shutting down the TCP connection if I decide to shut down my TCP connection I won't hear your message saying please could you repeat your acknowledgement so so this weird thing that the seemingly symmetrical actions of opening a tcv connection very very easy polite triple handshake Sin Sin a a closing down your TCB connection no it just doesn't work I've been teaching this for many many years and every year it just annoys me it should be easy but it's provably impossible how do we solve it in real life honestly it's what you'd call a clutch you just kind of wait around a little bit you you say oh yeah yeah definitely going to shut down and then you swe around go you still there it's like the teenager on the phone it's like the teenager on the phone have you said goodbye Sean yeah I'm just still listening waiting for a click used yeah yeah you used to get the click on the old phones that's true not on the modern ones not on the modern ones so yeah it's uh hard to say goodbye about here is what's called time to live every Internet Protocol packet when it's created is set up with this flag time to live it's as if they've all got a Doomsday Clock on them um they've got a little counter