Data structures for distributed counting

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


The main tool to obtain a tight deterministic time hierarchy for Turing machines is a new data structure for fast distributed counting. The data structure representes an integer in a redundant manner, and it is able to accept orders from many places to increase or decrease the integer value by 1. With the help of the new data structure, it is shown that the slightest increase in computation time allows k-tape Turing machines (for fixed k ≥ 2) to solve new problems.

Original languageEnglish (US)
Pages (from-to)231-243
Number of pages13
JournalJournal of Computer and System Sciences
Issue number2
StatePublished - Apr 1984

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Data structures for distributed counting'. Together they form a unique fingerprint.

Cite this