Strength of counting networks

Costas Busch; Marios Mavronicolas

doi:10.1145/248052.248115

Strength of counting networks

Costas Busch, Marios Mavronicolas

Research output: Contribution to conference › Paper › peer-review

3 Scopus citations

Abstract

This paper shows that any counting network, made up of balancers whose fan-in and fan-out vary arbitrarily, is, indeed, strong enough to simultaneously support both Fetch&Increment and Fetch&Decrement operations, once each of its balancers is substituted by an elimination balancer. Its proof is purely combinatorial, carried out within the elegant combinatorial framework put forth for the study of balancing networks. Through equivalence theorems, impossibility results, lower bounds, verification algorithms and methodologies to prove correctness carry over to counting networks with enriched operation set.

Original language	English (US)
Pages	311
Number of pages	1
DOIs	https://doi.org/10.1145/248052.248115
State	Published - 1996
Externally published	Yes
Event	Proceedings of the 1996 15th Annual ACM Symposium on Principles of Distributed Computing - Philadelphia, PA, USA Duration: May 23 1996 → May 26 1996

Conference

Conference	Proceedings of the 1996 15th Annual ACM Symposium on Principles of Distributed Computing
City	Philadelphia, PA, USA
Period	5/23/96 → 5/26/96

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1145/248052.248115

Cite this

@conference{49800a2cd1d7424297286c6681ef4683,

title = "Strength of counting networks",

abstract = "This paper shows that any counting network, made up of balancers whose fan-in and fan-out vary arbitrarily, is, indeed, strong enough to simultaneously support both Fetch&Increment and Fetch&Decrement operations, once each of its balancers is substituted by an elimination balancer. Its proof is purely combinatorial, carried out within the elegant combinatorial framework put forth for the study of balancing networks. Through equivalence theorems, impossibility results, lower bounds, verification algorithms and methodologies to prove correctness carry over to counting networks with enriched operation set.",

author = "Costas Busch and Marios Mavronicolas",

year = "1996",

doi = "10.1145/248052.248115",

language = "English (US)",

pages = "311",

note = "Proceedings of the 1996 15th Annual ACM Symposium on Principles of Distributed Computing ; Conference date: 23-05-1996 Through 26-05-1996",

}

TY - CONF

T1 - Strength of counting networks

AU - Busch, Costas

AU - Mavronicolas, Marios

PY - 1996

Y1 - 1996

N2 - This paper shows that any counting network, made up of balancers whose fan-in and fan-out vary arbitrarily, is, indeed, strong enough to simultaneously support both Fetch&Increment and Fetch&Decrement operations, once each of its balancers is substituted by an elimination balancer. Its proof is purely combinatorial, carried out within the elegant combinatorial framework put forth for the study of balancing networks. Through equivalence theorems, impossibility results, lower bounds, verification algorithms and methodologies to prove correctness carry over to counting networks with enriched operation set.

AB - This paper shows that any counting network, made up of balancers whose fan-in and fan-out vary arbitrarily, is, indeed, strong enough to simultaneously support both Fetch&Increment and Fetch&Decrement operations, once each of its balancers is substituted by an elimination balancer. Its proof is purely combinatorial, carried out within the elegant combinatorial framework put forth for the study of balancing networks. Through equivalence theorems, impossibility results, lower bounds, verification algorithms and methodologies to prove correctness carry over to counting networks with enriched operation set.

UR - http://www.scopus.com/inward/record.url?scp=0029713955&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029713955&partnerID=8YFLogxK

U2 - 10.1145/248052.248115

DO - 10.1145/248052.248115

M3 - Paper

AN - SCOPUS:0029713955

SP - 311

T2 - Proceedings of the 1996 15th Annual ACM Symposium on Principles of Distributed Computing

Y2 - 23 May 1996 through 26 May 1996

ER -

Strength of counting networks

Abstract

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this