The "Goodbye" Problem - Computerphile

[@josephrissler9847]

I love that doing computer science is basically just proving problems are mathematically impossible to solve, then implementing solutions to those problems.

[@TheGraemeEvans]

Impossible to solve, but possible to mitigate.

[@IceMetalPunk]

Well, implementing "probabilistic solutions that, in theory, should work like 99% of the time, but 1% of the time your connection times out".

[@SeanSMST]

Yeah like in a network with multiple routers, 'how the hell can I make sure that when one router goes down, another is used as backup?'. Someone somewhere thought of making a virtual router, with each real router appearing as the one virtual one. When I learned about this, it sounded like a child came up with it. When a solution to a tech problem sounds so creatively simple as this, it's pretty jarring and funny.

[@MorningNapalm]

I love that you work it out with white board markers on wide, endless printer paper :D Nothing has changed since the '90s at the very least.

[@NoEgg4u]

I was surprised when this video ended.

[@CottonInDerTube]

because it was telling a problem without talking about a solution. Lame video this time.

[@AySz88]

​@@CottonInDerTube I think you missed the message ;p

[@JavierSalcedoC]

@@CottonInDerTube literally the video title

[@richardclegg8027]

@@CottonInDerTube the problem as stated seems simple but is provably impossible. The working solution is just a simple timeout as I state at the end of the video.

[@reybontje2375]

​@@richardclegg8027I do wish that it was elaborated a bit more why we'd need to have a timeout. I understand that it's impossible to have a proper goodbye, but I'd have liked to learn how software engineers could work around this with timeouts. Presumably, the person who's saying goodbye would just timeout the fin ack, but what about the person who is receiving the goodbye? If the initial fin is lost, they wouldn't send a fin ack and the person saying goodbye would just time it out, but what stops the person who failed to get the fin from just hanging in a read loop? I suppose I can maybe answer my own question with the concept of Keep-Alive requests and timeouts.

[@chrishill601]

I'm proud that as soon as I saw the video title, I was pretty sure it'd be an application of the Two Generals problem.

[@albarnie1168]

Same! Always love a two generals video.

[@OhhCrapGuy]

I once had an study session type thing where these two techbros tried to explain they'd solved the general problem, and asked me if I had figured out how to *guarantee* that communication would succeed. I hadn't actually heard of the problem at the time, but I worked through the whole thing in a couple minutes and just said "I'm pretty sure communication cannot be guaranteed in every circumstance, or I've misunderstood the question, or I'm just missing the solution." They told me I was *wrong*, you just had to send a lot of messengers, that's how you guarantee the message will get through. I said "uh, that's a statistical sound approach, but it's not a guarantee. Your solution can get you as many nines as you want, but you can't guarantee it." and they said "sure you can, just send enough and it's guaranteed." I just stared at them for about 10 seconds, a bit shocked, then I thought for a moment, grabbed a three pieces of scratch paper, folded them up and tore them into 8 pieces each as I suggested the following: "let's do an experiment to model your solution. I'm going to be the internet route and all the gateways between your two subnets. You two need to sit at different tables facing away from each other. You (TB1) are going to play the client trying to close the TCP connection [handed him 8 scraps of paper]. Each FIN packet you send should contain a new nonce, and it's vital that you send each one with a different nonce, because I'm going to be a lossy network and lose most of your packets. Make sure you keep sending them until you get the FINACK, don't stop until you get that. Just put them on the corner of the desk, and each time I come over, I'll pick them up, throw a few out, and hand the rest to the other guy." I went over to tech bro 2, handed him the second pile of scraps, and said "you'll obviously send FINACK messages with the most recently received nonce. Once you get a FIN packet, just start writing FINACK with the highest nonce you've seen, okay?" Then I went back to TB1 and said "once you get the FINACK, you will start writing ACK on pieces of paper with the most recent nonce until you know TB2 has received them, okay? Don't look backward, you just have to send enough that you know he's gotten at least one, okay?" (To both) Now, remember, you keep sending your packets until you know for sure that everyone's on the same page, that's any ACK from . , keep in mind you can't stop sending FINACK until you get an ACK." So we started, I took like 7 FIN packets and threw them out before finding TB2 one. TB1 stopped at 8, which is fine. TB2 started sending FINACK, and I threw out 3 of them before I started giving them to TB1. TB1, of course, started writing ACK packets and putting them on the corner of his desk. I took the first 2 ACKs, threw them out, then I just left without a word. Took my backpack, turned off my phone, didn't answer their calls. They called me an asshole. I kept ----ng th-- -hy the- --ed to underst--- ho- packe- --ops can aff--t data tra--fe-.

[@ardonjr]

The animation from 'user with a laptop' to 'general with a sword' gave me some huge Macromedia Dreamweaver Flash animations throwback.

[@Computerphile]

Macromedia Director was probably the application I first used for animation! -Sean

[@JavierSalcedoC]

dreamweaver and fireworks, name a more iconic duo

[@der.Schtefan]

What was that website where you could play Flash games from the 2000s

[@Meta7]

@@der.Schtefan Do you have even the slightest idea how little that narrows it down?

[@revenevan11]

3:56 for anyone wondering

[@jozsefbodnar6177]

