Given a family @math of graphs and a positive integer @math , a graph @math is called vertex @math -fault-tolerant with respect to @math , denoted by @math -FT @math , if @math contains some @math as a subgraph, for every @math with @math . Vertex-fault-tolerance has been introduced by Hayes [A graph model for fault-tolerant computing systems, IEEE Transactions on Computers, C-25 (1976), pp. 875-884.], and has been studied in view of potential applications in the design of interconnection networks operating correctly in the presence of faults. We define the Fault-Tolerant Complete Matching (FTCM) Problem in bipartite graphs of order @math : to design a bipartite @math , with @math , @math , @math , that has a FTCM, and the tuple @math , where @math and @math are the maximum degree in @math and @math , respectively, is lexicographically minimum. @math has a FTCM if deleting at most @math vertices from @math creates @math that has a complete matching, i.e., a matching of size @math . We show that if @math is integer, solutions of the FTCM Problem can be found among @math -regular bipartite graphs of order @math , with @math , and @math . If @math then all @math -regular bipartite graphs of order @math have a FTCM, and for @math , it is not the case. We characterize the values of @math , @math , @math , and @math that admit an @math -regular bipartite graph of order @math , with @math , and give a simple construction that creates such a graph with a FTCM whenever possible. Our techniques are based on Hall's marriage theorem, elementary number theory, linear Diophantine equations, properties of integer functions and congruences, and equations involving them.
A related line of research is not to design the smallest fault tolerant graphs (in terms of any metric, like the ones given above), but to analyze the level of fault tolerance assured by prescribed topologies @cite_2 @cite_12 . This topic is of particular interest for algorithm design in high performance computing. Supercomputers are comprised of many processing nodes (with some local memory) that use an interconnection network to communicate during the execution of distributed algorithms. An algorithm delegates computational tasks to different nodes, and uses some logical topology for its message passing. This logical topology has to be somehow embedded in the interconnection network provided by the supercomputer. So it is of practical interest to study if the message passing topologies most common in algorithm design (like cycles, and trees of certain types) can still be embedded in interconnection topologies provided by supercomputers (often similar to hypercubes) when the system presents some faults @cite_2 .
@cite_12 @cite_2
2943552721 2298465770
Interconnection networks based on the k-ary n-tree topology are widely used in high-performance parallel computers. However, this topology is expensive and complex to build. In this paper we evaluate an alternative tree-like topology that is cheaper in terms of cost and complexity because it uses fewer switches and links. This alternative topology leaves unused upward ports on switches, which can be rearranged to be used as downward ports. The increase of locality might be efficiently exploited by applications. We test the performance of these thin-trees, and compare it with that of regular trees. Evaluation is carried out using a collection of synthetic traffic patterns that emulate the behavior of scientific applications and functions within message passing libraries, not only in terms of sources and destinations of messages, but also considering the causal relationships among them. We also propose a methodology to perform cost and performance analysis of different networks. Our main conclusion is that, for the set of studied workloads, the performance drop in thin-trees is less noticeable than the cost savings. Fault-tolerant distributed algorithms play an important role in many critical high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. We introduce PSync, a domain specific language based on the Heard-Of model, which views asynchronous faulty systems as synchronous ones with an adversarial environment that simulates asynchrony and faults by dropping messages. We define a runtime system for PSync that efficiently executes on asynchronous networks. We formalise the relation between the runtime system and PSync in terms of observational refinement. The high-level lockstep abstraction introduced by PSync simplifies the design and implementation of fault-tolerant distributed algorithms and enables automated formal verification. We have implemented an embedding of PSync in the Scala programming language with a runtime system for partially synchronous networks. We show the applicability of PSync by implementing several important fault-tolerant distributed algorithms and we compare the implementation of consensus algorithms in PSync against implementations in other languages in terms of code size, runtime efficiency, and verification.