Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

So I'm a senior in college and a couple of weeks ago, I interviewed at Microsoft for an entry-level SDE position. While most of the interviews (out of the total 7) were on the general principles of data structures and algorithms, one of the interviewers asked me if I knew anything about distributed computing.

I replied that, while I haven't had a course on 'distributed computing' per se, I'd like to take a stab at the question. He proceeded to ask a question on mutexes and semaphores that was covered in our operating systems course, and I thought was more about parallelism and concurrency than distributed computing.

Having gone through this experience, I am led to wonder as to what exactly constitutes distributed computing? Do multiple parallel threads trying to synchronize for access to a resource constitute a problem in the domain of distributed computing?

share|improve this question

closed as too broad by gnat, MichaelT, GlenH7, Kilian Foth, jwenting Nov 6 '14 at 12:24

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

It is strange they've asked about mutexes and not Pi-calculus. – SK-logic Oct 19 '11 at 7:34
SETI@Home and it's BOINC offshoots, are probably the most famous examples, though they are not necessarily typical. Parallelism is the most fundamental starting point for distributed/grid computing, and the synchronization of multiple threads of work, whether in "real" time on one machine or more spread out as in SETI is an inherent part of that. – kylben Oct 19 '11 at 12:28
Favorite quote: You know you have a distributed system when the crash of a computer you’ve never heard of stops you from getting any work done. - Leslie Lamport – sdg Oct 19 '11 at 12:58
up vote 6 down vote accepted

Having gone through this experience, I am led to wonder as to 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 and 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 Commit 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.)

share|improve this answer
+1 - This is the most acurate and detailed answer. – mouviciel Oct 19 '11 at 9:57
@mouviciel: Thanks. I was trying to distinguish it from traditional parallel computing (i.e., with pthreads, OpenMP or MPI) and it's the nature of the messaging and the time it takes for things to happen that really matters. – Donal Fellows Oct 19 '11 at 10:37
...and byzantine generals in the quest of the holy grail of a "global state". – mouviciel Oct 20 '11 at 7:55

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.

share|improve this answer
Threads running on different machines basically can't be synchronized the traditional way of mutexes and semaphores. – Jan Hudec Oct 19 '11 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 '11 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 '11 at 11:10

Distributed computing is a computing system that has processing occurring on different computers. 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 may 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.

share|improve this answer

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.

share|improve this answer
The biggest distributed system is the internet. The only reason it works is because it's doing so many different things that (mostly) don't interfere. – Donal Fellows Oct 19 '11 at 8:10

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
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. – Donal Fellows Oct 19 '11 at 10:41
@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 '11 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.) – Donal Fellows Oct 19 '11 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 '11 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"

share|improve this answer

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