1
$\begingroup$

Looking at a "Distributed" algorithm from a textbook on distributed algorithms (e.g. Building a spanning tree, Broadcast/Convergecast.) I found that one can implement it using Golang's concurrency primitives (i.e channels and goroutines)

AFAIK "distributed" means things are happening on multiple machines. But this is running in a single process. (the fact that all threads are sharing memory is irrelevant since the algorithm's implementation doesn't depend or make use of it)

So can we call the system consisting of the threads + channels a distributed system? This seems to have all characteristics:
- threads run independently and in parallel much like nodes (assuming enough processors)
- communication via message-passing

If we choose to not call it a distributed system, then why is the algorithm labeled distributed if it can run on a non-distributed system?

$\endgroup$
1
$\begingroup$

From Wiki:

Distributed algorithms are a sub-type of parallel algorithm, typically executed concurrently, with separate parts of the algorithm being run simultaneously on independent processors, and having limited information about what the other parts of the algorithm are doing.

It is inherent type of algorithm to be run independently with no requirement that processors are in the same machine. Think of it as the type of workload being cut into independent pieces.

From Wiki:

A distributed system is a network that consists of autonomous computers that are connected using a distribution middleware. They help in sharing different resources and capabilities to provide users with a single and integrated coherent network.

So the algorithm is distributed, but the system you have described is not. This is just algorithm with different purpose run in less distributed environment with potential to be sub-optimal in such setting.

Another example: you can run sorting network (say bitonic sort) in one thread, it doesn't make it serial algorithm, but overhead is costly in such case.

$\endgroup$

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.