[CS] Lamport's register

1. Safe Register: If a read does not overlap with a write, then the read returns the result of the latest completed write.
2. Regular Register: Safe + overlapping read. It returns either overlapping write or the latest completed write.
3. Atomic Register: Totally ordered.

어떤 register가 있고 여러 프로세스가 이 register에 read/write를 concurrent하게 할 수 있다고 하자. Concurrent의 개념은 한 프로세스가 이 register에 값을 read 또는 write하는 사이에 다른 프로세스도 역시 read 또는 write할 수 있다는 의미이다. 문제가 되는 것은 프로세스 A가 write를 하는 중간에 프로세스 B가 이 값을 읽으려고 하면 어떤 값이 read 될 것인가이다. Safe register는 일단, 이런 read와 write 사이 overlap 상황이 없을 때에 가장 최근에 write가 완료된 값을 리턴하는 것을 보장해주는 register이다. Regular register는 safe register가 보장해주는 것을 보장하는 것과 동시에 overlap상황이 있는 경우 최근에 완료된 write 혹은 현재 write하고 있는 값 둘 중에 하나를 리턴해준다는 것이다. Atomic register의 경우 어떤 totally ordered된 실행 순서가 존재하고 어떠한 read 요청에 대해서도 이 순서를 보장해주는 것이다. 

예를 들어, register x에 대해 5라는 값을 쓰는 것을 write(x, 5)라고 하자. write(x, 5)가 존재하고 이후에 write(x, 6)이 존재한다고 하자. write(x, 6)을 하는 중간에 A가 read(x)를 하고, 잠시 후 역시 write(x, 6)이 진행되는 중간에 B가 read(x)를 했다고 하자. 이 경우 Safe register는 어떠한 값을 리턴할 것인지에 대해 아무것도 보장하지 못한다. Regular register의 경우 완료된 값인 5 혹은 overlap되고 있는 값인 6 중에 하나를 리턴한다. Regular register의 경우 A는 6을, B는 5를 리턴 받는 경우가 발생할 수도 있다. 그러나, Atomic register의 경우 A가 6을 리턴한 경우 반드시 B도 6을 리턴하는 것을 보장한다. write(x, 6)이 완료되는 시점이 반드시 존재하고 write(x, 5)의 값이 리턴되는 시기와 write(x, 6)이 리턴되는 시기가 바뀌는 시점이 존재한다. 따라서 A, B는 각각 (5, 5), (5, 6), (6, 6)을 받을 수는 있지만 (6, 5)를 받을 수는 없다. 

Atomic Register

별로 중요한 것은 아닌데 심심해서 적어본다. (잘못 설명했을 수도...) 그나저나, 영어에서 If A, then B. 즉, propositional logic에서의 A->B는 참 받아들이기 어렵다. A가 참이면 B도 참인데, A가 거짓이면 B는 뭐든 상관없다라는 것. 나는 '상관없다'라는 것이 잘 와닿지 않는다. -_-;