# Parallel vs Distributed Algorithms

Let me clear first that I am not asking about parallel (data/task) or distributed computing architecture. A lot had been discussed here. I am just asking a plain theoretical question. What is core principal difference between Parallel and Distributed Algorithms? Below are my under standings:

In parallel algorithms (task parallelism), A big task is divided into two or more sub tasks and each sub task is executed by one processing element (PE) parallely. All sub tasks are depended on each other. What I further understand, a parallel algorithm can be coded using OpenMP which runs on multiprocessors as well as can be coded using MPI which runs on message passing systems. on the other hand, in distributed algorithm, every processing element or node executes the same copy of algorithm. They are totally independent and exchange messages to achieve the common goal. I think distributed algorithms are designed only for multi-computer systems.

It is requested to provide parallel and distributed algorithm for a same example problem for better understanding.

An algorithm is parallel if there are several processes (tasks, threads, processors) working on it at the same time. Often the tasks run in the same address space, and can communicate/reference results by others freely (low cost).

An algorithm is distributed if it is parallel and the tasks run on separate machines (separate address spaces), one task has no direct access to the work of the others. It has to request needed data, or just wait until it is sent to it.

Yes, it is a fuzzy distinction.

• I have to disagree a bit: spawning tasks is concurent, not parallel. And distributed programming differs from parallel - there is additional effort to synchronize machines, prepare to losses in machines during computation and data losses in transmission, so it is to be handled. It overlaps, but distributed is about heterogenous environment, and parallel is about ability to work in parts no matter the schedulling. Operating on same adress space is about latency. – Evil Dec 27 '15 at 1:14
• @EvilJS I guess the implicit assumption is that tasks are run in parallel on multiple processing units. – Raphael Jan 1 '16 at 12:07

One important quantitative distinction is that communication often costs more in distributed computing than in parallel computing.

An important qualitative distinction is that distributed algorithms often must deal with failure (e.g., one machine crashes, one machine starts misbehaving and sending spurious messages, or messages get lost or corrupted). In contrast, parallel algorithms typically assume there are no failures and do not have to deal with failures. Thus in the distributed algorithms literature we get algorithms for consensus, Byzantine fault tolerance, and more; those are issues that are specific to distributed systems and normally don't arise in parallel computing (or don't have much importance there).

The terms can mean almost anything, but I will try to present here one way in which the terms "parallel algorithms" and "distributed algorithms" are understood. Here we interpret "distributed algorithms" from the perspective of "network computing" (think: algorithms that keep the Internet running).

I will use as a running example the problem of finding a proper 3-colouring of a directed path (linked list). I will first describe the problem from the perspective of "traditional" algorithms — those are also known as centralised algorithms, to emphasise that they are not distributed, or sequential algorithms, to emphasise that they are not parallelised.

## Centralised sequential algorithms

The model of computing is e.g. the familiar RAM model.

The input is a linked list that is stored in the main memory of the computer. There is a read-only array $x$ with $n$ elements; node number $x[i]$ is the successor of node number $i$.

The output will be also stored in the main memory of the computer. There is a write-only array $y$ with $n$ elements.

We need to find a proper colouring of the list with $3$ colours. That is, for each index $i$ we must choose a colour $y[i] \in \{1,2,3\}$ such that $y[i] \ne y[j]$ whenever node $j$ is the successor of node $i$.

There is a single processor that can directly access any part of the main memory. In one time unit, the processor can read from main memory, write to main memory, or perform elementary operations such as arithmetic or comparisons. The running time of the algorithm is defined to be the number of time units until the algorithms stops.

Clearly, the problem can be solved in time $O(n)$, and this is optimal. For the upper bound, follow the linked list and colour the nodes with e.g. colours $1,2,1,2,\dotsc$. For the lower bound, observe that we need to write $\Omega(n)$ elements of output.

## Parallel algorithms

