CODEWITHSUNDEEP
multithreadingcompare-and-swapconsensus
Whiteclaws
Whiteclaws

Reputation: 942

Why does the consensus number matter in multithreading?

So the consensus number for a fetch-and-add operation is 2

I'm having a hard time grasping what that means and how it affects multithread programming? I would love some practical examples on how that would affect compared to a compareandswap for example ... Thank you very much.

Upvotes: 1

Views: 579

Answers (1)

jubueche
jubueche

Reputation: 793

Fetch-and-add gives you the ability to read and modify and location in memory atomically. Consensus means that protocol (fetch-and-add in this case) can give consensus for n different threads.

What does that mean?

Our goal is to use a protocol, where e.g. one thread determines a value and that value gets adopted by all other threads. You can google some of those protocols. In multithreading, it is important that we can modify memory atomically and that threads sometimes decide on one value.

It is important to note that consensus protocols are wait-free, that means that all threads make progress even when one dies (for some reason). Therefore it is important, when using multithreading, to be aware of an objects consensus number. A consensus number of e.g. an atomic register (1) tells us that we will never be able to implement an object using only atomic registers that can give consensus for 2 threads. That's why we use constructs such as fetch-and-add in multithreading.

Example Scheduling in an OS is usually done with FIFO queues. FIFO queues have consensus two so it is safe to use them for multithreading.

Upvotes: 1

Related Questions