Distributed algorithm

Flowchart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≥ A yields "yes" or "true" (more accurately, the number b in location B is greater than or equal to the number a in location A) THEN, the algorithm specifies B ← B − A (meaning the number b − a replaces the old b). Similarly, IF A > B, THEN A ← A − B. The process terminates when (the contents of) B is 0, yielding the g.c.d. in A. (Algorithm derived from Scott 2009:13; symbols and drawing style from Tausworthe 1977).

Algorithm designed to run on computer hardware constructed from interconnected processors.

- Distributed algorithm

39 related topics

Relevance

Parallel algorithm

Algorithm which can do multiple operations in a given time.

Charles Babbage, sometimes referred to as the "father of computing".

A subtype of parallel algorithms, distributed algorithms, are algorithms designed to work in cluster computing and distributed computing environments, where additional concerns beyond the scope of "classical" parallel algorithms need to be addressed.

Distributed computing

Field of computer science that studies distributed systems.

(a), (b): a distributed system. (c): a parallel system.

The word distributed in terms such as "distributed system", "distributed programming", and "distributed algorithm" originally referred to computer networks where individual computers were physically distributed within some geographical area.

Two-phase commit protocol

Type of atomic commitment protocol (ACP).

Charles Babbage, sometimes referred to as the "father of computing".

It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort (roll back) the transaction.

Graph coloring

Special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.

A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible.
This graph can be 3-colored in 12 different ways.
All non-isomorphic graphs on 3 vertices and their chromatic polynomials. The empty graph E3 (red) admits a 1-coloring; the complete graph K3 (blue) admits a 3-coloring; the other graphs admit a 2-coloring.

In the field of distributed algorithms, graph coloring is closely related to the problem of symmetry breaking.

Three-phase commit protocol

Network Packet

In computer networking and databases, the three-phase commit protocol (3PC) is a distributed algorithm which lets all nodes in a distributed system agree to commit a transaction.

Maximal independent set

Independent set that is not a subset of any other independent set.

The graph of the cube has six different maximal independent sets (two of them are maximum), shown as the red vertices.
Left is a maximal independent set. Middle is a clique, K_3, on the graph complement. Right is a vertex cover on the maximal independent set complement.

Initial research into the maximal independent set problem started on the PRAM model and has since expanded to produce results for distributed algorithms on computer clusters.

Self-stabilization

Concept of fault-tolerance in distributed systems.

"M2 Mobile Web", the original mobile web front end of Twitter, later served as fallback legacy version to clients without JavaScript support and/or incompatible browsers until December 2020.

A distributed algorithm is self-stabilizing if, starting from an arbitrary state, it is guaranteed to converge to a legitimate state and remain in a legitimate set of states thereafter.

List of terms relating to algorithms and data structures

Reference work maintained by the U.S. National Institute of Standards and Technology.

Chart of NBS activities, 1915

distributed algorithm

Tuple space

Implementation of the associative memory paradigm for parallel/distributed computing.

Content addressable memory

It is used to store the distributed system state and implement distributed algorithms.

SPIN model checker

General tool for verifying the correctness of concurrent software models in a rigorous and mostly automated fashion.

The "Dining Philosophers", a classic problem involving concurrency and shared resources

Systems to be verified are described in Promela (Process Meta Language), which supports modeling of asynchronous distributed algorithms as non-deterministic automata (SPIN stands for "Simple Promela Interpreter").