page 1  (19 pages)
2to next section

The Impact of Timing on Linearizability in Counting Networks?

Marios Mavronicolas y

Department of Computer Science
University of Cyprus
Nicosia, CY-1678
Cyprus
mavronic@turing.cs.ucy.ac.cy

Marina Papatriantafilou
Max-Planck-Institut f?ur Informatik
Im Stadtwald
D-66123 Saarbr?ucken, Germany
& CS Dept., Patras University, Greece
ptrianta@mpi-sb.mpg.de

Philippas Tsigas
Max-Planck-Institut f?ur Informatik
Im Stadtwald
D-66123 Saarbr?ucken, Germany
tsigas@mpi-sb.mpg.de

Abstract

Counting networks form a new class of distributed, low-contention data structures, made up of balancers and wires, which are suitable for solving a variety of multiprocessor synchronization problems that can be expressed as counting problems. A 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 [13, 18]. In this work, we further pursue the systematic study of the impact of timing assumptions on linearizability for counting networks, along the line of research recently initiated by Lynch et al. in [18]. We consider two basic 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 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 [13, 18].

?This work will also appear for publication elsewhere. Contact author: Philippas Tsigas
yPartially supported by funds for the promotion of research at University of Cyprus (research project Parallel, Concurrent and Distributed Computations"). Part of the work of this author was performed while visiting Max-Planck Institut f?ur Informatik, Saarbr?ucken, Germany.