// ----------------------------------------------------------------- // abit.txt: the alternating bit protocol // Concrete Abstractions: Concurrent Systems // (c) 2020, Wolfgang Schreiner, RISC, JKU Linz, Austria // ----------------------------------------------------------------- // the number of messages recorded val N:ℕ; type Msg = ℕ[1]; type Bit = Bool; type Seq = Array[N,Msg]; type Index = ℕ[N]; // arbitrary default message val Default:Msg = 0; // the shared version of the protocol shared system AlternatingBit { // the messages sent and received (local to each process) var sent:Msg = Default; var rcvd:Msg = Default; // the protocol bits var sbit:Bit = ⊥; var sack:Bit = ⊥; var rbit:Bit = ⊥; // the history of the messages sent and received var smsgs:Seq = Array[N,Msg](Default); var snum:Index = 0; var rmsgs:Seq = Array[N,Msg](Default); var rnum:Index = 0; // safety property: the messages received are the messages sent invariant rnum ≤ snum ∧ ∀i:Index with i < rnum. rmsgs[i] = smsgs[i]; // safety property follows from these invariants invariant snum-1 ≤ rnum; invariant sack = sbit ⇒ rnum = snum; invariant rbit ≠ sbit ∧ rnum < N ⇒ rnum < snum ∧ sent = smsgs[snum-1]; // the violation of this invariant indicates progress // invariant rnum < N; // sender choses a message and sends it action sender(m:Msg) with sack = sbit; { sent ≔ m; sbit ≔ ¬sbit; if snum < N then { smsgs[snum] ≔ sent; snum ≔ snum+1; } } // receiver receives a message action receiver() with rbit ≠ sbit; { rcvd ≔ sent; rbit ≔ sbit; sack ≔ rbit; if rnum < N then { rmsgs[rnum] ≔ rcvd; rnum ≔ rnum+1; } } } // the capacity of the package queues val M:ℕ; type Package = Record[msg:Msg,bit:Bit]; type Queue = Record[len:ℕ[M],pack:Array[M,Package]]; // the result of sending into queue q a package with message m and bit b fun add(q:Queue,m:Msg,b:Bit): Queue requires q.len < M; = q with .len = q.len+1 with .pack = q.pack with [q.len] = ⟨msg:m,bit:b⟩; // the result of receiving a package from a queue fun head(q:Queue):Package = q.pack[0]; proc tail(q:Queue):Queue requires q.len > 0; ensures result.len = q.len-1; ensures ∀i:ℕ[M] with i < result.len. (result.pack[i] = q.pack[i+1]); { var q0:Queue ≔ q; q0.len ≔ q0.len-1; for var i:ℕ[M] ≔ 0; i < q0.len; i ≔ i+1 do invariant q0.len = q.len-1 ∧ 0 ≤ i ∧ i ≤ q0.len; invariant ∀k:ℕ[M] with k < i. (q0.pack[k] = q.pack[k+1]); invariant ∀k:ℕ[M] with i ≤ k ∧ k < M. (q0.pack[k] = q.pack[k]); decreases q0.len-i; { q0.pack[i] ≔ q0.pack[i+1]; } return q0; } // the network version of the protocol shared system AlternatingBitNetwork { // the messages sent and received (local to each process) var sent:Msg = Default; var rcvd:Msg = Default; // the protocol bits var sbit:Bit = ⊥; var sack:Bit = ⊥; var rbit:Bit = ⊥; // the communication channels var msgq:Queue = ⟨len:0,pack:Array[M,Package](⟨msg:Default,bit:⊥⟩)⟩; var ackq:Queue = ⟨len:0,pack:Array[M,Package](⟨msg:Default,bit:⊥⟩)⟩; // the history of the messages sent and received var smsgs:Seq = Array[N,Msg](Default); var snum:Index = 0; var rmsgs:Seq = Array[N,Msg](Default); var rnum:Index = 0; // safety property: the messages received are the messages sent invariant rnum ≤ snum ∧ ∀i:Index with i < rnum. rmsgs[i] = smsgs[i]; // invariants from the shared memory version invariant snum-1 ≤ rnum; invariant sack = sbit ⇒ rnum = snum; invariant rbit ≠ sbit ∧ rnum < N ⇒ rnum < snum ∧ sent = smsgs[snum-1]; // additional invariants invariant rnum < snum ⇒ rbit ≠ sbit; invariant ∀i:ℕ[M] with i < msgq.len. (msgq.pack[i].bit ≠ rbit ⇒ msgq.pack[i].msg = sent ∧ msgq.pack[i].bit = sbit); invariant ∀i:ℕ[M] with i+1 < msgq.len. (msgq.pack[i].bit ≠ rbit ⇒ msgq.pack[i+1].bit ≠ rbit); invariant ∀i:ℕ[M] with i+1 < ackq.len. (ackq.pack[i].bit ≠ sack ⇒ ackq.pack[i+1].bit ≠ sack); invariant sack = sbit ⇒ (∀i:ℕ[M] with i < msgq.len. (msgq.pack[i].bit = rbit)); invariant sack = rbit ⇒ (∀i:ℕ[M] with i < ackq.len. (ackq.pack[i].bit = rbit)); // the violation of this invariant indicates progress invariant rnum < N; // sender choses a message and sends it action sender(m:Msg) with sack = sbit ∧ msgq.len < M; { sent ≔ m; sbit ≔ ¬sbit; msgq ≔ add(msgq,sent,sbit); if snum < N then { smsgs[snum] ≔ sent; snum ≔ snum+1; } } // sender resends the last message sent (arbitrarily often) action resend() with sack ≠ sbit ∧ msgq.len < M; { msgq ≔ add(msgq,sent,sbit); } // sender receives an acknowledgement action receiveAck() with ackq.len > 0; { sack ≔ head(ackq).bit; ackq ≔ tail(ackq); } // receiver receives a message action receiver() with msgq.len > 0; { val p = head(msgq); msgq ≔ tail(msgq); if p.bit ≠ rbit then { rcvd = p.msg; rbit ≔ p.bit; if rnum < N then { rmsgs[rnum] ≔ rcvd; rnum ≔ rnum+1; } } } // receiver acknowledges a message (arbitrarily often) action sendAck() with ackq.len < M; { ackq ≔ add(ackq,Default,rbit); } // channels may lose messages and acknowledgemens action loseMsg() with msgq.len > 0; { msgq ≔ tail(msgq); } action loseAck() with ackq.len > 0; { ackq ≔ tail(ackq); } } // ---------------------------------------------------------------- // end of file // ----------------------------------------------------------------