Asynchronous Bounded Expected Delay Networks

Details Asynchronous Bounded Expected Delay Networks Asynchronous Bounded Expected Delay Networks

2010-03-10

arxiv.org/abs/1003.2084v3

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

The commonly used asynchronous bounded delay (ABD) network models assume a fixed bound on message delay. We propose a probabilistic network model, called asynchronous bounded expected delay (ABE) model. Instead of a strict bound, the ABE model requires only a bound on the expected message delay. While the conditions of ABD networks restrict the set of possible executions, in ABE networks all asynchronous executions are possible, but executions with extremely long delays are less probable. In contrast to ABD networks, ABE networks cannot be synchronised efficiently. At the example of an election algorithm, we show that the minimal assumptions of ABE networks are sufficient for the development of efficient algorithms. For anonymous, unidirectional ABE rings of known size N we devise a probabilistic leader election algorithm having average message and time complexity O(N).

Affiliated with

Also associated with

No associations

Rating

Asynchronous Bounded Expected Delay Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asynchronous Bounded Expected Delay Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asynchronous Bounded Expected Delay Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-341879