A new look at fault-tolerant network routing
type: Item
instance of: scholarly article
title: A new look at fault-tolerant network routing
zbMATH Open document ID: 0638.68010
DOI: 10.1016/0890-5401(87)90031-9
author: Danny Dolev
author: Joseph Y. Halpern
author: H. Raymond Strong
author: Barbara B. Simons
published in: Information and Computation
publication date: 1987-01-01T00:00:00Z
review text: We model a communication network as a graph in which a processor is a node and a communication link is an edge. A routing for such a network is a fixed path, or route, between each pair of nodes. Given a network with a predefined routing, we study the effects of faulty components on the routing. Of particular interest is the number of routes along which a message must travel between any two nonfaulty nodes. This problem is analyzed for specific families of graphs and for classes of routings. We also give some bounds for general versions of the problem. Finally, we conclude with one of the most important contributions of this paper, a list of interesting and apparently difficult open problems.
Mathematics Subject Classification ID: 68N99
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 4041238
zbMATH Keywords: fault-tolerant routings
zbMATH Keywords: network communication protocol
zbMATH Keywords: communication network
MaRDI profile type: Publication
full work available at URL: 0890-5401(87)90031-9
OpenAlex ID: W2048447277
cites work: Q3941433
cites work: Diameter bounds for altered graphs
cites work: Authenticated Algorithms for Byzantine Agreement
cites work: Q3883524
cites work: A Scheme for Fast Parallel Communication
description: scientific article; zbMATH DE number 4041238