I first read about the "two generals" problem in a book where it was presented as a puzzle, first explaining that any message could be lost so the generals can never be sure, then asking the reader for a solution. I was like "obviously there is no solutions.... but the book would never ask it if there wasn't one", so I was thinking about it for a long time before looking up the "solution"... I was soooooo maaad at the way the book asked this...

[@gabrote42]

Rhetorical questions always trip me up

[@fllthdcrb]

2:53 Just one correction: that last packet should be ACK, not FIN. The same side doesn't send another FIN (unless the first one gets lost), but it does need to ACKnowledge the other side's FIN. (Also, a clarification. This is a common way to label handshakes when talking about TCP. Really, SYN, FIN, and ACK are flags. Only the packets labeled as such have the SYN and FIN flags, because they are used only for those purposes. But ACK is in very nearly every packet, because you always need to acknowledge the other side's state, except with the very first packet that opens a connection, which will only have SYN set. But for purposes of talking about handshakes, we only mark it where it relates to SYN and FIN packets.)

[@richardclegg8027]

You are right. The correct close sequence is FIN FIN/ACK ACK. How annoying. Slip of the pen and voice. Sorry, very hard to write and talk while improvising it all.

[@richardclegg8027]

I got Sean to add some text about this in the description. Thanks for pointing it out (I hadn't actually seen the video myself when you commented). It's a bit of a *blush* moment because I teach this (correctly) every year but it's pretty hard for me to completely avoid this kind of a slip. [The sequence is easy to remember because it's basically the same as SYN SYN/ACK ACK.]

[@japanskakaratemuva5309]

Isn't the close down aka as 4way teardown?

[@fllthdcrb]

@@japanskakaratemuva5309 It can be either 3 or 4 packets, depending on how the non-initiating peer handles the close. Each side must send a FIN to close its side, so the non-initiating peer could delay closing, and even continue to send in a state known as "half-closed". But OTOH, it could, and often does, send a FIN in the same packet as the one that acknowledges the initiating peer's FIN, resulting in a 3-way close.

[@richardclegg8027]

@@japanskakaratemuva5309yes. FIN. FIN-ACK. ACK. The FIN-ACK can be two packets but is often one.

[@AnotherPointOfView944]

When he has (finally) finished talking, my autistic son just hangs up (no goodbye). Bless him.

[@HarshKapadia]

Hahaha aww! 😂❤

[@michaeldamolsen]

That's nice, your son speaks UDP instead of TCP :)

[@HarshKapadia]

@@michaeldamolsen love that! 😂❤️

[@5h4ndt]

I can't relate to this, friend of mine used to hang up during saying goodbye. So I always received a partial goodbye and never a chance to say goodbye myself.

[@Ediolot123]

UDP friend ?

[@dexter9313]

@@Ediolot123 I laughed way too hard at this, thanks!

[@IceMetalPunk]

@@Ediolot123 Half the time, they only heard every second word of the conversation 😂

[@DavidSallge]

@@Ediolot123 This answer deserves way more credit!

[@ncot_tech]

This starts off sounding simple, then it turns into one of those spiralling recursive things computer science is full of. If every TCP packet is acknowledged, but the ack gets lost, do we need to acknowledge the acknowledgement, but what if that gets lost... and so on. Packets all the way down.

[@IceMetalPunk]

I won't close a connection until you've acknowledged that I acknowledged that you acknowledged that I acknowledged that you acknowledged that I acknowledged that you acknowledged that I acknowledged that you acknowledged that I acknowledged that you acknowledged that I acknowledged that you acknowledged that I acknowledged that you...

[@TheALPHA1550]

@@IceMetalPunk ... acknowledged that I acknowledged that you acknowledged that I acknowledged that you acknowledged that I acknowledged that you acknowledged that I acknowledged that you acknowledged that I acknowledged that you acknowledged that I acknowledged that you acknowledged that I acknowledged that you...

[@thewhitefalcon8539]

The ack of the ack is that you stop sending the original packet

[@GummieI]

@@thewhitefalcon8539 But how do you know whether the other party actually stopped sending, or the packets just got lost in transit?

[@smilerbob]

TCP is just like life. Lots of communications and some that naturally drift into silence and fade away then when you next see that person it all starts again with a “Hello”

[@0LoneTech]

And then there's the case where someone just continues talking to be met with a "Huh? Stop. I'm not whoever you thought you were talking to." That's what RST is for.

[@2Fast4Mellow]

In one of my first relationships my girlfriend told me 'you say goodbye'. Okay, goodbye, *click*. Next day she was upset that I just said goodbye and hung-up the phone. For the live of me I did not understood why she was mad and a friend has to explain to me the meaning of saying goodbye. While I'm now an American, I am Dutch by birth and we are direct, I am also a bit of a nerd who in general are also direct/literal. Direct squared equals disaster in relationships. I'm now 48 years old and a few weeks ago I did it again. She asked 'Did you miss me?' and I replied 'Not really, was busy with work'. Needless to say I lost certain privileges for a week after she was back. In short, I don't have a goodbye problem ;-)

[@Qbe_Root]

"I say SYN SYN, SYN I don't know why you say FIN-ACK I say SYN"

[@fishingtrippy]

SYN, FIN-ACK is a great song

[@gabrote42]

LOL

[@shahinza]

For some reason, I found the video both enjoyable and informative-it made learning about the problem surprisingly fun!

[@RJiiFin]

The reason is that the makers put in effort to try and make the video both enjoyable, but also informative

[@denhal1]

Just described a denial of service attack. Send 1000s of syn messages and ignore the syn ack measages.

[@ivanskyttejrgensen7464]

Those attacks can be mitigated with syn cookies. SCTP solves it by using a 4-step handshake.

[@richardclegg8027]

Can work. The better version is slow loris.

[@KyleWoodlock]

A particular kind of DOS attack, called a syn flood. Because these can be mitigated pretty easily, most DOS attacks these days are DDOS using botnets that act like legitimate traffic, just way way too much of it.

[@UNgineering]

3:45 the entire network communications can be boiled down to the 2 generals problem.

[@garryiglesias4074]

No. 10...

[@michaelharding4556]

Loving the snazzy animations, thank you 👍🏼

[@major__kong]

The way this is "solved" in the military is through everyone understanding doctrine (how you fight) and any contracts set up ahead of time when comms is good.

[@Windeycastle]

I just learned about TCP, and seeing this pop up: perfect! It's such an interesting problem.

[@prosodyspeaks4036]

great to see more vids, always look forward to them!

[@CartoType]

In practice, if the two generals have a telephone connection and hear each others voices, it works; which I suppose is equivalent to a probabilistic solution, in that an indefinite but large enough sequence of messages has passed between them, gradually increasing their confidence that the other will attack.

[@Amonimus]

Can't either/both sides ping each other periodically and if there's no response in a timeout of 60 seconds to consider the connection closed? I think it's called check-alive heartbeat or something.

[@thekaxmax]

Computationally intensive cos both need to run and monitor timers

[@fllthdcrb]

@@thekaxmax They already _do_ have timers, though. As long as the connection is open, there's always a need to wait for more packets and time it out if nothing is received for too long. (No need for pinging. Just sending or acknowledging data is enough to prove aliveness. But if no data is sent for a while, there are so-called keep-alive packets, which just repeat acknowledgment of the other side. It's like a response to a ping, but without the ping itself, because they aren't trying to measure their latency.) And even more, when sending a steady stream of data, the sender needs to regulate (with the receiver's help) the rate at which it sends, to avoid network congestion.

