Approximate shared-memory counting despite a strong adversary

ABSTRACT

A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented up to n times. For any fixed ε, the counter achieves a relative error of δ with high probability, at the cost of O(((1/δ) log n)^O(1/ε)) register operations per increment and O(n^4/5+ε((1/δ) log n)^O(1/ε)) register operations per read. The counter combines randomized sampling for estimating large values with an expander for estimating small values. This is the first sublinear solution to this problem that works despite a strong adversary scheduler that can observe internal states of processes.

An application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from O(n log n) to an optimal O(n), resolving one of the last remaining open problems concerning consensus in this model.

REFERENCES

• 1: Karl Abrahamson, On achieving consensus using a shared memory, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.291-302, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62594]
• 2: Noga Alon and Joel H. Spencer. The Probabilistic Method. John Wiley & Sons, 1992.
• 3: James Aspnes, Time- and space-efficient randomized consensus, Journal of Algorithms, v.14 n.3, p.414-431, May 1993 [doi>10.1006/jagm.1993.1022]
• 4: James Aspnes, Lower bounds for distributed coin-flipping and randomized consensus, Journal of the ACM (JACM), v.45 n.3, p.415-450, May 1998 [doi>10.1145/278298.278304]
• 5: James Aspnes , Hagit Attiya , Keren Censor, Randomized consensus in expected O(n log n) individual work, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400794]
• 6: James Aspnes , M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms, v.11 n.3, p.441-461, Sep. 1990 [doi>10.1016/0196-6774(90)90021-6]
• 7: James Aspnes , Orli Waarts, Randomized Consensus in Expected O(n log^ 2 n) Operations Per Processor, SIAM Journal on Computing, v.25 n.5, p.1024-1044, Oct. 1996 [doi>10.1137/S0097539792240881]
• 8: Hagit Attiya , Keren Censor, Tight bounds for asynchronous randomized consensus, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250814]
• 9: Hagit Attiya , Rachid Guerraoui , Danny Hendler , Petr Kouznetsov, Synchronizing without locks is inherently expensive, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146427]
• 10: Gabriel Bracha , Ophir Rachman, Randomized Consensus in Expected O(n²log n) Operations, Proceedings of the 5th International Workshop on Distributed Algorithms, p.143-150, October 07-09, 1991
• 11: Faith Ellen Fich , Danny Hendler , Nir Shavit, Linear Lower Bounds on Real-World Implementations of Concurrent Objects, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.165-173, October 23-25, 2005 [doi>10.1109/SFCS.2005.47]
• 12: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 13: Philippe Flajolet, Approximate counting: a detailed analysis, BIT, v.25 n.1, p.113-134, 1985 [doi>10.1007/BF01934993]
• 14: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 15: G. R. Grimmet and D. R. Stirzaker. Probability and Random Processes. Oxford Science Publications, 2nd edition, 1992.
• 16: Venkatesan Guruswami , Christopher Umans , Salil Vadhan, Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.96-108, June 13-March 16, 2007 [doi>10.1109/CCC.2007.38]
• 17: P. Hall and C. C. Heyde. Martingale Limit Theory and Its Application. Academic Press, 1980.
• 18: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 19: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 20: Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin (new series) of the American Mathematical Society, 43(4):439--561, October 2006.
• 21: Michael C. Loui and Hosame H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, pages 163--183, 1987.
• 22: Michael Mitzenmacher , Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, New York, NY, 2005
• 23: Robert Morris, Counting large numbers of events in small registers, Communications of the ACM, v.21 n.10, p.840-842, Oct. 1978 [doi>10.1145/359619.359627]
• 24: Michael Saks , Nir Shavit , Heather Woll, Optimal time randomized consensus—making resilient algorithms fast in practice, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.351-362, January 28-30, 1991, San Francisco, California, United States
• 25: Nicholas C. Wormald. The differential equation method for random graph processes and greedy algorithms. In M. Karonski and H. J. Proemel, editors, Lectures on Approximation and Randomized Algorithms, pages 73--155. PWN, 1999.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms