26

I've come across Filesystems with versioning and have been reading through the Unix Haters Handbook, linked there. I came across page 85:

On the other hand, techniques for guaranteeing synchronous, atomic operations, even for processes running on two separate computers, were known and understood in 1983...

Now to me that immediately jumped out as impossible. After all, that sounds as good as having solved the Two Generals problem, which according to Wikipedia

The Two Generals Problem was the first computer communication problem to be proved to be unsolvable.

I.e. it can't be done.

Now, I want to give the authors the benefit of the doubt. I assume when they wrote guaranteeing, they were referencing some system that existed at the time that in their opinion did just that. Were there such as systems? Or are the authors simply wrong?

| improve this question | |
  • 2
    The VAXcluster DLM would be one example, but it was released in 1984. – Stephen Kitt Feb 12 at 9:08
  • If the wiring (and logic gates, etc.) between two separate computers is as reliable as the wiring (and logic) within a single CPU, then the correctness of any synchronization logic becomes of the same order. Just slower due to the speed of light. – hotpaw2 Feb 12 at 15:32
  • 1
    "synchronous" in this case doesn't mean simultaneously like in the Two Generals problem. If machine A knows it can write, and machine B doesn't know if it can write, that is more than sufficient for safe atomic operations since they agree that B can't write even though they don't have perfect distributed state. – wrosecrans Feb 12 at 21:25
  • @worsecrans The problem of the 2 general is about comunication with assurance, non necessarily simultaneousness. Anyway, if you legitimatelly have both synchronous and atomic you can easily do the 'acknowldege' part of the problem, thus either machine considers the request agreed upon if and only if the other machine also does. And this does allow for simultaneous as long as both machines have an accurate clock, just use said method to agree on some time in the future, if the atomic operation finished before the set time just wait until then going off of the system clock. – Mr Redstoner Feb 12 at 21:53
  • I was using computer systems with multiple independent CPUs in 1979. Seemed to work OK. As with the file-systems-with-versioning question, examine your assumptions. – user207421 Feb 13 at 4:16
28

If you can ensure a reliable connection, synchronous, atomic operations can indeed be implemented using various techniques that also work for remote connections, much in the same way as they can be implemented on local multi-processor systems. The quoted claim doesn't make any statement about the distance of the separate computers or the quality of their connections: they could be next to each other and have dedicated connections just to coordinate atomic access. There are several algorithms specifically designed for networked coordination, for example the Suzuki-Kasami algorithm.

The "Two Generals" problem is about a worst-case case scenario here: how to reliably coordinate over an unreliable connection where messages may disappear. There are often ways to deal with this by introducing timeouts. This of course means possibly bad performance but depending on the operation being synchronous is more important than being fast. A lot of the distributed mutex algorithms I've seen while researching this answer do indeed break down if the communication is unreliable, they may "starve" or "deadlock".

So the quoted claim that distributed synchronous atomic operations were understood and available in 1983 is probably true when you make the assumption that you have a reliable setup with reliable connection.

One example of that era that is using network mutex are file locks on NFS. They were available in v2, ca. 1986. I guess they weren't the first to have this.

| improve this answer | |
  • On the other hand, one isn't making that assumption when one is talking about Internet electronic mail, via SMTP, over TCP, as the book in the question is. Ironically, it then proceeds to quote a war story that isn't even an instance of the problem. – JdeBP Feb 12 at 18:43
9

Not really an answer to whether there were such systems, but a comment on that section of the Unix-haters Handbook.

In the mid 1980s I implemented a (non-Unix, non-SMTP) mail sending agent that had the same "responsibility" (non-)issue: the sender required the final status from the receiver, else it would resend later, thus a window existed for potential double delivery -- if the status message got lost on its way from the receiver to the sender.

Regardless of whether I knew of these atomicity techniques, I could not have applied them because the protocol was not in my control.

Isn't that the same situation with sendmail? SMTP is what it is. After the message is at the mail receiver, it sends back OK status. There is no follow-up status about the delivery of the status. In particular, if the server has sent back OK, it now has responsibility for delivery of the message. If the client has not received OK, it still has responsibility for the message.

So, "are the authors wrong"?

Partially, I think. They may or may not be wrong about the existence of other systems that solve this problem. They are wrong about blaming Unix for this, since it is the property of the protocol.

