Data structures for distributed counting

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

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
Volume28
Issue number2
DOIs
StatePublished - Apr 1984

All Science Journal Classification (ASJC) codes

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

Fingerprint

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

Cite this