# sequential consistency is not composable

I am studying for my exam in Distributed Systems course. And i have one question that i do not really understand. This is the question:

Is sequential consistency compositional? if yes explain why, if no give an example.


Now this is the only two slides that we have that explains why it is not composable.

And i am having trouble understanding why just from that example. I tried searching on the web for a better explanation but i could not find it. If you have a good example that you can describe and explain or if you have a good link or both please do provide it.

• – abc
Aug 13 '17 at 14:30
• @newbie Thank you so much for that post i clearly understand what it means now. Although it would be easier for me to understand it from the slides perspective to. I cant seem to put what i learned there into the example they show on the slides? Aug 15 '17 at 12:46

Composable means we can check for each object separately and exactly if the property applies to all of them separately then it applies to the whole of them at once.

To show that sequential consistency is not composable we can use an example where the ordering implied by the projections on one object contradicts the ordering implied by the projection on an other object.

Consider a history

A p.enq(x)
B q.enq(y)
A p:void
A q.enq(x)
B q:void
B p.enq(y)
A q:void
A p.deq()
B p:void
B q.deq()
A p:y
B q:x


when simply written down as code. Or visualized:

A: ---*1: p.enq(x)*---*3: q.enq(x)*---*5: p.deq()=y*---
B: ------*2: q.enq(y)*---*4: p.enq(y)*---*6: q.deq()=x*


where the operations start and end at the * and are arbitrarily numbered. Note that this looks like time axes, but that's not how it's necessarily executed. Now when you look at the object p, there must be an order 4-1-5 and for q it's 3-2-6. If the history is sequentially consistent, we also need order 1-3-5 and 2-4-6. But this is not possible, all possible interleavings of 4-1-5 and 3-2-6 contradict either of 1-3-5 or 2-4-6.

(example taken from private slides of a lecture I attended)