What's the difference between a protocol and a distributed algorithm? My internship supervisor told me they are not exactly alike.

A protocol is more communication-oriented (e.g. TCP), whereas a distributed algorithm allows more complex interactions (e.g. a cryptocurrency system).

However, I still can't fully grasp this difference. Can someone enlighten me? Is it important to not conflate the two?

  • $\begingroup$ This is indeed confusing. After some thoughts of it, a "protocol" is not a very well-defined terminology and it sometimes used to denote a distributed algorithm, sometimes to denote the communication layer of interacting nodes, and sometimes to denote a tuple of algorithms executed over a given network (not necessarily distributed algorithms, i.e., algorithms that might be aware of the specific topology and differ per node; although some will call such algorithms distributed as well). $\endgroup$
    – Ran G.
    Jun 14 at 20:08
  • $\begingroup$ As mentioned in the previous comment, "protocol" is a bit overloaded and the answer will depend on the field. In Secure Multiparty Computation (en.wikipedia.org/wiki/Secure_multi-party_computation) we use the term protocol exclusively, and we really mean a distributed algorithm (with security guarantees). $\endgroup$
    – integrator
    Jun 15 at 7:59

A protocol and a distributed algorithm are completely different things.

A protocol is defined mechanism for communication that the communicating parties use to exchange information. It is the rules of the language used to carry the information.

An algorithm is a recipe for solving a problem that is made of a sequence of steps to follow that will lead to a solution.

A distributed algorithm is a recipe that uses many parties to contribute to the solution of the problem.

In a distributed algorithm the different parties may need to communicate either with each other or back to some central location where the solution is collected. They will use a communication protocol to achieve that transfer of information, so a distributed algorithm is very likely to use a protocol, but that is not the sole purpose of the protocol and that protocol can be used for many other things besides distributed algorithms.

It is very important not to conflate the two, in the same way that it is essential not to confuse chalk with cheese, otherwise it would be bad for the recipe.

  • $\begingroup$ But protocols (such as the DNS for instance) can involve quite complex behaviours. From my point of view, it seems more like a difference of degree rather than a difference of kind. $\endgroup$ Jun 14 at 19:25
  • $\begingroup$ According to your definitions, any non-trivial protocol is a distributed algorithm: the parties contribute step-by-step to solve the problem of gaining common knowledge. $\endgroup$ Jun 15 at 8:09

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.