TPTP Problem File: SWV479+1.p

View Solutions - Solve Problem

%------------------------------------------------------------------------------
% File     : SWV479+1 : TPTP v7.4.0. Released v4.0.0.
% Domain   : Software Verification
% Problem  : Establishing that there cannot be two leaders, part i56_p116
% Version  : [Sve07] axioms : Especial.
% English  :

% Refs     : [Sto97] Stoller (1997), Leader Election in Distributed Systems
%          : [Sve07] Svensson (2007), Email to Koen Claessen
%          : [Sve08] Svensson (2008), A Semi-Automatic Correctness Proof Pr
% Source   : [Sve07]
% Names    : stoller_i56_p116 [Sve07]

% Status   : Theorem
% Rating   : 0.44 v7.4.0, 0.33 v7.3.0, 0.45 v7.2.0, 0.41 v7.1.0, 0.39 v7.0.0, 0.40 v6.4.0, 0.46 v6.3.0, 0.42 v6.2.0, 0.52 v6.1.0, 0.50 v6.0.0, 0.48 v5.5.0, 0.63 v5.4.0, 0.64 v5.3.0, 0.70 v5.2.0, 0.55 v5.1.0, 0.62 v5.0.0, 0.71 v4.1.0, 0.74 v4.0.0
% Syntax   : Number of formulae    :   67 (  40 unit)
%            Number of atoms       :  237 ( 121 equality)
%            Maximal formula depth :   33 (   4 average)
%            Number of connectives :  239 (  69   ~;  12   |; 105   &)
%                                         (  13 <=>;  40  =>;   0  <=)
%                                         (   0 <~>;   0  ~|;   0  ~&)
%            Number of predicates  :    6 (   0 propositional; 1-2 arity)
%            Number of functors    :   34 (  17 constant; 0-2 arity)
%            Number of variables   :  175 (   1 sgn; 174   !;   1   ?)
%            Maximal term depth    :    4 (   2 average)
% SPC      : FOF_THM_RFO_SEQ

