Modeling Streamlet (Take Two)

This post is a sequel to my final 2 posts on Streamlet. The outset i explained the protocol. The 2nd i presented a outset draft modeling of the protocol.

In this post, I acquaint 2 improvements to the outset draft modeling.  In the first, I volition brand the epochs monotonic at the procedure level. In the 2nd one, I laissez passer on each node its ain inbox, instead of using a shared whiteboard message set. Again, I volition innovate the model dev-log style, using the notes I took spell developing it.

Adding locally monotonic epochs

Why don't I simply sequentially increase e inwards the procedure master copy loop. Instead of using while true, amongst e \in E, the procedure volition become through the epochs inwards increasing order. This all the same doesn't constrain the processes to become inwards lock-step through the epochs. Each procedure tin become through epochs inwards its ain measurement independent of the others. The exclusively requirement is if a procedure participated at an epoch (either equally a proposer or voter), it volition non participate at a lower epoch number. This is locally enforcable at each procedure fifty-fifty inwards a completely asynchronous environment.

So hither is the model, the alter beingness exclusively inwards procedure method at the end.

Making the epochs monotonic per procedure did wonders on the  model checking time. Now model checking is a blast. In the outset model, checking chains longer than iv took to a greater extent than than 5 minutes, inwards this model, checking chains of length 10 are simply about instant. 

Adding per procedure mailboxes

Now that I accept a rattling fast model, I tin add together per procedure message boxes to this model to cheque if in that place was whatever hidden concurrency work missed inwards the shared whiteboard message set. 

In social club to laissez passer on each node its ain inbox, I volition brand the Msgs gear upward an array of sets. 

variable Msgs=[n \in Nodes |->

{[chain|-> <<0>>, epoch|->0, sender|->0],

[chain|-> <<0>>, epoch|->0, sender|->1],

[chain|-> <<0>>, epoch|->0, sender|->2]}];

Then I volition drib the vote in addition to suggest message to the inbox of each procedure separately. This requires doing a spell loop iteration. I can't create these inwards the macros, in addition to thence I volition simply inline the macros inwards the procedure code. Here is the resulting model.

Consistency == \A i,j \in Nodes: ThreeCons(nChain[i]) /\ ThreeCons(nChain[j]) /\ Len(nChain[i])=< Len(nChain[j])                                  

=> \A k \in 1..Len(nChain[i]): 

            nChain[i][k]=nChain[j][Len(nChain[j])-Len(nChain[i])+k]

OK, Consistency all the same works. Recall that my consistency status is genuinely stronger than what is inwards the theorem because I am taking the final block also into account. Even amongst that consistency all the same checks out. This fourth dimension I accept per procedure inboxes, rather than atomic/unequivocal shared message gear upward communication. 

I intend the argue this all the same checks is because of combination of 2 things. The outset is the monotonic epoch status I added. The 2nd is that fifty-fifty though nosotros accept per procedure inboxes, the messages are delivered straight off to all the processes earlier the sender moves to the side yesteryear side epoch. I intend this volition involve making the inboxes a queue where messages are appended yesteryear the sender in addition to separately the receiver volition necessitate to asynchronously take the caput of the queue. Still a message puddle tin live used for the received messages, in addition to thence the residue of the model tin live salvaged. It seems similar to a greater extent than function in addition to I volition halt here.

Share this post