Algorithms for Extracting Timeliness Graphs

DOI10.1007/978-3-642-13284-1_11MaRDI QIDQ3569121zbMATH OpenOpenAlexFDO

Authors Carole Delporte-Gallet, Stéphane Devismes, Hugues Fauconnier, Mikel Larrea

Publication date 17 June 2010

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.1058

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Network design and communication in computer systems (68M10)

Abstract: 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).

Recommendations

• An introduction to temporal graphs: an algorithmic perspective
• An introduction to temporal graphs: an algorithmic perspective
• Assigning times to minimise reachability in temporal graphs
• A Graph-Theoretic Approach for Timing Analysis and its Implementation
• Reachability in graph timelines
• Complexity and algorithms for reasoning about time
• Fast and Simple Connectivity in Graph Timelines
• Timeline cover in temporal graphs: exact and approximation algorithms

Cited in

(3)

• Fast and Simple Connectivity in Graph Timelines
• Engineering Time-Expanded Graphs for Faster Timetable Information
• Correlating Alerts into Compressed Graphs Using an Attribute-Based Method and Time Windows

This page was built for publication: Algorithms for Extracting Timeliness Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569121)