Is there a set of canonical distributed systems problems from which all the possible distributed system problems can be reduced to?
I'm unaware of such a published list of problems.
Keep in mind that there are many different (and somewhat incomparable) models in distributed computing, ranging from the "benign" synchronous (fault-free) model where nodes execute in lock-step rounds and all messages are delivered
reliably in each round, to the asynchronous model where there are no bounds on
processing speeds and message delays and nodes themselves might crash or send
corrupted messages.
To further add to this variety, there are other requirements and assumptions
that are orthogonal to synchrony and faults: the initial knowledge of nodes
(network size, diameter of the network, maximum node degree, etc.), the ability
to query a failure detectors, whether nodes have unique identifiers, atomicity
of send & receive steps, the maximum size of a single message, and many more.
The actual model at hand often implies a very different nature of
question. (See [1] for more elaboration on these $2$ sub-communities in distributed computing.)
In models that are close to the fault-free synchronous model, researchers often
look at the complexity of local computation, for example, "What is the time and message
complexity for computing a vertex coloring?"
When looking at failures on the other hand, the questions are more related to solvability issues like "Is consensus solvable in this model?" or "Can we implement this fancy
failure detector under these assumptions?"
If there is not a canonical list what is the current list of problems and what reductions exist?
There are many examples of such reductions in certain distributed computing
models, I'll limit my answer to the following 2:
Local computation in the (fault-free) synchronous model
[2] show reductions between many optimization problems, for example, Minimum Dominating
Set, Maximal Independent Set (MIS), Maximal Matching (MM), and Minimum Vertex
Cover (MVC): In particular, [2] show a lower bound of $\Omega(\sqrt{\log n} +
\log\Delta)$, where $n$ is the network size and $\Delta$ the max degree, for
computing a constant approximation of an MVC. From this, the same bound follows
for computing an MM, since any maximal matching is also a $2$-approximation of
an MVC. From this, you also get a bound on computing an MIS, because an
MIS-algorithm $A$ can be used to compute MM by simulating the execution of $A$
on the line graph.
Asynchronous Model with Crash Failures
Here the most studied problem is
fault-tolerant consensus and its many variations, since implementing basic primitives like atomic broadcast and or a synchronizer themselves require consensus.
For example, assuming access to failure detectors [3], gives rise to a classification of problems by looking at
the power of their respective failure detector.
We say that failure detector $S$ is the weakest failure detector for problem $P$, if, given any failure detector $T$ for $P$, you can also implement $S$.
Using this relation, we can define problem $P$ as being harder than problem $Q$, if
the weakest failure detector for solving $P$ can implement the weakest failure
detector for solving $Q$.
It has recently been shown that every problem has a weakest failure detector [4]; note however, that [4] is an existential result. For some problems, e.g., consensus, the weakest failure detector is known [5], while for other problems, e.g., $k$-set agreement, the weakest falure detector is still open [6].
For example, I would say very naively that the leader election and mutual
exclusion problems can be reduced to the consensus problem.
Sure, if you can solve consensus, you immediately have an algorithm for leader
election: Simply use the ID of each node as the input for the consensus
algorithm. The opposite way only holds in models where it is guaranteed that the leader is eventually known to all.
[1] Pierre Fraigniaud: Distributed computational complexities: are you volvo-addicted or nascar-obsessed? PODC 2010.
http://doi.acm.org/10.1145/1835698.1835700
[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Local Computation: Lower and Upper Bounds. CoRR abs/1011.5470 (2010)
http://arxiv.org/abs/1011.5470
[3] Tushar Deepak Chandra, Sam Toueg: Unreliable Failure Detectors for Reliable Distributed Systems. J. ACM 43(2): 225-267 (1996).
http://doi.acm.org/10.1145/226643.226647
[4] Prasad Jayanti, Sam Toueg: Every problem has a weakest failure detector. PODC 2008: 75-84.
http://doi.acm.org/10.1145/1400751.1400763
[5] Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg: The Weakest Failure Detector for Solving Consensus. J. ACM 43(4): 685-722 (1996)
http://doi.acm.org/10.1145/234533.234549
[6] Michel Raynal: Failure Detectors to Solve Asynchronous k-Set Agreement: a Glimpse of Recent Results. Bulletin of the EATCS 103: 74-95 (2011)
http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/61