[@richardclegg8027]

You need a low resource low packet transmission solution because a working machine may have tens of thousands of such connections. The actual solution used is just to wait a little bit so very similar (but to part of your suggestion).

[@michaelcobb1024]

You’d essentially end up with the same exact problem. Think about the SYN/FIN packets as ping requests and the ACK packets as ping replies. You just end up with the exact same issue. How do you know if the remote host has gone or if your replies are just getting lost/corrupted/dropped?

[@thekaxmax]

@@michaelcobb1024 Timeout time==assumed not there any more. Some systems will reattempt connection after a timeout to try and get rerouted around the issue.

[@gidi1899]

It's about 'time spent waiting for establishing a connection' VS 'time spent waiting for a safe disconnection' Between Connecting and Disconnecting, any one can be more costly or take longer, and the timeouts in the protocol should reflect that.

[@Loki-]

My idea is just as unsatisfactory and would add more noise, but an "Attack" with a second delayed "Attack" by some arbitrary amount of time and same for "Received" and delayed "Received." Unsatisfactory because both can still be lost, so it just kicks the can down the road with "What if more redundancy?" Sometimes though with these problems one redundant measure is safe enough, maybe two, rarely three, but analyses are done for safety engineering for how much redundancy is statistically enough so that we don't go out of budget or over materials or some other criteria they need to remain below...

[@richardclegg8027]

You can get arbitrarily close with lots and lots of redundancy -- which for the attack problem you would definitely want to do -- for the close down problem it is not worth the time... just have the little hacky pause.

[@sabriath]

In building games, I simply attach the disconnect as part of the keep-alive protocol that I build. Basically you are sending constant update data about your movements while playing a game, so there's code that will track the average speed of the incoming data. At some points, the player may stop moving (maybe they went to the bathroom), so update data may stop momentarily, at which point the client would be programmed to send a very small KA signal in order to maintain the average speed ("speed" is not a byte-per-second but rather tied to the ack registration). During a disconnect, one side sends the FIN but doesn't really give a shit about listening anymore, it just closes down.....the other side will close down under 2 situations, whether they hear the FIN or the average speed has hit threshold, in which case it assumes closing. The data for the character is held in memory for a few minutes just in case of a reconnect (to reattach the data to the new stream connection) but otherwise it is freed as well as queue dropping (so player has to re-enter at the back). As for the server, it is always sending updates to players, so when the threshold (which is a little tighter) hits, the client will send an RN (sounds like nurse, bacronym for 'reply now') on the OOB emergency set for the server to ACK whether or not the server is either: alive and sending (which a re-establish handshake will need to be negotiated), or alive but stalled (10 sec wait before update or RN repeat). The client will attempt 2 more times within 5 seconds for an RN on silent replies before it decides that the connection was lost.....at which point a re-connect may be tried, yadda yadda. Is this not a protocol that people use? I mean, I could sell mine as a library....but I honestly thought everyone in the biz used something similar.

[@benaubrey2410]

