> In the worst-case though, wouldn't it just be equivalent to a non-async version of the program?

No. You can absolutely stall (I'm hesitant to use the phrase deadlock because you're not locking, specifically) an async program. More specifically, you can block all of the available scheduler threads. To see for yourself, spawn a bunch of async tasks in a loop that all increment and print a shared counter and then sleep forever. The counter will stop incrementing at some point. Compare that number to the number of scheduler threads your runtime uses. It should look similar.

I think maybe you're conceptually comparing a single threaded Rust program to an async program, which isn't quite accurate. A "normal" program in my experience has many threads. All of these threads can block. One of them blocking does not inherently slow down the rest of the program. Try the above example but spawn a new thread instead of a new async task during each loop iteration. The number will increment much higher, at least until you've exhausted some system limit on the number of threads a process can have.

Maybe there are fancy async runtimes that dynamically expand their threadpool as the number of blocked tasks increases. But naively they all use a threadpool sized at some multiple of the number of real cores your system has, and so will eventually stall if starved.

In any case, it's not generally async-safe to block any thread, ever (obviously if you could prove that the number of async tasks that block is always less than the number of threads the runtime uses, this doesn't hold, but that's a rather wild assumption). And it's impossible for say a library to know the context in which it's being used, so it's never correct for a library that is to be called in an async context to block. It must always yield.

You're right that in the common case things will just appear to slow down since most things don't block for a long time and eventually continue. But there are gnarly edge cases where the entire program stalls. Hence my comparison to memory safety. In the common case memory corruption and dangling pointers aren't horrible they just sometimes cause spurious errors which most programs can recover from. But every once in awhile they cause really bad problems which programs can't recover. Hence why we care.

For a real world example, imagine a server that processes requests. In the async handler block, for some requests you access the filesystem and the device starts experiencing degraded performance due to media errors and read calls never complete. Should the server stop processing healthchecks because some of the requests are having trouble? The answer is almost certainly no. Instead the server should report in its healthcheck that one of its block devices has an increased error rate and tasks are piling up.

Another case would be one involving locks. If you are dealing with a program that involves many workers/consumers waiting for a producer to produce a value and the workers use a blocking api to wait on a semaphore before reading a next value from memory and continuing, the program will almost certainly deadlock not because of a logic error leading to an imbalanced semaphore but instead because the async runtime will stall and the producer will never produce a value. If instead the tasks yield as they should, the program would progress normally.