Belated Analyses of Three Credit-Based Adaptive Polling Algorithms

We study the problem of credit-based adaptive polling in undirected arbitrary point-to-point asynchronous networks. Polling consists of two rounds, namely propagation (broadcast) and feedback (confirmation, response) rounds. By adaptive polling, a spanning tree of unknown topology is built dynamical...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2016-08, Vol.27 (5), p.579-594
Main Author: Tse, Savio S. H.
Format: Article
Language:English
Subjects:
Adaptive algorithms
Algorithms
Feedback
Graph theory
Lower bounds
Polling schemes
Propagation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c2669-53040bd14a77bc36faeeb3b7adb7b7847ed0c6501dc62c0739fd8e86a5ec096f3
container_end_page 594
container_issue 5
container_start_page 579
container_title International journal of foundations of computer science
container_volume 27
creator Tse, Savio S. H.
description We study the problem of credit-based adaptive polling in undirected arbitrary point-to-point asynchronous networks. Polling consists of two rounds, namely propagation (broadcast) and feedback (confirmation, response) rounds. By adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths back to the initiator — a specific node who initiates the polling algorithm. The freedom in the feedback round relies on the use of credits in the propagation round. We re-visit three existing algorithms and analyse their average case communication bit complexities incurred by the credits in the propagation round, and these analyses match with the numerical results. We also give an optimal lower bound on the worst case bit message complexity for the case when the number of nodes in the network is unknown.
doi_str_mv 10.1142/S0129054116500179
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1142_S0129054116500179</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2116260914</sourcerecordid><originalsourceid>FETCH-LOGICAL-c2669-53040bd14a77bc36faeeb3b7adb7b7847ed0c6501dc62c0739fd8e86a5ec096f3</originalsourceid><addsrcrecordid>eNplkE9LAzEQxYMoWGo_gLcFz6uTZDdpjm3xHwgK1vOSTSZtJG1qslX67d2l4qWXmcN7v-HNI-Sawi2lFbt7B8oU1BWlogagUp2RUT95Kbjk52Q0yOWgX5JJzr4FqgSvWS1GZD7HoDu0xWyrwyFjLqIrluuEWCwSWt-Vc50H2epd57-xeIsh-O2qmIVVTL5bb_IVuXA6ZJz87TH5eLhfLp7Kl9fH58XspTRMCFXWHCpoLa20lK3hwmnElrdS21a2clpJtGD6_NQawQxIrpyd4lToGg0o4fiY3Bzv7lL82mPums-4T33s3LD-cyZA0ap30aPLpJhzQtfskt_odGgoNENbzUlbPQNH5iemYLPxuO288-YfPUV-AVSVauo</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2116260914</pqid></control><display><type>article</type><title>Belated Analyses of Three Credit-Based Adaptive Polling Algorithms</title><source>World Scientific Journals</source><creator>Tse, Savio S. H.</creator><creatorcontrib>Tse, Savio S. H.</creatorcontrib><description>We study the problem of credit-based adaptive polling in undirected arbitrary point-to-point asynchronous networks. Polling consists of two rounds, namely propagation (broadcast) and feedback (confirmation, response) rounds. By adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths back to the initiator — a specific node who initiates the polling algorithm. The freedom in the feedback round relies on the use of credits in the propagation round. We re-visit three existing algorithms and analyse their average case communication bit complexities incurred by the credits in the propagation round, and these analyses match with the numerical results. We also give an optimal lower bound on the worst case bit message complexity for the case when the number of nodes in the network is unknown.</description><identifier>ISSN: 0129-0541</identifier><identifier>EISSN: 1793-6373</identifier><identifier>DOI: 10.1142/S0129054116500179</identifier><language>eng</language><publisher>Singapore: World Scientific Publishing Company</publisher><subject>Adaptive algorithms ; Algorithms ; Feedback ; Graph theory ; Lower bounds ; Polling schemes ; Propagation</subject><ispartof>International journal of foundations of computer science, 2016-08, Vol.27 (5), p.579-594</ispartof><rights>2016, World Scientific Publishing Company</rights><rights>2016. World Scientific Publishing Company</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c2669-53040bd14a77bc36faeeb3b7adb7b7847ed0c6501dc62c0739fd8e86a5ec096f3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.worldscientific.com/doi/reader/10.1142/S0129054116500179$$EPDF$$P50$$Gworldscientific$$H</linktopdf><link.rule.ids>314,780,784,3213,4872,27924,27925,55587</link.rule.ids></links><search><creatorcontrib>Tse, Savio S. H.</creatorcontrib><title>Belated Analyses of Three Credit-Based Adaptive Polling Algorithms</title><title>International journal of foundations of computer science</title><description>We study the problem of credit-based adaptive polling in undirected arbitrary point-to-point asynchronous networks. Polling consists of two rounds, namely propagation (broadcast) and feedback (confirmation, response) rounds. By adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths back to the initiator — a specific node who initiates the polling algorithm. The freedom in the feedback round relies on the use of credits in the propagation round. We re-visit three existing algorithms and analyse their average case communication bit complexities incurred by the credits in the propagation round, and these analyses match with the numerical results. We also give an optimal lower bound on the worst case bit message complexity for the case when the number of nodes in the network is unknown.</description><subject>Adaptive algorithms</subject><subject>Algorithms</subject><subject>Feedback</subject><subject>Graph theory</subject><subject>Lower bounds</subject><subject>Polling schemes</subject><subject>Propagation</subject><issn>0129-0541</issn><issn>1793-6373</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2016</creationdate><recordtype>article</recordtype><recordid>eNplkE9LAzEQxYMoWGo_gLcFz6uTZDdpjm3xHwgK1vOSTSZtJG1qslX67d2l4qWXmcN7v-HNI-Sawi2lFbt7B8oU1BWlogagUp2RUT95Kbjk52Q0yOWgX5JJzr4FqgSvWS1GZD7HoDu0xWyrwyFjLqIrluuEWCwSWt-Vc50H2epd57-xeIsh-O2qmIVVTL5bb_IVuXA6ZJz87TH5eLhfLp7Kl9fH58XspTRMCFXWHCpoLa20lK3hwmnElrdS21a2clpJtGD6_NQawQxIrpyd4lToGg0o4fiY3Bzv7lL82mPums-4T33s3LD-cyZA0ap30aPLpJhzQtfskt_odGgoNENbzUlbPQNH5iemYLPxuO288-YfPUV-AVSVauo</recordid><startdate>201608</startdate><enddate>201608</enddate><creator>Tse, Savio S. H.</creator><general>World Scientific Publishing Company</general><general>World Scientific Publishing Co. Pte., Ltd</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>201608</creationdate><title>Belated Analyses of Three Credit-Based Adaptive Polling Algorithms</title><author>Tse, Savio S. H.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c2669-53040bd14a77bc36faeeb3b7adb7b7847ed0c6501dc62c0739fd8e86a5ec096f3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2016</creationdate><topic>Adaptive algorithms</topic><topic>Algorithms</topic><topic>Feedback</topic><topic>Graph theory</topic><topic>Lower bounds</topic><topic>Polling schemes</topic><topic>Propagation</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Tse, Savio S. H.</creatorcontrib><collection>CrossRef</collection><jtitle>International journal of foundations of computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Tse, Savio S. H.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Belated Analyses of Three Credit-Based Adaptive Polling Algorithms</atitle><jtitle>International journal of foundations of computer science</jtitle><date>2016-08</date><risdate>2016</risdate><volume>27</volume><issue>5</issue><spage>579</spage><epage>594</epage><pages>579-594</pages><issn>0129-0541</issn><eissn>1793-6373</eissn><abstract>We study the problem of credit-based adaptive polling in undirected arbitrary point-to-point asynchronous networks. Polling consists of two rounds, namely propagation (broadcast) and feedback (confirmation, response) rounds. By adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths back to the initiator — a specific node who initiates the polling algorithm. The freedom in the feedback round relies on the use of credits in the propagation round. We re-visit three existing algorithms and analyse their average case communication bit complexities incurred by the credits in the propagation round, and these analyses match with the numerical results. We also give an optimal lower bound on the worst case bit message complexity for the case when the number of nodes in the network is unknown.</abstract><cop>Singapore</cop><pub>World Scientific Publishing Company</pub><doi>10.1142/S0129054116500179</doi><tpages>16</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0129-0541
ispartof International journal of foundations of computer science, 2016-08, Vol.27 (5), p.579-594
issn 0129-0541
1793-6373
language eng
recordid cdi_crossref_primary_10_1142_S0129054116500179
source World Scientific Journals
subjects Adaptive algorithms
Algorithms
Feedback
Graph theory
Lower bounds
Polling schemes
Propagation
title Belated Analyses of Three Credit-Based Adaptive Polling Algorithms
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T04%3A35%3A39IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Belated%20Analyses%20of%20Three%20Credit-Based%20Adaptive%20Polling%20Algorithms&rft.jtitle=International%20journal%20of%20foundations%20of%20computer%20science&rft.au=Tse,%20Savio%20S.%20H.&rft.date=2016-08&rft.volume=27&rft.issue=5&rft.spage=579&rft.epage=594&rft.pages=579-594&rft.issn=0129-0541&rft.eissn=1793-6373&rft_id=info:doi/10.1142/S0129054116500179&rft_dat=%3Cproquest_cross%3E2116260914%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c2669-53040bd14a77bc36faeeb3b7adb7b7847ed0c6501dc62c0739fd8e86a5ec096f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2116260914&rft_id=info:pmid/&rfr_iscdi=true