Noncommutative operation

As explained in Think Distributed Systems

An operation whose result can change when its operands or applications are reordered.

A noncommutative operation is one whose result can change when operations are applied in a different order. Order therefore becomes part of the result. section 2.2

Applying updates to acceptors

Starting from 0, applying (+2) and (×2) produces different results depending on order: (+2) then (×2) gives 4, while (×2) then (+2) gives 2. If two acceptors receive these requests in different orders, they can diverge. section 2.2

Concurrent broadcasts do not require a particular order if every acceptor uses the same one. They do require consistent ordering when operations are noncommutative; otherwise, the system can exhibit a race condition. section 2.2 section 2.2

Figure 2.11 Proposers and acceptors

Trace how proposers' requests reach acceptors and how differing application orders affect their states. section 2.2

How Think Distributed Systems covers it

How deep it goes

Defines order dependence and demonstrates it with arithmetic, without developing an implementation protocol.

Examples

Uses (+2) and (×2) requests sent by two proposers to two acceptors starting at zero.

What you can do after

Evaluate whether reordering concurrent operations can produce divergent states or a race condition.

How it connects

Connects noncommutative operations with commutative operations, race conditions, concurrency, and parallelism.

liveBookmanning.com

Read Think Distributed Systems on liveBook Get the book at manning.com

Related concepts

• commutative operationcontrasts with · A commutative binary operation produces the same result when its two operands are exchanged.

This explainer was generated by Manning's knowledge graph from the text of Think Distributed Systems. The section links point to the parts of the book it draws on.