The only difference between parallel and sequential algorithms is that we will use the PRAM model instead of the RAM model. In the PRAM model we can consider any number of processors, but here a particularly interesting case is what happens if there are precisely $n$ processors.

While we will have multiple processors, there is still just one main memory. As before, the input is stored as a single array in the main memory, and the output will be written in a single array in the main memory.

Now in one time unit, each processor in parallel can read from main memory, write to main memory, or perform elementary operations such as arithmetic or comparisons. Some care is needed with memory accesses that may conflict. For the sake of concreteness, let us focus on the CREW PRAM model: the processors may freely read any part of the memory, but concurrent writes are forbidden.

Now in this setting it is not at all obvious what is the time complexity of $3$-colouring linked lists. Perhaps we could solve the problem in $O(1)$ time, as we have $n$ processors, and only $n$ units of input to read and $n$ units of output to write?

However, it turns out that the time complexity of this problem is precisely $\Theta(\log \log^* n)$. So it can be solved in almost constant time, but not quite.

## Distributed algorithms

Now things change radically. The model of computing is e.g. the LOCAL model, which has very little resemblance to RAM or PRAM.

There is no "main memory". There are no "arrays".

We are only given a computer network that consists of $n$ nodes. Each node is labelled with a unique identifier (say, a number from $\{1,2,\dotsc,n\}$). Each node has two communication ports: one port that connects the node with its successor, and one port that connects it with its predecessor.

The same (unknown) computer network is both our input and the tool that we are supposed to use to solve the problem. Each node is a computational entity that has to output its own colour, and the colours have to form a proper colouring of the network (i.e., my colour has to be different from the colours of my neighbours).

Note that everything is distributed: no single entity holds the entire input, and no single entity needs to know the entire output.

All nodes run the same algorithm. In one time unit, all nodes in parallel can send messages to their neighbours, receive messages from their neighbours, or perform elementary operations. The running time of the algorithm is defined to be the number of time units until all nodes have stopped and produced their local outputs.

Again, it is not at all obvious what is the time complexity of $3$-colouring. It turns out that it is precisely $\Theta(\log^* n)$.

From this perspective:

• Research on parallel algorithms is primarily about understanding how to harness the computational power of a massively parallel computer. For practical applications, consider high-performance computing, number-crunching, multicore, GPU computing, OpenMP, MPI, grids, clouds, clusters, etc.

• Research on distributed algorithms is primarily about understanding which tasks can be solved efficiently in a distributed system. For practical applications, consider computer networks, communication networks, social networks, markets, biological systems, chemical systems, physical systems, etc.

For example:

• If you want to know how to multiply two huge matrices efficiently with modern computer hardware, it may be a good idea to first have a look at research related to "parallel algorithms".

• If you want to know if there is any hope people could form stable marriages in their real-world social network, by just exchanging information with those whom they know, it may be a good idea to first have a look at research related to "distributed algorithms".

Once again, I emphasise that this is just one way in which the terms are used. There are many other interpretations. However, this is perhaps the most interesting interpretation in the sense that e.g. PRAM and LOCAL are radically different models.

As many other answers show, another possible interpretation is to understand "distributed algorithms" from the perspective of e.g. distributed high-performance computing (computer clusters, cloud computing, MPI, etc.). Then you could indeed say that distributed algorithms are not necessarily that different from e.g. I/O efficient parallel algorithms. At least if we put aside e.g. issues related to fault tolerance.

