Safe semantics
Safe Semantic is a form of semantics (computer science) which describes the guarantees and data register provided or shared by several processors in parallel machines or in a network of computers working together.
This work first appeared in a [DEC Systems Research Center]] (SRC) Research Report in December 1985.[1] Later on, it was formally defined in Leslie Lamport's "On Interprocess Communication", which was published in Distributed Computing in 1986. [2]
Safe semantics are defined for a variable with a single writer but multiple readers(SWMR).An SWMR register is safe if the read operation satisfies the two following properties:
1)A read operation does not concurrent with any write operation returns the latest value written by the write operation.
2) In case of concurrency between the read and write operation,the read operation returns any value within the register's allowed range of values(for example 0,1,2,...)
We can also state that if there is concurrency between the read and the write operation,the read operation can return a value which has never been written by any write operation.The return value only belongs to the register domain.For example,let's suppose that RV is the register domain and it contains some numbers such as 0,1,2,3,4 (RV={0,1,2,3,4}).Assume that when RV=0,one read operation is concurrent with write(3).The read operation can return 0,1,2,3,or even 4,but it cannot return 5 since this value is not included in the RV.On the other hand,the read operation can return 4,which has never been written.
We can see a binary safe register as modeling of a bit flickering.Whatever the previous value of the register is,the register's value could flicker until the write operation finishes.Therefore,the read operation which overlaps with a write operation could return 0 r 1.
There has been many implementation of safe register in a distributed systems.Generaly ,[3] shows that there is no way to implement a regular semantics in a synchronous system under continuous churn.On the other hand,it has been demonstrated in [4] that the safe register was implemented under continuous churn in a non-synchronous system.Leaving and joining of servers from/into a distributed system can be characterized under the name churn/Dynamicity.Modeling and Implementing a type of storage memory ( Safe Register) under non-quiescent churn in [5] required some system models such as client and server systems.Client systems contains finite arbitrary number of processes and they are responsible for reading and writing into the server system.On the other hand,the server system just make sure that read and write operations happen properly.Safe register implementation was as follow:
-Safe register was maintained by the set of active servers.
-Clients do not maintain any register information (trigger operation, and interact with servers)
-Eventually synchronous system
-Quorums(set of server or client systems)
-Size of the Read() and Write() operation executed on quorums = n – f – J (n is the number of servers, J is the number of servers that leave and join,and f is the number of byzantine failures.
Before implementing the safe register,in [6] some algorithms were introduced such as join,read, and write operation.
Join Operation():A server(si) which wants to get entered into a server system will broadcast an inquiry message to other servers to inform other servers of its arrival into the distributed system,si also wants to find a current value of the register.Once other server received this inquiry they will send a reply message to si.After si receives enough reply from other servers,it will collect all the replies and saves them into a reply set.Si waits until it gets enough reply(n-f-j) from other servers then it will pick up the most frequent value among other values.Si will also do the following :
-Updates its local copy of the register
-It becomes active
-Sends reply to the processes in the set reply
-If si its active it will sends reply message to the other servers immediately.
-Otherwise,if Si is not active ,it will store the inquiries somewhere to reply them by the time it become active.
-When si gets reply from other servers it will eventually add the new reply to the reply set and throw the old value from the reply set.
-If the value of the respond server is bigger that si value, then si will update its information with the new value.
Read operation(): the read operation algorithm is a basic version of the join operation.The only difference between these two algorithms is the broadcast mechanism used by the read operation.A client (cw)will broadcast a message to the system and once a server receives the inquiry,it will send a reply message to the client.Once the client receives enough replies (n-f-j) it will stop sending an inquiry.
Write operation:Client(cw) sends an inquiry into the system in different rounds and it will wait until it receives two acknowledgment.(sn =sequence number)
The reason for receiving two acknowledgment is because there could be a danger in a system. When a process Sends an acks, it may die after one millisecond.Therefore,there will be no confirmation received by the client.
In [7] the validity of the safe register(If a read() not concurrent with any write(), returns the last value written before its invocation) was proved based on the quorum system.Assume that there are two quorum system(Qw,Qr).Qw indicates the Servers that know about the latest value,and Qr indicates Values of Read’s responses.Based on the assumption in [8] the size of each quorum is equal to n-f-j.To prove the safe register's validity we need to prove the following equation: (Qw∩Qr)\B >(Qr∩B) :Note that B is the number of Byzantine failures. Proof : Red region indicates (Qw∩Qr)\B and the blue region indicates Qr∩B.Based on the assumption,we know that the size of each quorum is n-f-j,so the red region will have n-3f-2j active servers.Therefore,n-3f-2J > f --> n > 4f+2J --> n is strictly greater than f.
Notes
- ^ Lamport, Leslie. On Interprocess Communication. Palo Alto, CA: DEC Systems Research Center, 1985. Web. 21 Oct. 2013. SRC Research Report.
- ^ Lamport, Leslie. “On Interprocess Communication.” Distributed Computing 1.2 (1986): 77–85. link.springer.com. Web. 21 Oct. 2013.
- ^ Bonomi , Rayna. "Implementing a Regular Register in an Eventually Synchronous Distributed System prone to Continuous Churn".
{{cite journal}}: Cite journal requires|journal=(help) - ^ SoltaniNezhad,Bonomi,Baldoni. "A protocol for implementing byzantine storage in churn-prone distributed systems".
{{cite journal}}: Cite journal requires|journal=(help)CS1 maint: multiple names: authors list (link) - ^ SoltaniNezhad,Bonomi,Baldoni. "A protocol for implementing byzantine storage in churn-prone distributed systems".
{{cite journal}}: Cite journal requires|journal=(help)CS1 maint: multiple names: authors list (link) - ^ SoltaniNezhad,Bonomi,Baldoni. "A protocol for implementing byzantine storage in churn-prone distributed systems".
{{cite journal}}: Cite journal requires|journal=(help)CS1 maint: multiple names: authors list (link) - ^ SoltaniNezhad,Bonomi,Baldoni. "A protocol for implementing byzantine storage in churn-prone distributed systems".
{{cite journal}}: Cite journal requires|journal=(help)CS1 maint: multiple names: authors list (link) - ^ SoltaniNezhad,Bonomi,Baldoni. "A protocol for implementing byzantine storage in churn-prone distributed systems".
{{cite journal}}: Cite journal requires|journal=(help)CS1 maint: multiple names: authors list (link)