Must every distributed algorithm be decentralized?

No; a central coordinator can participate in a distributed computation.

Can correct local results yield a wrong global answer?

Yes. The unweighted-average and duplicate-contribution examples show two different ways.

Does distribution automatically provide fault tolerance?

No. The algorithm must address the failures it is intended to tolerate.

AI Glossary / Mathematics and optimization / Advanced

Distributed algorithm

Definition

A distributed algorithm is a procedure carried out by multiple computing participants that perform local work and coordinate through communication. Its specification describes not only the calculations but also how information moves between participants and how their actions combine to achieve an objective. In a networked setting, participants may begin with local inputs and cannot simply assume that every other participant's current state is immediately available.

What it means

The overall computation is divided across participants, but correctness belongs to the procedure. Correct local answers can still produce an incorrect overall result if they are combined improperly, counted twice or interpreted under different assumptions.
Distributed algorithms may use a central coordinator, a tree or peer-to-peer communication. It also does not by itself guarantee privacy, faster execution or tolerance of failures. Those properties depend on the algorithm, implementation and assumptions about the environment.

How it works

Specify each participant's local state, messages, update rules and output conditions. State assumptions about timing, communication and failures. A synchronous procedure may organize work into rounds, while an asynchronous procedure allows participants to advance without a common round-by-round schedule.
Analyze both local work and coordination costs. Network latency, message volume and waiting for slow participants can dominate a computation. Correctness should account for allowed message orderings and failures, rather than only the easiest execution. If the task requires termination, the specification must explain when a participant can safely conclude that enough work has been completed.

Three practical examples

A distributed analytics job computes local counts and totals, then combines them into a global statistic. The summaries must retain the information needed for the intended result; averaging local averages can be incorrect when partition sizes differ.
A distributed model-training procedure computes updates on different data partitions and combines them according to its training rule. The weighting, timing and treatment of stale updates affect which computation is actually performed.
A network of devices exchanges estimates to approach an agreed quantity under a specified communication model. Convergence and resilience depend on that model and the update rule, not merely on the existence of multiple connected devices.

Think of it this way

Think of several branches preparing parts of one report. Each branch can calculate accurately, yet the report can still be wrong if totals cover different periods or a resubmitted contribution is counted twice. The reporting procedure must define the meaning of each contribution and how completion is recognized. Local arithmetic is only one part of the coordinated task.

Worked example

Suppose participant A stores the values 10, 20 and 30, while participant B stores 70 and 90. The goal is the mean of all five values. Assume these are disjoint partitions of a fixed dataset and both participants respond successfully.
A computes a local sum of 60 and count of three. B computes a local sum of 160 and count of two. Each sends its pair to a coordinator. The coordinator adds sums and counts separately, giving total 220 and count five. The global mean is 220/5 = 44.
By contrast, the local means are 20 and 80. Their unweighted average is (20 + 80)/2 = 50, which is wrong for the requested mean. It treats the two partitions as equally influential even though they contain different numbers of records. Weighting the local means by counts gives (3 × 20 + 2 × 80)/5 = 44.
Combining pairs by (s₁, n₁) + (s₂, n₂) = (s₁ + s₂, n₁ + n₂) preserves the required total and count. Under exact arithmetic, such pairs can be combined through a tree without changing the result. The example uses small integers whose sums are exact; floating-point sums in larger computations can depend on the order of addition.
The algorithm's success also depends on knowing which partitions belong to the job and receiving each required contribution under the specified completion rule. A local total is not enough to establish that the global result is ready.

Illustrative case study

In a fictional branch-reporting system using the worked example, B resends its contribution because an acknowledgment is delayed. A naive coordinator adds both copies. It now reports sum 60 + 160 + 160 = 380 and count 3 + 2 + 2 = 7, producing 380/7, approximately 54.286.
The arithmetic is internally consistent, but the dataset has been counted incorrectly. The team gives every contribution a job identifier and partition identifier. For this fixed-snapshot workflow, the coordinator records which partition contribution has already been accepted and treats an identical retry as a duplicate rather than additional data.
The team also defines what happens when a required partition is missing. It does not silently label a partial result as complete. If partitions can legitimately change, the protocol needs version rules as well; a simple duplicate check is not a universal solution for arbitrary updates.

Common misconceptions and mistakes

More participants do not guarantee proportional speedup. Communication, coordination and serial work can limit gains. Likewise, a distributed procedure can still have a single coordinator and depend on it.
Do not assume that mathematical associativity implies identical floating-point results under every execution order. Also distinguish the algorithm's supported failure model from broader claims of reliability. A procedure designed for delayed messages may not handle participant crashes or incorrect contributions without additional mechanisms.

Business use

A distributed algorithm is useful when data, work or devices are spread across locations or when one machine cannot meet the required workload. Define the global result, the meaning of local contributions and acceptable completion behavior. Compare end-to-end performance, including communication and recovery costs. Record how partial, repeated or outdated contributions are handled so that operational monitoring can distinguish a delayed computation from a completed one.

Check your understanding

Why is 50 the wrong mean?

Answer: It gives equal weight to partitions containing three and two records.

What summaries produce 44?

Answer: The pairs (60, 3) and (160, 2).

Why did the retry produce a wrong result?

Answer: The coordinator counted one partition twice.

Related terms

Message passing
Synchronization
Fault tolerance
local state
reduction
data partition
asynchronous computation
distributed training

Learn next

Trace a small distributed reduction under different message orders. Then examine how completion detection, repeated messages and floating-point arithmetic affect the guarantees of the complete procedure.

Sources

Aalto Dictionary of Machine Learning, distributed algorithm: local computation coordinated by exchanged messages. https://aaltodictionaryofml.github.io/ADictML_Main.pdf MPI Forum, MPI-4.1, section 7.9.1, Reduce: combining process contributions and the effect of evaluation order on floating-point operations. https://www.mpi-forum.org/docs/mpi-4.1/mpi41-report/node130.htm The mean calculation and fictional retry-handling case are original teaching illustrations.

Previous: Distillation Next: Distributed algorithmic mechanism design