This paper deals with graph relabelling introduced in [LMS95]. Our first result concerns the open problem of searching a graph as a minor in a graph with a distinguished vertex, by means of graph relabellings. We give...
详细信息
ISBN:
(纸本)3540643001
This paper deals with graph relabelling introduced in [LMS95]. Our first result concerns the open problem of searching a graph as a minor in a graph with a distinguished vertex, by means of graph relabellings. We give and prove a graph rewriting system which answers to this problem. Secondly we define and study normal forms of graph relabellings. We prove that any graph rewriting system can be simulated by a system in k-normal form (with an integer k depending on the original system). Proofs for both results are linked by the enumeration systems they wed.
We present a formal method based on graph rewriting systems for the specifications and the proofs of fault-tolerant distributed algorithms. Our method deals with crash failures. In a crash failure system the process c...
详细信息
ISBN:
(纸本)3540292004
We present a formal method based on graph rewriting systems for the specifications and the proofs of fault-tolerant distributed algorithms. Our method deals with crash failures. In a crash failure system the process can fail by crashing, i.e. by permanently halting. The faulty processes are the processes contaminated by the crashes. The methodology is formalized in two phases. In the first phase, we build the set of illegitimate configurations to specify the faults and the faulty processes. The second phase is devoted to the addition of correction rules in the initial graph rewriting system used to encode the distributed algorithm. These rules are able to detect and eliminate the faults locally during the computation. This method can be implemented under an asynchronous message passing system which notifies the faults. To illustrate this approach, we present examples of fault-tolerant distributed spanning tree algorithms.
This paper presents one possible implementation of a transformation that performs linear mapping to a lower-dimensional subspace. Principal component subspace will be the one that will be analyzed. Idea implemented in...
详细信息
Formal proofs of distributed algorithms are long, hard and tedious. We propose a general approach, based on the formal method Event-B, to automatically generate correct programs of distributed algorithms. Our approach...
详细信息
ISBN:
(纸本)9780769550022
Formal proofs of distributed algorithms are long, hard and tedious. We propose a general approach, based on the formal method Event-B, to automatically generate correct programs of distributed algorithms. Our approach is implemented with a translation tool, called B2Visidia, that generates Java code from an Event-B specification related to distributed algorithms. The resulting code can be run on classical distributed computing systems. To execute the induced programs, we use a tool called Visidia that can be used for experimenting, testing and visualizing programs of distributed algorithms.
In the paper a class of locally derivable graphs is defined and discussed. Well known particular cases of derivable graphs are (among others) trees, complete, and triangular graphs;in the paper a broader class of loca...
详细信息
In the paper a class of locally derivable graphs is defined and discussed. Well known particular cases of derivable graphs are (among others) trees, complete, and triangular graphs;in the paper a broader class of locally derivable graphs, called closed graphs, is defined. Nodes and edges of closed graphs can be partitioned into external and internal ones;the main property of such graphs their local reducibility: successive removing its external nodes leads eventually to a singleton, and removing its external edges leads to an a spanning tree of the graph. The class of closed graphs is then a class enabling structural reducing. This property can be applied in processor networks to design some local procedures leading to global results.
Formal proofs of distributed algorithms are long, hard and tedious. We propose a general approach, based on the formal method Event-B, to automatically generate correct programs of distributed algorithms. Our approach...
详细信息
ISBN:
(纸本)9781479904051
Formal proofs of distributed algorithms are long, hard and tedious. We propose a general approach, based on the formal method Event-B, to automatically generate correct programs of distributed algorithms. Our approach is implemented with a translation tool, called B2Visidia, that generates Java code from an Event-B specification related to distributed algorithms. The resulting code can be run on classical distributed computing systems. To execute the induced programs, we use a tool called Visidia that can be used for experimenting, testing and visualizing programs of distributed algorithms.
In the paper triangular graphs are discussed. The class of triangular graphs is of special interest as unifying basic features of complete graphs and trees. The main issue addressed in the paper is to characterize cla...
详细信息
In the paper triangular graphs are discussed. The class of triangular graphs is of special interest as unifying basic features of complete graphs and trees. The main issue addressed in the paper is to characterize class of triangular graphs (defined globally) by local means. Namely, it is proved that any triangular graph can be constructed from a singleton by successive extensions with nodes having complete neighborhoods. Next, the proved theoretical properties are applied for designing some local algorithms for triangular graphs: for elections a leader and for constructing their spanning trees. The fairness of these algorithms is proved, which means that any node can be elected and any spanning tree can be constructed by execution of these algorithms.
暂无评论