My answer (that minimizes, but doesn't eliminate risk and requires the generals to both have a clock) would be to send a ton of messages, through different channels and at varying times stating a time to attack. When received, the receiving general sends a ton of acknowledge messages back. Infact the receiver probably doesnt even need to send acknowledge messages. Not a good idea with computers though, as bandwidth is limited.

[@jmontign1]

Wonderful explanation. I will use this

[@ivanskyttejrgensen7464]

Nice with a video about (negative/positive) proofs, and why some things are unavoidable ugly.

[@gregorymorse8423]

Time is used to engineer around the theoretical issue. Although it adds complexity and security challenges, from a practical standpoint it is not an issue

[@HupfderFloh]

7:43 it's me, Margaret

[@mattlm64]

And peers can stop responding without sending a FIN in any case. One reason keepalive and other pings exist is to check that a connection is still alive. There's never a guarantee of an orderly close and an orderly close should never be relied upon.

[@thekaxmax]

Connection timeouts are the final orderly finish

[@richardclegg8027]

That is a fair point. One computer might just die. Honestly closing distributed protocols properly is the toughest thing. It is a shame though that the orderly shut down has no satisfying solution.

[@tomaszkarwik6357]

0:31 hey dont call me out like that

[@syjwg]

You should really explain the SYN flood attack and ACK bugs. This was more of the old school "You can't trust the computers". Bugs are found everyday, but are also fixed everyday.

[@thekaxmax]

Were explained elsewhere

[@Llortnerof]

Bugs are not fixed. They're replaced by better bugs.

[@thekaxmax]

@@Llortnerof or, in the case of Microsoft starting to develop Windows NT, "These 82,000 bugs are not bugs, they're features" and took them out of the bug-fix process.

[@timbeattie4268]

I'm old enough to remember using that perforated printer paper. Didn't know they still made it.

[@Medan1993]

2 generals problem was already talked about on your channel by Tom Scott quite some time ago.

[@jort93z]

It's a well known problem, many people have talked about it.

[@CDanieleLudus]

This reminds me a lot of the Byzantine Generals' Problem introduced by Leslie Lamport

[@AlexHutan]

That's so cool, ingenious solution

[@zxuiji]

Simple: fin = normal goodbye, sht means "sh**, this is my last ditch effort to close connection, don't expect anything else" **Edit:** in the attacker example it would be like hearing the trumpet or whatever it was after missing the "attack" message

[@justsurajp]

what a wonderful analogy!

[@anve2441]

Im waiting for the rest of this video...

[@ldstalker9462]

first off, the solution with good-bye on the phone is to answer to the question "who shall say good-bye?" with a simple "you just said it, now I say it too: good bye!" and then hang up. as for the problem of the generals the solution is to use probabilistic methods, like for example a keep-alive signal. after handshake you periodically send messages and measure how many are lost. and then once probability drops to zero the other general died. for example each message could contain chess-moves to verify by checking if it is a valid move, to avoid spoofing... and instead of attacking immediately just appoint a specific time where it is highly probable you'll get an answer back. that way you confirm the time of attack is agreed upon by both by sending enough messages one of them got through, for both question and ack. as the proof said, wont guarantee the other general wasn't killed right before you attacked, nothing is 100% certain, but you get high probability you'll attack together! i.e. it's a problem with how the question is formulated, it seems to imply that we want absolute certainty. in reality however the network is totally ok with a probabilistic answer too, and this completely changes the methods available! there simply is no need for a final message like the proof claims, a lack of message could be a message on its own too...

[@oystercatcher943]

The difficulty (as you later said) is the unreliable communication network. It closer to talking to my dad on the phone who is going deaf. You never know what he heard!

[@ARKGAMING]

Saw the thumbnail and was expecting to see tom scott expanding on his 2 generals problem video

[@asagk]

I do get the principle issue with the basic protocol and "FIN" . On the other hand I am not sure why it is not even mentioned that the "Keepalive" msgs has solved the poential loss of FIN already, cause not receiving "Keepalive" for some time declares the connection as "DEAD" anyways for all protocols, including TCP/IP, that do make use of time triggered "Keepalive" msgs.

[@richardclegg8027]

@@asagk so a timeout to DEAD has a default of 15 minutes I believe. If you don't use FIN at all just let the connection dangle then every connection hangs around your client and server 15 minutes at both ends if you just stop sending. Here a shorter timer is used at one end only 2xMSL which was originally 4 minutes but on a lot of systems 1 minute. It can be tuned shorter with few bad effects to your system if you are running a busy web server with a high churn of connections. If you look at a busy server though you will see a bunch of connections in TIME_WAIT. It is all about efficiency. If you could just probably close then your system does not need to maintain them and you can squeeze more connections out of it.

[@asagk]

@@richardclegg8027 Well, what you describe is primarily a result of poor software design along with TCP usage. There is no reason to maintain connections beyond a request and its response if no further requests are planned. Keeping connections alive for several minutes while not in use is just a malicious use of TCP. So timeouts of less than 1 minute for idle connections are obviously the right way to solve this problem with bad TCP practices.

[@AlmostSeagull]

And that's why time stamps exist, so you can say "I will shut down at X:00. I ACKnowledge we shut down at X:00." Both systems are prepared and know when to shut down. I don't understand why this is a big deal.

[@rudiklein]

Have a look at any router log, like OPNsense's. It's swamped with broken FIN communications. I finally understa

[@davidioanhedges]

In reality - If the client stops sending data, then eventually the TCP connection will time out - because weather the client sent a FIN/BYE message that was not received or just got disconnected, or can't send anything, does not really matter the connection is redundant In the two generals problem - if you have sent 300 messages saying attack at 8am - and got 150 acknowledgements back sporadically saying Yes OK I will attack at 8am ... logically you should not attack - but in reality it will be fine ...

[@rickwalters8553]

I had to watch twice. The first time I couldn’t think about anything except where he found a stack of fan-fold paper in 2024

[@andrasbiro3007]

In the old days there were mountains of those everywhere. If you had just a little leftover at the end of that era, that lasts for a lifetime. Except it looks new. Probably many organizations kept using those old machines for decades, and needed a steady supply, so it's still manufactured somewhere.

[@ValidatingUsername]

Imagine people thought good bye meant they never wanted to see the person again

[@phill6859]

Tcp connection close is an optimisation. If you dont hear from them eventually, then you assume they just went away.

[@mad_circuits]

Oh no. From now on I can never say "Good bye" again and leave the conversation! 😮😢

[@bernardobuffa2391]

is this somehow connected with the two-phase-commit protocol for distributed transactions? or analog kind of problem?

[@ivanskyttejrgensen7464]

Yes, 2-phase commit is vulnerable in the same way. 3-phase commit is the kludge.

[@richardclegg8027]

Three phase commit is a little like the SYN SYN/ACK ACK open connection. After three phase we are sure both sides are alive. Two phase are not enough and we cannot be sure both sides are open.

[@bernardobuffa2391]

@@richardclegg8027 thx

[@camillagreer9028]

But it is symmetric, just *more* symmetric than you're stating, the connection ending protocol is of the same format as the connection opening protocol, it just uses message *absence* rather than message *transmission* , derived from the desired (or caused) state change.

[@richardclegg8027]

The symettry breaks because on start up both sides stay switched on listening for new packets. If there is an error and more packets are sent they will receive them. On close down the two machines want to stop listening for packets. If a machine closes the connection and there are still packets out there this can be a genuine problem. Closing a connection is an action that cannot be reversed once you do it just like the general committing to attack. If it was an error there will be a problem. On opening a connection there is no such irreversible action. Connection closing doesn't really use message "absence" except as (say) a signal to retransmit FIN if it did not get FIN ACK (symettrical with retransmit SYN if you don't get SYN ACK). If you look at the state diagram for TIME_WAIT it there is no state change depending on packet presence or absence.

