What exactly constitutes distributed computing, and how does it differ from parallelized / concurrent computing?

Does the use of mutexes and semaphores in multiple parallel threads trying to synchronize for access to a resource constitute a problem in the domain of distributed computing?


8 Answers 8


What exactly constitutes distributed computing?

Distributed computing is an inherently parallel collection of processing elements that communicate with one another to tackle one or more problems. Those processing elements are sufficiently separated from each other that it is not practical to build a reliable and timely messaging fabric between them, and so it becomes impossible for there to be a global knowledge of the state of the system. Particular features of messaging with distributed systems are that messages will get lost, will get garbled, will get delayed — solutions in this space have to take account of this. Thus, distributed programming is about dealing with networks and messages, parallelism and a lack of global information.

The easiest method of working around the problems is to make a single processing element be special, i.e., authoritative for a particular piece of information. Then the other elements can either refer back to it every time, or cache the information and hope that it doesn't go out of date (since they can't count on being told of changes). This is the classic client/server architecture.

Internet computing is distributed computing, but without the ability to control what most of the distributed nodes really do.

Do multiple parallel threads trying to synchronize for access to a resource constitute a problem in the domain of distributed computing?

They constitute a possible solution that is useful when building the client/server model, but at a cost of a potentially dramatic increase in resource contention. For reads, that's not a very big deal (providing there's enough hardware) but for writes it's a big problem indeed.

What you try to avoid though is distributed locks. The lack of reliable timely messaging absolutely slays distributed decision protocols, unless you use something like the Paxos protocol, but that's got a lot of caveats. The fundamental problem with distributed computing is that "bad stuff happens to messages". Relatively-low level protocols, like TCP, lessen the problems, but you can still come badly unstuck.


Do multiple parallel threads trying to synchronize for access to a resource constitute a problem in the domain of distributed computing?

They do if those threads could be running on different machines, or even if they're running on the same machine but in different processes.

  • 1
    Threads running on different machines basically can't be synchronized the traditional way of mutexes and semaphores.
    – Jan Hudec
    Oct 19, 2011 at 9:20
  • @JanHudec I think that was the point of the interviewer's question. Without atomic test-and-set or compare-and-swap instructions or shared memory, distributed computing has to rely on messaging between machines for synchronization. Fortunately, there are algorithms that accomplish this.
    – Caleb
    Oct 19, 2011 at 10:56
  • I don't agree with the "fortunately". The algorithms are complicated and not fault tolerant, so they should be avoided.
    – Jan Hudec
    Oct 19, 2011 at 11:10

Distributed computing is a computing system that has processing occurring on different computers (i.e. on a distributed system). The individual programs communicate with each other through a series of communication channels. These channels are usually network connections (TCP sockets, for example), but often use other communication protocols and devices (such as DeviceNET, BACNet, SECS-2, Modbus, etc.) or even protocols that are custom made for a specific device.

Distributed systems are usually much more complicated than systems that are designed to run on a single computer. In addition to concurrency and resource locking issues that multi-threaded applications need to contend with, distributed systems need to handle communication failures, and processing node failures. Transactions (and rollback) that require multiple processors to conduct can also be tricky.

Distributed systems take on many forms and are currently used in many applications. Web applications are distributed systems. An N-Tiered system usually has at least N different processors (with different applications). Distributed systems are also used in many factory automation systems as well.

The write-up on distributed computing in Wikipedia is worth a read.

In answer to you question about whether a multi-threaded application constitutes a distributed application -- if the threads are running on a single computer, the system is not distributed. It does have to solve some of the problems inherent in distributed systems, but not all of them.


Strictly speaking "distributed computing" is any solution that involves processing a single transaction/request/calculation on more than one computer.

You will also come across the term "Distributed Systems" which is a catch all term for windows, unix and other small systems servers which would have originally deployed outside the central data center. Although its more normal for these systems to be deployed inside the data center these days the term has stuck.


To answer your general question about what constitutes distributed computing, I would recommend the paper A Note on Distributed Computing by Ann Wollrath, Geoff Wyant, Jim Waldo and Samuel C. Kendall. It covers the recent history of distributed systems and its failures, and it proposes that distributed computing requires thinking differently about the problems involved.

Though neither mutexes nor semaphores are mentioned in the paper, it provides valuable insight into the proper engineering of a distributed software system.

As to why your interviewer asked about mutexes and semaphores, I would agree with @Caleb:

They do if those threads could be running on different machines, or even if they're running on the same machine but in different processes.

The only thing I would add is that mutexes and semaphores are low level locking primitives that allow you to distribute work across multiple computing devices, and their operation is (usually) vital to the success of the application. Obviously, it depends on the language and technology used. If you're using Erlang or Scala, you'll probably use Actor model-based concurrency rather than traditional, lock-based concurrency.


The word says it all. You have to do some computing operation and if you could distribute parts of this computing such that each computing works irrespective of the other computing and then when all are done you combine the result of each computing to get the answer of main computing. Example would be : Map-Reduce


We did have a course on "distributed systems" and while I don't remember the definition exactly, it was along the lines of:

  1. can run on multiple separate nodes that communicate via messages (can't share memory)
  2. objects can be migrated between nodes
  3. objects keep their identity when migrated and can be addressed transparently when migrated
  4. objects don't depend on the node that created them
  5. the system can handle adding and removing nodes

(I believe there were some more and I am not certain about the last point)

Now in the course we did learn how to implement distributed transaction and distributed lock. The lesson is that distributed lock is basically implemented using distributed transaction, which is the other way around compared to what you do locally, and that it's inherently not fault tolerant, which rather defeats the purpose of having distributed system in the first place.

Edit: That definition is for "distributed system" in the narrow sense of operating system or database system and as opposed to merely client-server system. Anything satisfying the first condition may be called distributed in some contexts.

Coincidentally the definition matches the difference between distributed and traditional version control systems, all of which are at least client-server and often also replicated.

  • That's very much a particular style of distributed computing. There are others, and the only thing they really share is the first point. Messaging is critical, the others… not so much. Oct 19, 2011 at 10:41
  • 1
    @DonalFellows: Well, this is distributed system, in a sense of operating or database system. There the migration and fault-tolerance are the main points for doing them. Distributed "computing" is anything that runs on multiple nodes.
    – Jan Hudec
    Oct 19, 2011 at 11:31
  • Well, in that case it should have covered the business of coming to a decision. That's hard in a distributed system. (Moreover, most of the academic papers I've seen on the topic make totally unrealistic assumptions about the underlying graph topology, giving valid but useless conclusions.) Oct 19, 2011 at 11:40
  • @DonalFellows: The course of course did cover the business of coming to decision and all that arbitration and split brain stuff (not too deeply, it was introductory-level only). But that's not defining property of distributed system. It's merely a hurdle you have to jump if you want to create one.
    – Jan Hudec
    Oct 19, 2011 at 12:09

Distributed computing the the "non-marketting" term for enterprise computing which you may hear a lot more in real life. However, the general idea as pointed out by others is "you are using more than one computer to do work"

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