Simulation of Paxos

 --[[  Terribly written ugly lua code that simulates Paxos multi-proposer
-- The file paxos.data has the configuration
-- We try for multiple sizes of the set of Acceptors, incrementing by 2 each
-- time until the limit

Example data file with parameters

T= {
rounds = 50000,
proposers = 5,
acceptors = 7,
timeperround = 500,
retries=15,
maxacceptors=31
}

(c) Victor Yodaiken, Finite State Research LLC. 2016

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
---]]


dofile("paxos.data") -- read in parameters in a structure T

p = {} --- proposers
a = {} --- acceptors
stat = {} --- game stats

function count(x,n)  --- how many non-nil entries up to n are in array x
    local c =0
    for i=0, n do if x[i] ~= nil then c = c+1 end end
    return c;
end

function displayproposers(m,axes) --print out proposer key values
local v = nil
print(m,"-------------------")
for i=1,T.proposers do
    print(i,"id=", p[i].id, "phase=",
         p[i].phase, "v=",p[i].value, count(p[i].approved,axes),
        count(p[i].accepted,axes))
    if p[i].phase == 3 then
        if v == nil then v = p[i].value elseif v ~= p[i].value then
            print("failed")
        end
    end
end
end

function statinit(x)
    stat = {
    runs =0,
    failures =0 ,
    livelocks = 0,
    winners = 0,
    winning = 0,
        acceptors = x,
    retries = retries,
    totalvalue =0 }
end

function stats(axes)
    local winners=0
        local value = nil
    local fails = 0

    for i=1,T.proposers do
        if p[i].phase == 3 then
            winners = winners+1
            if value == nil then value = p[i].value
            elseif value ~= p[i].value then fails = 1
                    end
        end
    end
    stat.runs = stat.runs +1
    if winners == 0 then stat.livelocks = stat.livelocks +1
    else
        stat.winners = stat.winners + winners
        stat.winning = stat.winning +1
        stat.totalvalue = stat.totalvalue + value
    end
    if fails == 1 then
        stat.failures = stat.failures +1
        displayproposers("stat failure",axes)
    end
end

function displaystats()
    print(stat.acceptors, stat.livelocks/stat.runs, stat.winning,stat.totalvalue/stat.winning)
end






function setretry(n)
  p[n].retries = p[n].retries +1
  if p[n].retries > T.retries then
    local id = p[n].id
    initonep(n)
    p[n].id = id + T.proposers
  end
end

function pickvalue(n)
    local v
    if p[n].bestv ~= nil then v= p[n].bestv else v= p[n].id end
    return v
end

function newapproval(px,ax,numa)
    local t = a[ax].highestq
    local z = p[px].id
    if p[px].approved[ax] == nil and a[ax].highestq <= p[px].id then --ifq
        p[px].approved[ax]=1;
        a[ax].highestq = p[px].id
                if p[px].bestq < a[ax].bestq then p[px].bestq = a[ax].bestq p[px].bestv = a[ax].bestv end if count(p[px].approved, numa) > numa/2 then --ifcount
            p[px].phase =2
            p[px].value = pickvalue(px)
            p[px].retries =0 --approval starts fresh
        end --ifcount
    p[px].retries =0
    return true
    end --ifq
return false
end

function newaccept(px,ax,numa)
    if p[px].accepted[ax] == nil and a[ax].highestq <= p[px].id then --ifq
        p[px].accepted[ax]=1;
        if a[ax].bestq < p[px].id then a[ax].bestq = p[px].id a[ax].bestv = p[px].value end if count(p[px].accepted, numa) > numa/2 then
            p[px].phase =3
        end --count
        p[px].retries =0
        return true
    end --ifq
return false
end

function initp()
for i=1, T.proposers do initonep(i) end
end

function initonep(i)
    p[i] ={ id=i, retries=0, phase=1, approved= {}, accepted={},value=nil, bestv=nil, bestq=0}
end

function inita()
for i=1,T.maxacceptors do
    a[i] = { id = i, highestq = 0, bestv = nil, bestq= 0 } end
end

function nextproposer()
    local x= (math.floor((math.random()* T.proposers) +1 )% T.proposers )+1
return x
end

function nextacceptor(n)
    return (math.floor((math.random()* n) +1 )% n )+1
end

-- main
math.randomseed(os.time())

print("Proposers=",T.proposers, "Time per round = ",T.timeperround, "rounds=",T.rounds, "Retries=",T.retries)
for n= T.acceptors,  T.maxacceptors,2 do --foracceptors
    statinit(n)
    for round = 1, T.rounds do --forround
        initp(); inita();
        for t=1, T.timeperround do --fortime
            local px =  nextproposer()
            local ax = nextacceptor(n)
            if p[px].phase == 1 then --ifphase
                if newapproval(px,ax,n) == false then setretry(px) end
            elseif p[px].phase == 2 then --ifphase2
                if newaccept(px,ax,n) == false then setretry(px) end
            end --ifphase2 and phase1
        end --fortime
        stats(n)
    end --forround
displaystats()
end
print("AxtLlock%tWinningtAvg value")