[@pierpaolotofani3929]

Every time I see these interesting videos I ask myself: where do these gentlemen get the sheets of paper that were used in the printers of the last century?

[@Computerphile]

I buy reams of it from paperstone office supplies -Sean

[@paulf1071]

What about some sort of system of "keep-alive" messages between the Server and Client? A pre-agreed "finish-time" at some point in the future will be designated as the definite end of the communication. If there is any change of plan in the mean-time, then another Syn/Syn Ack loop should begin. Kind of like TTL or lease-times in a Router's settings...... Just a thought!

[@Eric_D_6]

Yeah, ultimately, everything with networking (that cares to check for a response) has to just timeout if it doesn't get the expected response in some timeout window.

[@der.Schtefan]

THANK GOD nobody uses their phone to telephone another person anymore. 12 billion transistors per phone, we solved the good bye problem with WhatsApp

[@nothingtoseehere93]

I like this guy

[@blazearmoru]

What's the problem of having the message be "Attack at [time] if [2 or more] messages come. Also don't stop sending messages until say... 4 has been recieved?"

[@ilikekitty10]

My guess is that how would first general know that they received 2 messages? First general sends a bunch and assume they got it, but if they were all intercepted the first general would be charging in alone. Or the second general receives it and sends a bunch back but they all get intercepted, so same problem as the original 2 generals problem.

[@Nope-w3c]

@@ilikekitty10 simply send the entire state of the system. for each message show if it's OK or ?? for each of the generals. After some messages you have enough history to confirm that both you and the other party have received enough messages. Problem is that the payloads gets bigger and bigger.

[@AsmodeusMictian]

@@Nope-w3c and you still just end up waiting around.... ...man that sounds familiar, doesn't it? 😆

[@SkorjOlafsen]

