In the paper, a new augmented binary-tree multiprocessor architecture, called LAB-tree, is proposed. It consists of ann-level full binary tree augmented with (2n−2) redundant links. The short and regular redundant links improve several properties of the full binary tree, such as increased tolerance, reduced traffic congestion and efficient routing of messages. It is shown that there exist at least two node-disjoint paths between every pair of nodes in the LAB-tree. In fact, all nonfaulty nodes remain connected in the presence of one faulty node at each level of the tree. The LAB-tree supports simple shortest-path routing algorithms which distribute messages evenly over links. The LAB-tree can be constructed modularly in VLSI by interconnecting modules of smaller size.