Algorithms For Extracting Timeliness Graphs

Computer Science – Distributed – Parallel – and Cluster Computing

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

We consider asynchronous message-passing systems in which some links are timely and processes may crash. Each run defines a timeliness graph among correct processes: (p; q) is an edge of the timeliness graph if the link from p to q is timely (that is, there is bound on communication delays from p to q). The main goal of this paper is to approximate this timeliness graph by graphs having some properties (such as being trees, rings, ...). Given a family S of graphs, for runs such that the timeliness graph contains at least one graph in S then using an extraction algorithm, each correct process has to converge to the same graph in S that is, in a precise sense, an approximation of the timeliness graph of the run. For example, if the timeliness graph contains a ring, then using an extraction algorithm, all correct processes eventually converge to the same ring and in this ring all nodes will be correct processes and all links will be timely. We first present a general extraction algorithm and then a more specific extraction algorithm that is communication efficient (i.e., eventually all the messages of the extraction algorithm use only links of the extracted graph).

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Algorithms For Extracting Timeliness Graphs 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 Algorithms For Extracting Timeliness Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms For Extracting Timeliness Graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-560263

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.