MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


The impact of timing on linearizability in counting networks

Mavronicolas, Marios and Papatriantafilou, Marina and Tsigas, Philippas

May 1996, 19 pages.

Status: available - back from printing

{\em Counting networks} form a new class of distributed, low-contention data structures, made up of {\em balancers} and {\em wires,} which are suitable for solving a variety of multiprocessor synchronization problems that can be expressed as counting problems. A {\em linearizable} counting network guarantees that the order of the values it returns respects the real-time order they were requested. Linearizability significantly raises the capabilities of the network, but at a possible price in network size or synchronization support. In this work, we further pursue the systematic study of the impact of {\em timing} assumptions on linearizability for counting networks, along the line of research recently initiated by Lynch~{\em et~al.} in [18]. We consider two basic {\em timing} models, the {instantaneous balancer} model, in which the transition of a token from an input to an output port of a balancer is modeled as an instantaneous event, and the {\em periodic balancer} model, where balancers send out tokens at a fixed rate. In both models, we assume lower and upper bounds on the delays incurred by wires connecting the balancers. We present necessary and sufficient conditions for linearizability in these models, in the form of precise inequalities that involve not only parameters of the timing models, but also certain structural parameters of the counting network, which may be of more general interest. Our results extend and strengthen previous impossibility and possibility results on linearizability in counting networks.

  • MPI-I-96-1-011.psMPI-I-96-1-011.pdf
  • Attachement: (194 KBytes); MPI-I-96-1-011.pdf (239 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Mavronicolas, Marios and Papatriantafilou, Marina and Tsigas, Philippas},
  TITLE = {The impact of timing on linearizability in counting networks},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-96-1-011},
  MONTH = {May},
  YEAR = {1996},
  ISSN = {0946-011X},