You're getting closer to the real world (computing, not military) solution. The real-world approach (assuming you really must coordinate) is to keep sending messages back and forth on a regular schedule. Each contains some sort of in-order numbering, and a summary of both the senders state and what the sender knows about the receiver's state. And of course you repeat all messages until they are acknowledged. This all gives enough information for both parties to judge whether you have a reliable-enough connection, and almost always come to the same conclusion. If the connection is unreliable, those parties stop trying to co-ordinate (so in the example, they wouldn't attack). This approach works well enough even for more than 2 parties. The downside is it's a lot of network traffic, and can introduce human-scale latencies when communication is iffy, so it doesn't scale past a few parties.

[@richardclegg8027]

@@blazearmoru you can't know how many have been received without a message to tell you how many have been received. That message may be lost. So if your protocol is "send 10 messages and attack if 4 are received" you end up in the same problem. The other general sends back "4 messages received" and sets off to attack but that message is lost so you don't attack. Take a look at the WP page for two general problem which lays out the proof in full.

[@miglespigles2025]

A segue, not to a sponsor??? Woa! ❤

[@NeunEinser]

Couldn't the general problem be solved by the following: - First general doesn't send "attack now", he sends "attack in an hour" - If he receives an Ack, he assumes all is well and both generals attack. - Let's say the round trip between them is about 7 minutes. - If he doesn't receive the Ack within 10 minutes, he sends another message with a new time, 60 minutes from that point. You still have some risk if 6 messages in a row are lost here, so you have to determine the time to attack accordingly to your risk.

[@LeraResan]

That doesn't work, and it's explained in the video. If the second general sends the Ack but the first general doesn't receive it, how does the second general know not to attack? He'll attack in an hour, and the first general won't - because there's no guarantee the 'attack in another hour' message will get through. It can work if the messages aren't intercepted, but that's not the problem - the problem is whether there's a way to always make it work no matter how many messages don't get through.

[@kooijbas]

Send out a new messenger every hour, until you get an answer. This is actually how reliable messaging works, you simply retry sending until you get an ack.

[@TokyoTransit]

an keep a resource locked for an hour😅

[@kirillsukhomlin3036]

Most uses TCP, but also HTTP/3 uses UDP. Not sure how widespread it is, but it will be in upcoming years.

[@pahan228_killer]

Fascinating

[@buttonasas]

I disagree. It's nothing like the 2 generals problem: there is no need to know exactly when the computer shuts down - the server doesn't care. Honestly, the server doesn't care _if_ the computer shuts down - not the server's problem. Why not just send a "after you acknowledge this, I will shutdown soon after" message? (and the server simply acknowledging it) If it goes through, just shut down. If _either message_ doesn't, just try and ask again! Heck, I thought this might introduce problems in a real scenario where the server has to clean up the connection and the client doesn't control it completely (as opposed to what was presented in the video) but if the client has the ability to send these messages indefinitely after cleanup just as if they were brand new connections (except only asking for acknowledgement and not to create anything new) and the server is fine with some clients stuck sending that junk all the time, it sounds fine? Not sure about security, though...

[@chimpana]

I don't think his General was carrying a sword...

[@refusist]

never thought about this

[@conradludgate]

This is forever a problem at work. Connections regularly close without saying goodbye. Attempting to reuse the connection occurs with spurious failures. So much time wasted on connection test messages. On internal networks (single datacenter) I often set much more aggressive keepalive frequencies because I expect the network to be fairly reliable, but quite often VMs just die without sending a FIN.

[@tasherratt]

Not the 9 o'clock News solved the problem of saying goodbye, just sat "kinda lingers".

[@frankmalenfant2828]

- Attack at noon ! - Yeah ! Got it !

[@flyguille]

Yep, just the problem I had in one software, if I JUST SEND A sck.close, and inmediately unload the socket from the array, what will happen when receiving the CLOSE ACK, IF THE socket is already killed?

[@StYxXx]

Why even wait for another response? Just assume the connection was terminated after receiving the first "fin", respond once and don't care about it anymore :D Also timeouts help in real life of course.

[@landspide]

I think the point is deterministic finalisation is possible when things are peachy, but when things go pear shaped, either side may not play fruit ninja in time, depending on where the loss is/was.

[@richardclegg8027]

The used solution is something like this. Send the FIN FIN/ACK ACK but just hang around a little in case there was a problem. It works but it is just inelegant and slightly wasteful.

[@LuukvdHoogen]

I can connect to this guy.. I can also get a bit uneasy about polling connections for instance. `So it will be checking 10 times a second? All night long? An nobody ever answers? Thats just sad..

[@franzweitkamp]

Is there really no way to flip the problem so that you send an acknowledgement of the message "if i dont receive any more messages i will attack"?

[@richardclegg8027]

It feels like there should be some solution doesn't it. Imagine green general sends "I am going to attack even if I don't hear from you again" but that message is lost. Now green general attacks but the purple general doesn't. If you want full proofs take a look at Wikipedia two generals problem

[@hughcaldwell1034]

Well, let's say you send that message, but the other general isn't ready to attack so sends a "don't attack" message which is then intercepted. You then charge in alone.

[@richardclegg8027]

​@@hughcaldwell1034exactly this. You change the problem but don't solve it. Now you have the "has the attack been called off" problem.

[@chrismarkhill]

This can happen in real life. If two people are on the phone discussing a number of important issues, with a dodgy connection, but both sides understand neither side can end the call unless both sides have agreed that they have said everything that needs to be said. If the line on one side goes silent due to a fault, then the call never ends.

[@noobnoob98noob]

Why can't the generals decide that for example a smoke signal means attack. Deciding that before the siege makes sense to me atleast.

[@patcat8950]

Now you can provide an explanation of how UDP avoids this issue but has its own problems. Sure, people might not get it, but oh well. *cough*

[@kigtod]

6:13 ‘i before e except after c’. Otherwise, a good video.

[@retropaganda8442]

Is this the same problem has distributed commit?

[@ashleycrow8867]

well a tcp connection got a timeout time, so if one server shuts down before the closure was finished then the other server doesn't recieve anything for long enough and closes the connection too

[@richardclegg8027]

This is true but that is a worse solution. If a connection just *dies* (say the network connection ceased) and no FIN FIN-ACK ACK procedure is followed then the TCP connection at both ends hangs around for 15 minutes. That's a huge amount of time for a busy web server that wants to handle thousands of connections a second. You only have a limited number of connections available at once and you want to reuse them as soon as possible. So while what you say is true it's completely a worst case. If everyone connecting to a webserver did not send FIN and just shut their end of the connection that webserver would be much less efficient.

[@VtuberMoe]

I saw tom scotts video about this problem and he talked about idempotency tokens. Does that not solve the issue or is this in a different context?

[@richardclegg8027]

It is a bit of "sleight of hand" to call that a solution to the two generals problem. It solves a slightly different but related problem. His problem was (by analogy) to stop the generals attacking twice. The usually defined two generals problem is insoluble as stated (you can look up full proofs on Wikipedia). It is cool though that he does a nice video on a problem which is related.

[@Jagentic]

If we agreed to at 10 PM say goodbye - I sent you a 10 PM goodbye request (just prior to 10pm) you sent me back an acknowledgment - I sent you an acknowledgment of your acknowledgment (and perhaps one more) and when 10 PM came and we said goodbye. Except very quickly in computer time- is that not feasible?

[@twistedsim]

Why not send, attack at 12:00 ? wait for a confirmation, then wait until 12:00 to attack..

[@dantenotavailable]

Because you don't know if the lack of confirmation is because your message got intercepted (in which case attacking gets you killed) or because the response got intercepted (in which case not attacking gets your fellow general killed). As you make the protocol more complex you reduce the probability of one of the generals dying but the point is that it's impossible to reduce the probability to 0. Also (when it comes to the technical solution), there's no shared observations, just the messages, and there's no reliably synchronised clock which makes the whole thing harder however that's irrelevant to the purist 2 generals.

[@gustavoeduard4372]

Could the possible solution of this be agreeing on unix timestamp? FIN - send a specific time for the closing connections ACK-FIN - agrees the connection close timestamp IF you don't receive the ack within a timeout of maybe 5s you send it again till you receive it?

[@richardclegg8027]

This would work but it is less efficient than the actual solution. The actual solution has one connection inefficiently waiting around consuming some resources. This solution would have both ends of the connection doing it. The point really is to avoid the inefficiency or having the connection hang about.

[@ZT1ST]

​@@richardclegg8027 It also presumes that all connections will be able to send and receive the important thing within 5 seconds, or some threshold. Some connections are choppier, or slower, or faster, than others.

[@richardclegg8027]

@@ZT1ST the defined limit is MSL Maximum Segment Lifetime which is the longest time we consider a packet could plausibly be in the network. The close here waits twice that. It was originally defined as two minutes though some people set it more aggressively.

[@JudeBcoin]

Have you heard about the glitch token known as Leilani?

[@multigladiator384]

for me personally my hardest fin was when my dad died recently :(

[@multigladiator384]

no ack at all..

[@paszTube]

5:25 green general slacking off watching a computerphile video 😂

[@T86k35]

g..g..granville get yer mop!

[@Yupppi]

Computers need "attack at dawn" message and "approved, attacking at dawn" and then waiting until dawn unless the message wasn't acquired and you send "attack at dawn" again and they reply again until no more "attack at dawn" message.

[@dantenotavailable]

It sounds like you're going with something similar to the "pragmatic approach" from the Wikipedia page on the problem. The important point there (which was unstated in your post) is that General A (that sends the attack message) is going to attack regardless. General B (sending the acknowledgement) will attack at the stated time(i.e. Dawn) if even one message arrives. General A retries until hearing an acknowledgement (or alternatively will just send a static number of messages... such would make the ack irrelevant). This doesn't solve the issue because if every "attack" message is lost then General B never hears the dawn attack time and so General A dies. As an aside, in the specific technical case we're talking about there isn't a dawn, we can't rely on clocks being synchronised and, even if we could, we can't rely on all sides having enough compute to be able to handle storing a timestamp for every connection that's shutting down. But that's all secondary to the detail of the original thought experiment.

[@Anonymous-df8it]

@@dantenotavailable What about only having General A attack if an acknowledgement was received?

[@dantenotavailable]

@@Anonymous-df8it Leaves you open to the chain of events where General B receives the attack message and sends the Ack but the Ack is intercepted. If your next thought is "ok they need to get X acknowledgements" then shift where the messages get lost to the last acknowledgement. If you think "ok A sends attack messages until they get any acknowledgement from B and attacks only if they get that acknowledgement" is vulnerable to all acknowledgements being lost. The key to the pragmatic approach is not that it solves the problem (there's no guarantees that both attacks go in) but the probability of failure is much less.

[@likebot.]

I Never Can Say Goodbye: - Gloria Gaynor

[@TheCommuted]

If you have a standing order to attack at a future time which resets if it is cancelled requiring an ack.

[@DedmenMiller]

Say you want to reset. A tells B to reset. B sends ack back, but the ack gets lost. B got reset, and send ack. They did do the reset. A never got an ack, and thinks B never got the message. A is not reset, but B is.

[@richardclegg8027]

If the generals both arrive with a standing agreement to attack because they were able to meet before hand and reliably agree that just works. The idea you might be able to cancel it gets into the reverse problem. One general sends cancel, the other does not receive it and attacks and gets killed.

[@plonkster]

So the kludgy solution is wait-closed :-)

[@lijath]

Yeah you use a timeout.

[@ksenom256]

This video was surprisingly funny and entertaining. The word "fin" means a part of a fish 🐟 in English and "FIN" is the standard abbreviation of Finland. 🙂

[@RealCadde]

Modern phones will still tell you when the connection has closed. For the generals problem, you just keep "chatting away" until you can be reasonably sure that both of them know to attack at some set time. Beginning the conversation with "I will attack at noon" and responding with "Sure, attack at noon". Then, talk about what you'll have for dinner or whatever. If both generals are reasonably certain about what's for dinner, they can be absolutely certain they both know when to attack.

[@fiddley]

still doesn't solve the problem if messages start going missing at the threshold between 'sort of sure' and 'reasonably sure', which may be different for both Generals and thus one General still may attack alone.

[@RealCadde]

@@fiddley Yes you can, if you get an out of order packet, you know you've lost one along the way. And as long as the packet ordering is preserved, you can be reasonably sure that the packets before that have been delivered.

[@fiddley]

@@RealCadde It doesn't matter what scheme you introduce, there is *ALWAYS* some uncertainty as to whether both generals will attack. You can make the uncertainty very small, but never zero. This is *mathematically* proven so despite what your common sense is telling you, you're wrong. Go check out the WP article.

[@RealCadde]

@@fiddley If you can be sure that you have gotten to this point in a conversation then you can be sure that everything prior to it has been sent and received. Refuting that is flat earther territory IMHO.

[@fiddley]

@@RealCadde Are you really comparing flat earth with a mathematical proof? Cool you do you. Have a nice day 😆

[@marklonergan3898]

Just as an idea, TCP reliability relies on the sender to assume lost packets and resend. What it if was the other way around? What if instead, the receiver was in charge of handling reliability? I.e. instead of: Sender - Msg2 Receiver - ACK Msg2 Sender - Msg3 Receiver - ACK Msg3 ... Do Receiver - REQ Msg2 Sender - Msg2 Receiver - REQ Msg3 Sender - Msg3 ... On the surface they seem the same, but it does allow for a slight modification at the end. Receiver - REQ Msg101 Sender - Msg101 Receiver - REQ Msg102 Sender - Msg102 FIN That way the FIN is in the final message itself. Given that the receiver is in charge of reliability, the receiver will send another REQ if it didn't receive the packet, so a simple timeout after last message would suffice. I know the immediate point is that the sender doesn't KNOW the last message was received, but as this whole video points out, that's already an issue with the current system. As a benefit though, the server that has many simultaneous connections isn't sending out unnessessary duplicate messages because it didn't receive an ACK. I would assume this would reduce line congestion coming out of the server given that the potential unnecessary duplicate messages would be on the client side.

[@jocamar15]

Well that's the crutch he mentioned at the end of the video, the sender has to wait a bit on the line to see if the receiver actually got the final message, before hanging up. So it's essentially the same issue and same solution.

[@richardclegg8027]

The thing is a timeout at the end of the last message is already the actual solution. It is not a big deal it is just a little inelegant. In a busy system you often see a lot of them just hanging about waiting. Does not cause a lot of harm but just a bit annoying where the opening protocol is tighter.

[@marklonergan3898]

@@jocamar15 I see what you're saying, but with onus of reliability on the sender, timing-out without knowing if the last message was received feels like it's not doing it's job properly, whereas if onus was on the receiver, then timeout feels more-correct, as it's up to the receiver to say "actually I didn't get that packet". So even though I accept this doesn't solve the theoretic issue (which is unsolvable), I do feel that is does render the issue slightly more moot. Original issue aside though, I do believe it would add the benefit of lowering the network congestion at the server-side slightly. I'm not sure if my original post explained why I believe this well enough, but I was conscious of how long the post was already.

[@marklonergan3898]

@@richardclegg8027 even with the timeout, if onus was on the receiver under the model above, a final courtesy ACK to the final message could be sent. It would be sent purely as a fire-and-forget, but it would at least close a high percentage of connections rather than having them all wait on the timeout.

[@landspide]

Ah, but have you considered Quantum entanglement. 🎉

[@SiMeGamer]

So do they even send a "FIN" message at all or was that just a hypothetical to demonstrate the problem? I understand that it cannot be verified due to the problem being unsolvable but is that packet even sent at all just to save on server "resources" or smth?

[@rmsgrey]

I imagine you still send a FIN just to be courteous - you just limit how many times you resend it without receiving a response before giving up and dropping the connection without a confirmed termination.

[@richardclegg8027]

You send the FIN FIN/ACK ACK but hang around just a little in case there's a need to send the last one again.

[@chanpasadopolska]

Blockchain like Solana can be the solution

[@31redorange08]

6:08 *received

[@MichaelOfRohan]

Next time can you have him say "til its cool, just cool" Just once please? For me?

[@Shmeeeed]

Please give me an extension 🙏🏽🙏🏽🙏🏽