% Comments :
%------------------------------------------------------------------------------
%----Include axioms for verification of Stoller's leader election algorithm
include('Axioms/SWV011+0.ax').
%------------------------------------------------------------------------------
fof(conj,conjecture,(
    ! [V,W,X,Y] :
      ( ( ! [Z,Pid0] :
            ( elem(m_Ldr(Pid0),queue(host(Z)))
           => ~ leq(host(Z),host(Pid0)) )
        & ! [Z,Pid0] :
            ( elem(m_Down(Pid0),queue(host(Z)))
           => host(Pid0) != host(Z) )
        & ! [Z,Pid0] :
            ( ( Pid0 != Z
              & host(Pid0) = host(Z) )
           => ( ~ setIn(Z,alive)
              | ~ setIn(Pid0,alive) ) )
        & ! [Z] :
            ( ( ( index(status,host(Z)) = elec_1
                | index(status,host(Z)) = elec_2 )
              & setIn(Z,alive) )
           => index(elid,host(Z)) = Z )
        & ! [Z,Pid0] :
            ( ( setIn(Z,alive)
              & setIn(Pid0,alive)
              & setIn(host(Pid0),index(down,host(Z)))
              & index(status,host(Pid0)) = elec_2 )
           => leq(index(pendack,host(Pid0)),host(Z)) )
        & ! [Z,Pid0] :
            ( ( setIn(Pid0,alive)
              & index(status,host(Pid0)) = norm
              & index(ldr,host(Pid0)) = host(Pid0) )
           => ~ ( setIn(Z,alive)
                & setIn(host(Pid0),index(down,host(Z))) ) )
        & ! [Z,Pid20,Pid0] :
            ( ( setIn(Z,alive)
              & setIn(Pid0,alive)
              & elem(m_Down(Pid20),queue(host(Z)))
              & host(Pid0) = host(Pid20)
              & index(status,host(Pid0)) = elec_2 )
           => leq(index(pendack,host(Pid0)),host(Z)) )
        & ! [Z,Pid20,Pid0] :
            ( ( setIn(Pid0,alive)
              & host(Pid20) = host(Pid0)
              & index(status,host(Pid0)) = norm
              & index(ldr,host(Pid0)) = host(Pid0) )
           => ~ ( setIn(Z,alive)
                & elem(m_Down(Pid20),queue(host(Z))) ) )
        & ! [Z,Pid0] :
            ( ( setIn(Z,alive)
              & setIn(Pid0,alive)
              & index(ldr,host(Z)) = host(Z)
              & index(status,host(Z)) = norm
              & index(status,host(Pid0)) = norm
              & index(ldr,host(Pid0)) = host(Pid0) )
           => Pid0 = Z )
        & ! [Z,Pid20,Pid0] :
            ( ( ~ leq(host(Pid20),host(Pid0))
              & setIn(Pid0,alive)
              & elem(m_Down(Pid20),queue(host(Pid0)))
              & host(Pid20) = host(Z) )
           => ~ ( setIn(Z,alive)
                & index(ldr,host(Z)) = host(Z)
                & index(status,host(Z)) = norm ) )
        & ! [Z,Pid30,Pid20,Pid0] :
            ( ( host(Pid20) != host(Z)
              & setIn(Z,alive)
              & setIn(Pid20,alive)
              & host(Pid30) = host(Z)
              & host(Pid0) = host(Pid20) )
           => ~ ( elem(m_Down(Pid0),queue(host(Z)))
                & elem(m_Down(Pid30),queue(host(Pid20))) ) )
        & ! [Z,Pid30,Pid20,Pid0] :
            ( ( host(Pid20) != host(Z)
              & setIn(Z,alive)
              & setIn(Pid20,alive)
              & host(Pid30) = host(Z)
              & host(Pid0) = host(Pid20) )
           => ~ ( elem(m_Down(Pid0),queue(host(Z)))
                & setIn(host(Pid30),index(down,host(Pid20))) ) )
        & ! [Z,Pid20,Pid0] :
            ( ( host(Pid0) != host(Pid20)
              & setIn(Pid0,alive)
              & elem(m_Down(Z),queue(host(Pid0)))
              & host(Pid20) = host(Z)
              & index(status,host(Pid0)) = norm
              & index(ldr,host(Pid0)) = host(Pid20) )
           => ~ ( setIn(Pid20,alive)
                & index(status,host(Pid20)) = norm
                & index(ldr,host(Pid20)) = host(Pid20) ) )
        & ! [Z,Pid20,Pid0] :
            ( ( host(Pid0) != host(Pid20)
              & setIn(Pid0,alive)
              & elem(m_Down(Z),queue(host(Pid0)))
              & host(Pid20) = host(Z)
              & index(status,host(Pid0)) = wait
              & host(index(elid,host(Pid0))) = host(Pid20) )
           => ~ ( setIn(Pid20,alive)
                & index(status,host(Pid20)) = norm
                & index(ldr,host(Pid20)) = host(Pid20) ) )
        & ! [Z,Pid30,Pid20,Pid0] :
            ( ( ! [V0] :
                  ( ( ~ leq(host(Pid0),V0)
                    & leq(s(zero),V0) )
                 => ( setIn(V0,index(down,host(Pid0)))
                    | V0 = host(Pid20) ) )
              & setIn(Z,alive)
              & leq(host(Z),host(Pid0))
              & elem(m_Down(Pid20),queue(host(Pid0)))
              & host(Pid30) = host(Pid0)
              & index(status,host(Z)) = elec_2
              & index(status,host(Pid0)) = elec_1 )
           => ~ elem(m_Ack(Z,Pid30),queue(host(Z))) )
        & ! [Z,Pid30,Pid20,Pid0] :
            ( ( ! [V0] :
                  ( ( ~ leq(host(Pid0),V0)
                    & leq(s(zero),V0) )
                 => ( setIn(V0,index(down,host(Pid0)))
                    | V0 = host(Pid20) ) )
              & setIn(Pid0,alive)
              & leq(nbr_proc,s(host(Pid0)))
              & elem(m_Down(Pid20),queue(host(Pid0)))
              & elem(m_Down(Pid30),queue(host(Pid0)))
              & host(Pid30) = s(host(Pid0))
              & index(status,host(Pid0)) = elec_1 )
           => ~ ( setIn(Z,alive)
                & index(ldr,host(Z)) = host(Z)
                & index(status,host(Z)) = norm ) )
        & queue(host(X)) = cons(m_Down(Y),V) )
     => ( setIn(X,alive)
       => ( leq(host(X),host(Y))
         => ( ( index(status,host(X)) = elec_2
              & host(Y) = index(pendack,host(X)) )
           => ( leq(nbr_proc,index(pendack,host(X)))
             => ! [Z] :
                  ( setIn(host(Z),index(acks,host(X)))
                 => ! [V0] :
                      ( host(X) = host(V0)
                     => ! [W0,X0,Y0] :
                          ( host(Z) != host(Y0)
                         => ( host(X) != host(Y0)
                           => ( ( ! [V1] :
                                    ( ( ~ leq(host(Y0),V1)
                                      & leq(s(zero),V1) )
                                   => ( setIn(V1,index(down,host(Y0)))
                                      | V1 = host(X0) ) )
                                & setIn(Y0,alive)
                                & leq(nbr_proc,s(host(Y0)))
                                & elem(m_Down(W0),queue(host(Y0)))
                                & elem(m_Down(X0),queue(host(Y0)))
                                & host(W0) = s(host(Y0))
                                & index(status,host(Y0)) = elec_1 )
                             => ~ ( setIn(V0,alive)
                                  & host(X) = host(V0) ) ) ) ) ) ) ) ) ) ) ) )).

%------------------------------------------------------------------------------