The Impact of Timing on Linearizability inCounting Networks.pdf

The Impact of Timing on Linearizabili ty in Counting Networks Marios Mavronicolas  Marina Papatriantalou y Philippas Tsigasz Abstract Counting networks form a new class of distributed, low-contention data structures, made up of interconnected balancers and are suitable for solving a variety of multipro cessor synchronization problems that can b e expressed as counting problems. A linearizable counting network guarantees that the order of the values it returns resp ects the real- time order they were requested. Linearizabili ty signicantly raises the capabilities of the network, but at a p ossible price in network size or synchronization supp ort. In this work we further pursue the systematic study of the impact of timing on linearizabili ty for counting networks, along the line of research recently initiated by Lynch et al. in [18]. We consider two basic timing mo dels, the instantaneous balancer mo del, in which the transition of a token from an input to an output p ort of a balancer is mo deled as an instantaneous event, and the p erio dic balancer mo del, where balancers send out tokens at a xed rate. We also consider lower and upp er b ounds on the delays incurred by wires connecting the balancers. We present necessary and sucient conditions for linearizabili ty in the form of precise inequalities that not only involve timing parameters, but also identify structural parameters of the counting network, which may b e of more general interest. Our results extend and strengthen previous imp ossibility and p ossibility resul