The Greatest Common Divisor algorithm computes the maximal number that divides its two arguments—and can be used as an efficient random-number generator.
The Byzantine Generals Problem is an agreement protocol that's built around an imaginary General who makes a decision to attack or retreat, and who must communicate his decision to his lieutenants.