Show simple item record

dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorPapatriantafilou, Marinaen
dc.contributor.authorTsigas, Philippasen
dc.creatorMavronicolas, Mariosen
dc.creatorPapatriantafilou, Marinaen
dc.creatorTsigas, Philippasen
dc.description.abstractCounting networks form a new class of distributed, low-contention data structures, made up of interconnected balancers and 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. In this work we further pursue the systematic study of the impact of timing on linearizability for counting networks, along a research line 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. We also consider lower and upper bounds on the delays incurred by wires connecting the balancers. We present necessary and sufficient conditions for linearizability in the form of precise inequalities that involve timing parameters and identify structural parameters of the counting network, which may be of more general interest. Our results significantly extend and strengthen previous impossibility and possibility results on linearizability in counting networks.en
dc.sourceProceedings of the International Parallel Processing Symposium, IPPSen
dc.sourceProceedings of the 1997 11th International Parallel Processing Symposium, IPPS 97en
dc.subjectComputer softwareen
dc.subjectReal time systemsen
dc.subjectData structuresen
dc.subjectCounting networksen
dc.subjectCounting circuitsen
dc.titleImpact of timing on linearizability in counting networksen
dc.description.endingpage688 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.type.uhtypeConference Objecten
dc.description.notes<p>Conference code: 46339en
dc.description.notesCited By :9</p>en
dc.contributor.orcidPapatriantafilou, Marina [0000-0001-9094-8871]
dc.contributor.orcidTsigas, Philippas [0000-0001-9635-9154]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record