Incidentally, there is apparently some interest in the community to make the terminology slightly less confusing. People occasionally use the term distributed graph algorithms (cf. http://adga.hiit.fi/) or the term network computing to emphasise the perspective that I described here. However, there is not that much pressure to do that, as we can use formally precise terms such as "LOCAL" and "CONGEST" for distributed graph algorithms, "PRAM" for parallel algorithms, and e.g. "congested clique" and "BSP" (bulk synchronous parallel) for various in-between cases.

## References

You should distinguish two concepts that are orthogonal:

• system architecture, which can be shared or distributed, meaning that the processing elements have direct access to common resources or on the opposite manage some local resources and can only access the resources of their fellows through them;

• programming model, which can be synchronous (SIMD) or asynchronous (MIMD), meaning that the processing elements execute the same instructions concurrently or independently of each other; one can further distinguish the case where the processing elements use the same code (SPMD) or different pieces (asymmetric processing).

Parallel is a general qualifier that can cover any form of multiprocessing. Distributed is more related to loosely coupled systems.

Multicore parallelism falls in the shared-memory MIMD category. GPGPU supports a mix of shared and distributed memory, operating in a kind of multi-SIMD mode. PC farms are clearly distributed MIMD.

There is no strict theoretical distinction between a parallel algorithm and a distributed one. The meaning of these terms is derived from their conventional use in computing.

A parallel algorithm is one that can be executed by a parallel computer. Here, parallelism refers only to the fact that the computer can execute multiple sequential programs simultaneously. (Strictly, even some sequential processors could be called parallel because they execute instructions simultaneously, but this is not the conventional usage of the term parallel computing.) The use of the term parallel algorithm also does not imply anything about the programming model or structure of the algorithm (i.e. whether it is shared memory, written in OpenMP or SIMD, MIMD etc.).

A distributed algorithm is one that can be executed by a distributed computer, which consists of multiple processors with separate memories. The processors are connected by a communication network allowing them to transfer data between themselves. Typically, distributed computing refers to supercomputers or grid processing systems, however, there are examples of distributed chip multi-processor architectures such as the MIT RAW and Kalray MPPA processors. As with parallel algorithms, the use of the term distributed algorithm also does not imply anything about the programming model or algorithm structure. Indeed, it is possible to implement shared memory with a distributed algorithm.

By no means distributed nodes are SIMD or homogenous.

IMO, distributed means that computers are separated is space. The further you separate computing nodes the more distributed your system is. Parallel computing is also distributed but it is not that obvious if it runs within single processor.

That is why you deal with node and transmission failures when regard distributed computing. If all your computation is parallel, it fail at once if your processor is down. It all goes down if something bad happens in that location. The distributed nodes can fail independly however and can experience communication failures when distributed over wide area in space. They can provide redundancy. You also distribute your redundant data to reduce the risk of loosing it.

Another answer also agrees with this point. It identifies multicomputers with distributed whereas says that multiprocessor is parallel. They both are parallel and distributed but there are more chances that you abandon the common memory at larger distances so you can speak about distributed here.

This also accommodates the definition given in the most popular answer as soon as we understand that shared-mem threads are basically virtual multiprocessors whereas private-memory processes are virtual multicomputers. Here again, shared mem computing nodes are called 'parallel' computing nodes whereas more loosely coupled private mem coputing nodes are 'distributed'.

It seems that multiprocessor/multicomputer is a computer engeneering division whereas CS community prefer to speak in SW terms of threads and processes.

Distributed computation can even be sequential. Yes, client may make a blocking call to a web-server, which makes blocking calls to DB. There is not parallelism in this model but there is a distribution -- all components are located in different places.

• I demand something that is quite possible: scientific rigor. If you can not provide evidence -- proofs, studies, references to literature -- no one will believe you. So take my comment as well-intentioned advice, not an opener for discussion. As long as you can not back your statements with evidence, there can and will be no discussion (at least not with me). – Raphael Jan 6 '16 at 16:03
• @Raphael en.wikipedia.org/wiki/Distributed_computing#Introduction starts saying that 'distributed' refers to 'geographical separation'. I hate when people cast invalidity upon things which make more sense than others. You should challenge the less adequate things in the first place not say that correct, reasongable, meaningful and logical ones are less valuable and meaningless just because they are not supported experimentally, as aren't supported the others. – Valentin Tihomirov Jan 10 '16 at 11:56