It seems like protocols solve 90% of the problems that inheritance does, but with 10% of the headaches. Instead of trying to ensure that two types can both be passed to a function that only knows about the parent type, just have a parameter that says "Whatever's passed has to conform to this, I don't care what it is otherwise."
Protocols as a term have other prior art. Which shouldn’t be surprising because a protocol is also descriptive of interface boundaries between software products (such as, but not limited to, network protocols).
The term is unintuitive to me in that usage, because to me a protocol implies an exchange or a sequence of steps between two or more parties, such as in network or cryptographic protocol or a diplomatic protocol. Interfaces, however, only specify one endpoint of an interchange, in an inherently asymmetric way, and they primarily specify operation signatures, where there are often few constraints on the possible sequence of operations.
An interface can specify or be part of a protocol as a special case, but to me the term doesn’t match the general case.
An interface representing a state machine usually does not directly represent the concrete state machine, but presents an interface to interact with the state machine. E.g. for a parser state machine, submit the next token that will advance the state machine; or an operation to read out the current state, or an operation to obtain a list of the currently possible transitions.
Of course it's not impossible for the preconditions for each operation of the interface to map exactly to a protocol so that the operations permitted in each state correspond 1:1 to the state transitions of a protocol. But that is not the general case, and not how people usually think about interfaces.
I don't know if you are familiar with the term interface description language (IDL), but generally IDLs are not suitable for specifying a protocol, in the sense of specifying (among other things) the protocol's state machine. It would be misleading to call them protocol description languages.
There are other ways in which "interface" and "protocol" differ. For example, we call HTTP a protocol, and things like SOAP and REST and CORBA. But we call a concrete REST API an interface, not a protocol, and we call what is defined by a WSDL an interface, not a protocol. A protocol can be used to access an interface (I use SOAP to access a monitoring API). An interface may support different protocols (I can operate different protocols through the Unix socket interface). We talk about Linux kernel interfaces, not about Linux kernel protocols (and if we would, we would mean something different by that). The two words are not interchangeable.
An interface describes the boundary between two things. A protocol describes a behavior between multiple entities. By the implementation of an interface we mean the implementation of one specific side, the one that exposes the interface, not the one that uses the interface. An interface can exist even if no one uses it (only one side exists). The implementation of a protocol, on the other hand, is split between both sides. You can't have only a one-sided protocol. If no one uses the protocol, neither side exists, so to speak.
A lot of OOP syntax has that exact problem because you don't use a fully-qualified method name. That's actually an upside of a janky C pseudo-OOP patterns. You have to call a function, that function has one name, one way of being called. So you can usually find all the call sites with grep (modulo macro explanations or something).
I could imagine a syntax that made you specify the protocol at the call site, e.g. for an object Foo that conforms to protocol Bar with method baz, you'd have to write obj->Bar->baz() as opposed to just obj->baz(). Or alternatively, Foo->Bar->baz(obj) if you want to make any given call site discoverable.
Indeed in OOP (or in any kind of indirect call mechanisms, including ones using function pointers in C, right?) you would not find which particular method is being called, but if you are using a nominative type system with OOP, you would at least find which method of which interface is being implemented—and similarly from the call site you would find which interface is being called. So you get a set of functions that may be called, and you would get the precise list of sites they may be called from. And this you get "for free".
In your proposal by stating the name of interface you are calling you do get to see what is being called, and some protocol implementations such as the one in Python/MyPy you can name the protocol of the object you are invoking a method on.
But how about the implementation sites? I was under the impression with protocol based system you would implement a protocol by just having methods of certain names. So the set of functions that may be called would be the set of classes that happen to have a certain set of methods that conform to a protocol, which might or might not be made with the idea that they should be used in the protocol's context. You would need to rely on documentation, which isn't checked by the compiler.
Personally I think protocols are too ad-hoc for general program structure purposes, though they can have their uses. I consider both "class implements these abstract named interfaces" and traits (as in Rust) better.
Interfaces in C# are used way more often than abstract classes and inheritance. It is also becoming more important as there is more code written in Rust style with structs implementing interfaces for zero-cost dispatch through generic constraints e.g.
void Handle<T>(T value) where T : IFeature1, IFeature2...
