Scribd
Upload
336 views

Java Concurrent Programming Consensus

This document discusses consensus algorithms and numbers. It introduces concepts like consensus, consensus protocols, consensus numbers, queue consensus, atomic registers, approximate agreement, trinary registers, and team consensus. Examples and implementations are provided for several consensus algorithms.

Uploaded by

InVaSiOn101
Copyright
© Attribution Non-Commercial (BY-NC)
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
336 views

Java Concurrent Programming Consensus

This document discusses consensus algorithms and numbers. It introduces concepts like consensus, consensus protocols, consensus numbers, queue consensus, atomic registers, approximate agreement, trinary registers, and team consensus. Examples and implementations are provided for several consensus algorithms.

Uploaded by

InVaSiOn101
Copyright
© Attribution Non-Commercial (BY-NC)
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 21

Multicore Programming

Consensus Tutorial 6 CS 0368-3469 Spring 2010

Summary
Consensus Queue<> Atomic( n, n(n+1)/2) Approximate agreement Trinary register Team consensus
2

Consensus
Consistent: all threads decide the same value Valid: the common decision value is some thread's input

Generic Consensus Protocol


abstract class ConsensusProtocol implements Consensus { protected Object[] proposed = new Object[N]; private void propose(Object value) { proposed[ThreadID.get()] = value; } abstract public Object decide(object value); }}
(4)

4 (4)

Consensus Numbers
An object X has consensus number n
If it can be used to solve n-thread consensus
Take any number of instances of X together with atomic read/write registers and implement n-thread consensus

But not (n+1)-thread consensus

Queue<>
Suppose we augment the FIFO Queue<> class with a peek() method that returns but does not remove the first element in the queue. Show that the augmented queue has infinite consensus number.
6

Queue<> implementation
public class QueueConsensus extends ConsensusProtocol { private Queue queue; public decide(object value) { propose(value); this.queue.enq(threadID); return proposed[this.queue.peek()]; }
This is correct because if X is the first index to be enqueued, later enq() calls will not change X's position, and X stored its value in proposed[] before calling enq().
7

Atomic (n,n(n+1)/2)
Atomic (n,n(n+1)/2)-register assignment for n>1 has consensus number at least n.

Reminder: Atomic (2,3)


A
Writes to 0 and 1

Writes to 1 and 2
9

Atomic (n,n(n+1)/2)
n fields r0rn-1 n(n-1)/2 fields rij , where i > j. Each thread i atomically assigns its input value to n fields (with its index).
10

Atomic (n,n(n+1)/2)
Read rij . If the value is null, then neither assignment has occurred. Otherwise, read ri and rj . If ri value is null, then j precedes i, and similarly for rj . If neither ri nor rj is null, reread rij . If its value is equal to the value read from ri, then j precedes i, else vice-versa.
11

b<d<<c,a
12

b<a<d<<c
13

Approximate agreement
The two-thread approximate agreement class for a given : Call decide(xi)=yi (xi is a real number). yi in [min(xa, xb), max(xa, xb)] |ya - yb| < for > 0 What is the consensus number?
14

Approximate agreement solution


Can be implemented using atomic registers consensus == 1 yi xi If yj= return yi while(|yi-yj|>)

yi (yi+yj)/2 //average
15

Trinary register
Holds values [,0,1], provides compareAndSet() and get(). Solve n-consensus for K-bits values:
n trinary registers k trinary registers

16

Trinary register solution


Solution n trinaty registers
yi.cas(,1) For each j<>i

return smallest xj such that yj=1


17

yj.cas(,0)

Trinary register solution


Solution k trinaty registers Idea: try to set your bit or help.
1. Try to set the all k bits
2. If fails help to help another thread. Look in the announce array for a matching value. Replace yours with the other, goto 1. 3. return current value.
18

Team consensus
A Team consensus object provides the same propose() and decide() methods as consensus. A team consensus object solves consensus as long as no more than two distinct values are ever proposed. (If more than two are proposed, the results are undefined.) Show how to solve wait-free n-thread consensus, with up to n distinct input values, from a supply of team consensus objects.
19

Team consensus Solution


4 threads 2 threads

4
7 5
5 6

4 4
3 4

1
1 2

7
7 8
20

This work is licensed under a Creative Commons AttributionShareAlike 2.5 License.


You are free: to Share to copy, distribute and transmit the work to Remix to adapt the work Under the following conditions: Attribution.YoumustattributetheworktoTheArtof MultiprocessorProgramming(butnotinanywaythatsuggeststhat the authors endorse you or your use of the work). Share Alike. If you alter, transform, or build upon this work, you may distribute the resulting work only under the same, similar or a compatible license. For any reuse or distribution, you must make clear to others the license terms of this work. The best way to do this is with a link to http://creativecommons.org/licenses/by-sa/3.0/. Any of the above conditions can be waived if you get permission from the copyright holder. Nothing in this license impairs or restricts the author's moral rights.

Art of Multiprocessor Programming

21

You might also like