To: seminaire@pauillac.inria.fr
From: James.Leifer@inria.fr
Subject: SEM - INRIA : Moscova - 24/09/04 - Paris - FR

      Vous pouvez maintenant vous abonner à nos annonces de séminaires
             http://pauillac.inria.fr/seminaires/subscribe.html


                             S E M I N A I R E
                                         . ___ 
                           /   _   _      /   _   /
                          /   / \ / \  / /   __| /
                         |___ |_/ |_/ / |__ |_/ |_
       ___      .                  /    
      /    ___   __  /_  _   /   _/        /| /|  _   __ __ _       _ 
     /    /   / /_  /   __| /             / |/ | / \ /_ /  / \ | / __|
    |___ /   / __/ |_  |_/ |_            /     | |_/__/ |_ |_/ |/ |_/
                                                
                          I N R I A - Rocquencourt
                           Amphi Turing du Bat 1.

                        Vendredi 24 septembre, 10h30

                          -----------------------
                          Bernadette Charron-Bost
                          -----------------------

                   Laboratoire STIX, École Polytechnique

    ====================================================================
    Reductions in Distributed Computing: Applications to Agreement Tasks
    ====================================================================

In this talk, 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 "\`a 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 establish various reducibility and irreducibility theorems with
respect to these two 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.

Finally, we introduce a third notion of reduction which measures the
hardness to solve a task in terms of the information about failures
required to solve the task. We prove that this latter reduction is
strictly weaker than the $C$-reduction. In other words, the
information about failures -- or equivalently, the weakest failure
detector -- needed to solve a task does not entirely capture the
hardness of the task.