Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Publications de Bernadette Charron-Bost
Publications
Reductions in Distributed Computing.
Part II: k-Threshold Agreement Tasks
Submitted. Available from ArXiv as number cs.DC/0412116 PDF
-
Postscript
We extend the results of Part I by considering a new class of agreement
tasks, the so-called k-Threshold Agreement tasks.
These tasks naturally interpolate between Atomic Commitment and Consensus.
Moreover, they constitute a valuable tool to derive irreducibility results
between Consensus tasks only.
In particular, they allow us to show that (A)for a fixed set of processes,
the higher the resiliency degree is, the harder the Consensus task is,
and (B) for a fixed resiliency degree, the smaller the set of processes
is, the harder the Consensus task is.
The proofs of these results lead us to consider new oracle-based reductions,
involving a weaker variant of the C-reduction introduced in Part I.
We also discuss the relationship between our results and previous ones
relating f-resiliency and wait-freedom.
Reductions in Distributed Computing.
Part I: Consensus and Atomic Commitment Tasks
Submitted. Available from ArXiv as number cs.DC/0412115 PDF
-
Postscript
We introduce several notions of reduction in distributed computing,
and investigate reduction properties of two fundamental agreement tasks,
namely Consensus and Atomic Commitment.
We first propose the notion of reduction
`` à la '' Karp,
an analog for distributed computing of the classical Karp reduction.
We then define a weaker reduction which is the analog of Cook reduction.
These two reductions are called
K -reduction and C-reduction, respectively.
We also introduce the notion of C*-reduction which has no
counterpart in classical (namely, non distributed) systems, and which
naturally arises when dealing with symmetric tasks.
We establish various reducibility and irreducibility theorems with
respect to these three reductions. Our main result is an incomparability
statement for Consensus and Atomic Commitment tasks: we show that they are
incomparable with respect to the C-reduction, except when the resiliency
degree is 1, in which case Atomic Commitment is strictly harder than
Consensus. A side consequence of these results is that our notion of
C-reduction is strictly weaker than the one
of K-reduction, even for unsolvable tasks.