| improve this answer | |
  • 3
    I guess it depends how you define Unix. If reduced to the kernel, then yes, it's not Unix to blame for. Then again, the whole idea of Unix is to make a phletoria of small (or not so small) tools. One for each job. And sendmail is one of them. So it's as valid to see them in total as Unix. Isn't it? The same is true for protocols that have been developed as part. To me it seams as if that's as well the viewpoint of the book. And SMTP hasn't been developed complete independent of sendmail. The addition of protocol elements about delivery and reliable handshake would have been no rocket science. – Raffzahn Feb 12 at 13:22
  • 5
    My point was it's not sendmail or Unix, it's RFC 821, that mandates that behaviour. If the client does not know for sure that the server has accepted responsibility then it must retry later. And if the server does not know for sure that the client will retry, then it must accept responsibility. – another-dave Feb 12 at 17:20
  • 1
    Neiter MTP nor SMTP was send from heaven. And Sendmail wasn't just the reference implementation of SMTP, but Allman was a major source in creating SMTP. The whole protocol grew out from its Unix (BSD) implementation. Thus blaming te unix environment isn't hitting the wrong group. – Raffzahn Feb 12 at 17:54
  • In the Real World (as opposed to the Platonic World), synchronicity isn't and atomicity doesn't. See also Worse is Better (but also "Worse is Better is Worse"), A Critique of the Remote Procedure Call Paradigm, the CAP 'Theorem' (is really more a Murphy's law than a theorem) etc. etc. Use Paxos if you must. – David Tonhofer Feb 12 at 18:00
  • 1
    And for other RFCs, see RFC 1047. Yes, this issue is SMTP itself rather than Unix or Sendmail specifically. – JdeBP Feb 12 at 18:31
4

The key to making problems like the Two Generals Problem solvable is to categorize some failure modes as annoying but tolerable. For example, a variation analogous to a mutex would have a goal of attacking the enemy with only one general's army, and regard the possibility of both generals' armies attacking at once as unacceptable (e.g. because they'd be clobbered by each others' artillery). Having both generals hold off on attacking the enemy would be undesirable, but better than having both attack.

Under that scenario, generals Bob and Joe would have three states between them: Bob expects that Joe might attack, and Joe knows he will; Joe expects that Bob might attack, and Bob knows he will; or Bob and Joe each expect that the other might attack, but neither is actually planning to do so.

If any general who wants to attack and doesn't yet know that he's clear to do so will send messages until a go-ahead is received, the only reasons the generals would remain in the third state would be if either neither wants to attack (in which case being in that state is fine), or attempts at communication continuously fail (Bob and Joe could coordinate so that an attack will be possible if 1.5 round trips are completed while at least one of them wants to attack).

Note that the original Two Generals Problem only has two outcomes: successful, and intolerable. Here, classifying the third outcome (neither general attacks) as annoying but tolerable shifts the problem from being unsolvable to being easily tractible.

Applying that to a mutex, if two entities each think the other might alter a resource without further coordination, and will thus hold off on any attempt to alter it themselves unless they are cleared to do so, one may end up in situations where neither party will be able to alter a resource in the absence of a working communications link, but it would nonetheless be possible to guarantee that nobody would alter a resource when the other party wasn't aware of that possibility.

| improve this answer | |
  • And applying that to SMTP, the protocol design choice for the annoying but tolerable state was (given the 'S' in 'SMTP') between "risk of multiple delivery" and "risk of no delivery". It seems clear to me that the correct decision was made. – another-dave Feb 14 at 12:30
  • 1
    @another-dave: Especially since multiple delivery can be dealt with by by giving each message a unique identifier, and having recipients ignore duplicates. Needlessly sending redundant messages will waste bandwidth, but should have no other adverse effect. – supercat Feb 14 at 15:00
  • There's another issue hidden in there - at least in my experience, mail was intended for, and designed for, person-to-person communication. Determining 'I have already seen this' is not tricky in that case. Once 'you' start using it for program-to-program communication, 'you' own the problems caused by that scope creep. – another-dave Feb 15 at 14:24
  • 1
    @another-dave: I think intermediary mail agents are already supposed to try to detect and drop redundant messages based on ID, rather than relay them to the final recipient. To be sure, if a mail message happens to get retransmitted after a year delay (I have actually received email messages more than a year after they were sent!), it's likely that nothing would recognize it as a duplicate, but programs that keep a list of IDs they've seen in the last six months could probably prevent duplicates by discarding any incoming mail that's over six moths old. – supercat Feb 15 at 19:15
0

it can't be done.

Really?

The two generals problem applies to any two way communication channel that does not have perfect reliability. So that means, if you phone your friend to arrange to go out for a beer, the two generals problem applies. How can you be sure that your communication exchange has worked? The reason is because when you say on the telephone "meet you at 8", you will get some sort of response pretty much straight away. But, if you don't what do you do? You repeat the message until either you do get a response or you give up.

A simple three way acknowledgement sequence is enough to establish that both parties got the message. If Alice sends the message to Bob, Bob sends an ack back to Alice and then Alice sends an ack of the ack to Bob, then both parties know that Bob got the message and both parties know that both parties know Bob got the message. Of course, Alice doesn't know that Bob knows that both parties know that Bob got the message. But if Bob is expecting an ack but doesn't get one within a certain expected time frame, he can resend his original ack.

With the possibility of resending messages and acks, you can't prove that the message has been received with mathematical rigour, but you can be reasonably confident to any desired level of probability. If you send a message with a 1% probability of failure, sending it twice has a 0.01% chance that neither message will get through, three times has a 0.0001% chance and so on.

The two generals problem is flawed in that we routinely accept things that are not completely certain. It's a mathematical problem, not a pragmatic one.

| improve this answer | |
  • There are some cases where variations of the two-generals problem can pose some real difficulties. For example, many short-range radios such as those used for Bluetooth low-energy use more power when receiving than when transmitting. If two devices are engaged in a conversation where they listen 10 times a second and one party sends another saying "I'm not going to transmit anything for the next 10 seconds", and that message is sent and successfully received, but the ack isn't received, what should happen? If the sender doesn't resend the message, the listener will... – supercat Feb 14 at 15:59
  • ...listen uselessly 100 times, burning more than 15 minutes' worth of energy. But if the listener goes to sleep before the sender retransmits the message, then no number of retransmissions will yield a response. Perhaps the listener could wake up a couple of extra times even after getting the first message so it can listen for and acknowledge retransmissions of the sleep request, but that would use extra energy in the case where everything worked. – supercat Feb 14 at 16:02
  • 1
    sending it twice has a 0.01% chance that neither message will get through, three times has a 0.0001% chance and so on that would assume that sendings are independent. That's probably an assumption you can't make when computer networks are involved. – Mr Redstoner Feb 16 at 8:43
  • @MrRedstoner and everybody else It's exactly the technique used with TCP. Of course, if there is a systematic problem with the link such as the network cable being unplugged, then you can retry forever but the point is it is not about perfection but getting things reliable enough. – JeremyP Feb 16 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.