A quantitative approach to dynamic networks
Baruch Awerbuch, Oded Godlreich, Amir Herzberg · 1990
We present a quantitative approach to dynamic networks.Dynamic networks, extensively studied in the last decade, are asynchronous networks with arbitrary topology, in which links and processors repeatedly fail and recover.Loosely speaking, we quantify the reliability of a link at a given moment as the time since the link last recovered.This quantitative definition allows us to iuvestigate protocols that either assume a certain amount of reliability, or provide service only to sufficiently reliable parts of the network.There are several tasks which cannot be solved efficiently when defined in the known (qualitative)approaches, but may be solved efliciently using the new quantitative definitions.We demonstrate this on the broodcast task.Broadcast is basically an order preserving transmission of a sequence of messages from a source processor to all other processors.Every processor which satisfies some fairness condition should accept the messages.This requires unbounded resources, if the fairness is defined using the known (qualitative) approaches.Hence, we give a new