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!
Description
Summary: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.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054116500179