Advancements in Counting Algorithms for Multiprocessing Systems
Presentation of key concepts and advancements in counting algorithms for multiprocessing systems, focusing on topics like max registers, counters, and monotone circuits. Discusses the importance of efficient counting in achieving consensus, crash failure requirements, and lower bounds for time complexity. Explores different approaches such as tree-based counters and the use of Max Registers as solutions to counter implementation challenges.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Max Registers, Counters, and Monotone Circuits James Aspnes, Yale University Hagit Attiya, Technion Keren Censor, Technion PODC 2009
Counting 2 Counting is critical for some programs in multiprocessing systems 0 1 2 Example: Algorithms for randomized consensus Required: Counters with sub-linear (in the number of processes n) step complexity per operation PODC 2009
Counter 3 increment ok +1 Counter Model: readCounter v System of n processes Asynchronous system: no timing assumptions Implement using shared Read/Write registers Crash failures: require wait-free implementations Can be implemented using snapshots in linear time (in n) PODC 2009
Related work 4 Lower bound of (n) for time complexity by Jayanti, Tan, and Toueg [PODC 1996] and similar lower bounds by Ellen, Hendler, and Shavit [FOCS 2005] Motivated work on approximate counting [Aspnes and C, SODA 2009] PODC 2009
Exact counting 5 Give up on sub-linear exact counting? Or inspect lower bound more carefully: Based on executions with many increments long operation But some applications use a small number of increments We show an implementation of a bounded counter where each operation takes sub-linear time PODC 2009
A tree-based counter 6 Increment: recursively increment from leaf to root p1 increments ReadCounter: return value at root pk reads si +1 update s1+...+s4 O(log n) steps to increment O(1) steps to read counter update s1+s2 s3+s4 sn-1+sn update s1 s2 s3 s4 sn PODC 2009
Seems nice, but 7 If each node is a multi-writer register, then even for 2 processes and 2 increments this does not work p1 increments p2 increments +1 +1 Counter is incorrect +1 +1 s1+s2 update 1 update 2 s1 s2 PODC 2009
Max register 8 Replace multi-writer registers with Max Registers WriteMax(v) Maximal value previously written ok Max Register ReadMax v In this case the tree-based counter works If max registers are linearizable then so is counter PODC 2009
A tree-based counter 9 Increment: recursively increment from leaf to root ReadCounter: return value at root si s1+...+s4 s1+s2 s3+s4 sn-1+sn s1 s2 s3 s4 sn PODC 2009
Max register recursive construction 10 MaxReg0: Max register that supports only the value 0 WriteMax is a no-op, and ReadMax returns 0 MaxReg0 MaxReg1 supports values in {0,1} Built from two MaxReg0 objects and one additional multi-writer register switch =1 0 1 WriteMax = ? switch ReadMax switch=0 : return 0 MaxReg0 MaxReg0 switch=1 : return 1 PODC 2009
Max register recursive construction 11 MaxRegksupports values in {0, ,2k-1} Built from two MaxRegk-1objects with values in {0, ,2k-1-1} and one additional multi-writer register switch =1 t t WriteMax < 2k-1 ? = ? switch t-2k-1 t ReadMax t t switch=0 : return t MaxRegk-1 MaxRegk-1 switch=1 : return t+2k-1 MaxRegk PODC 2009
MaxRegk unfolded 12 MaxRegk switch Complexity does not depend on n: WriteMax and ReadMax in O(k) steps switch switch switch MaxReg0 MaxReg0 MaxReg0 MaxReg0 MaxReg0 PODC 2009
A tree-based counter 13 Increment: recursively increment from leaf to root ReadCounter: return value at root si m-valued counter: ReadCounter: O(log m) steps Increment: O(log n log m)steps s1+...+s4 s1+s2 s3+s4 sn-1+sn s1 s2 s3 s4 sn PODC 2009
Analysis 14 Inductive linearizability proof No contradiction with lower bound of JTT because of bounded size of max register and counter Extension to unbounded max registers (and counters) with complexity according to value written or read Both WriteMax and ReadMax of value v take O(min(log v, n)) steps PODC 2009
Lower bound of min(log m, n-1) 15 Sm = {executions with WriteMax operations up to value m by p1 ,pn-1, followed by one ReadMax operation by pn} pn reads T(m,n) = worst case cost of ReadMax in Sm PODC 2009
Lower bound of min(log m, n-1) 16 No process takes steps after pn so pn does not write pn reads pn reads R Reads a fixed register R. Did anyone write to R? k = minimal such that there is a write to R in Sk No one in Sk-1 writes to R so T(m,n) T(k-1,n)+1 PODC 2009
Lower bound of min(log m, n-1) 17 In addition, consider a run in Sk that writes to R write to R by pi pn reads R write to R by pi Finish writes except by pi Non-concurrent writes in {k, ,m} R pn reads pnreturns maximal value from {k, ,m} T(m,n) T(m-k+1,n-1)+1 Solve recurrence: T(m,n) 1+ mink {max(T(k-1,n), T(m-k+1,n-1))} , we had T(m,n) T(k-1,n)+1 PODC 2009
Summary 18 Implementation of max registers with O(min(log v, n)) steps per operation writing or reading the value v Sub-linear implementation of counters Extension of counters to any monotone circuit with monotone consistency instead of linearizability PODC 2009
Summary 19 Lower bounds An alternative proof for JTT Tight lower bound for max registers Same lower bound proof for counters Further research: close gap between upper and lower bounds on counters Randomized lower bound Further research: randomized algorithm? Take-home message: Lower bounds do not always have the final say PODC 2009
20 Thank you PODC 2009
