Verifying Parameterized Networks Specified by Vertex-Replacement Graph Grammars

Radu Iosif, Arnaud Sangnier, Neven Villani · 2025

Read Verifying Parameterized Networks Specified by Vertex-Replacement Graph Grammars by Radu Iosif, Arnaud Sangnier, Neven Villani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-01269.txt.

Introduction

Radu Iosif, Arnaud Sangnier, and Neven Villani tackle, in a 2025 computer science paper, the problem of checking safety for whole families of networks at once. In these families, nodes run copies of the same small process and shake hands in pairs to talk. The families are described by a grammar that swaps out single nodes to grow the network.

The authors show this checking task can be turned into the same task for a second grammar type that swaps whole edges. Extra edges are added to route messages along the way. The trick matters because many known checking tools exist for the second type. It opens dense network shapes, like full cliques, to those tools.

Catalog record

CREATORRadu Iosif, Arnaud Sangnier, Neven Villani
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-01269

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Verifying Parameterized Networks Specified by Vertex-Replacement Graph Grammars Radu Iosif, Arnaud Sangnier, Neven Villani Abstract We consider the parametric reachability problem ( 𝖯𝖱𝖯 \mathsf{PRP} ) for families of networks described by vertex-replacement ( VR ) graph grammars, where network nodes run replicas of finite-state processes that communicate via binary handshaking. We show that the 𝖯𝖱𝖯 \mathsf{PRP} problem for VR grammars can be effectively reduced to the 𝖯𝖱𝖯 \mathsf{PRP} problem for hyperedge-replacement ( HR ) grammars, at the cost of introducing extra edges for routing messages. This transformation is motivated by the existence of several parametric verification techniques for families of networks specified by HR grammars, or similar inductive formalisms. Our reduction enables applying the verification techniques for HR systems to systems with dense architectures, such as user-specified cliques and multi-partite graphs. 1 Introduction As pointed out in recent literature, “ network verification is a necessary part of deploying modern hyperscale datacenters ” [ 19 ] . In this context, verification considers global properties of routing control, such as access between point A and point B. Very often, the intended functionality of a network can be derived from its architecture, typically known at early stages of network design. The huge scale of present-day datacenters, of \sim\!\!10^{4} routers for a regional hub and continuously growing, requires parametric verification techniques, that work no matter how many servers in a rack, switches in a cluster, clusters in a layer, etc. Despite decades of theoretical research and an impressive body of results (see [ 7 ] for a nice survey), these techniques consider mostly hard-coded architectures, either dense ( e.g., cliques [ 16 ] ) or sparse ( e.g., rings [ 11 ] ) families of graphs with a common topological pattern. The problem of verifying networks with user-specified architecture has gained recent momentum, with the development of parametric verification techniques for systems described using logic [ 5 ] or graph grammars [ 20 ] . In principle, logic-based graph specification languages are good at describing global properties, such as planarity, k -colorability or reachability, which make them more suitable for the specification of correctness properties, than network design. On the other hand, graph grammars are appealing for their constructive aspect, i.e., defining how large graphs are built from smaller subgraphs. Moreover, this recursive way of describing sets of graphs is common among programmers and software engineers, who are familiar with inductively defined datastructures (lists, trees, etc.) used in both imperative and functional programming. Graph grammars are at the core of the theory of formal languages (see [ 13 ] for a comprehensive survey). Based on the underlying set of operations ( i.e., graph algebra), we distinguish between vertex-replacement ( VR ) and hyperedge-replacement ( HR ) grammars. In principle, HR graph grammars can specify families of graphs having bounded tree-width, such as chains, rings, stars, trees (of unbounded rank) and beyond, e.g., overlaid structures such as trees or stars with certain nodes linked in a list. Since cliques and grids are families of unbounded tree-width, neither can be specified using HR graph grammars. On the other hand, vertex-replacement ( VR ) grammars are strictly more expressive [ 12 ] . For instance, VR grammars can describe the sets {\{{K_{n}}\}}_{n\geq 1} of cliques and {\{{K_{n,m}}\}}_{n,m\geq 1} of complete bipartite graphs, among others. A concrete motivation for using VR grammars to design datacenter networks can be found in the informal description of the Azure datacenter architecture [ 17 , 19 ] , deployed in the Microsoft hyperscale cloud network ( Figure 1 ). The top-of-rack (ToR) switches connect servers hosted in a rack. Several ToR switches are connected together by a number of leaf switches. Leaf switches are in turn connected together by a set of spine switches, that connect the datacenter to the Azure regional network. These networks cannot be described as cliques, because of their layered structure. However, the links between each layer ( i.e., ToR, leaf, spine, regional spine) and its adjacent layers form a complete bipartite graph, thus lying outside the scope of HR grammars, which cannot define complete bipartite graphs of unbounded sizes 1 1 1 Each set {\{{K_{n,m}}\}}_{n\in N,m\in M} for N,M infinite subsets of \mathbb{N} , has unbounded tree-width, whereas HR -grammars define bounded tree-width sets. . T2-4-m T3-1 T3-2 T3-3 T3-p … Regional Spine ToR Servers T0-2 T0-k … … Leaf T0-1 Servers T0-1 T0-2 T0-k Servers T0-1 T0-2 T0-k … T1-1 T1-2 T1-3 T1-m T1-1 T1-2 T1-3 T1-m T1-1 T1-2 T1-3 T1-m … … … … … Spine … T2-1-1 T2-1-2 T2-1-3 T2-1-n T2-4-1 T2-4-2 T2-4-3 Figure 1: Azure Datacenter Switching Topology The precise relation between the expressivity of VR and HR grammars has been elegantly coined in a result by Courcelle, stating that the sets defined by HR grammars are exactly the sparse sets defined by VR grammars [ 12 ] . Moreover, each VR grammar can be transformed into an HR grammar producing a set of graphs with \epsilon -edges, such that the elimination of these edges from the HR language yields the original VR language. For instance, the elimination of \epsilon -edges from the graph from Figure 2 (b) yields the complete bipartite graph K_{4,3} from Figure 2 (a). u_{1} u_{2} u_{3} u_{4} v_{1} v_{2} v_{3} a (a) u_{\epsilon} v_{\epsilon} a u_{1} \epsilon u_{2} \epsilon u_{3} \epsilon u_{4} \epsilon v_{1} \epsilon v_{2} \epsilon v_{3} \epsilon (b) Figure 2: The complete bipartite graph \overrightarrow{K}_{4,3} (a) and one possible encoding using \epsilon -edges (b). Contribution We leverage the idea of transforming VR grammars into HR grammars modulo elimination of \epsilon -edges to define a reduction from the parametric reachability problem ( \mathsf{PRP} ) for systems described by VR grammars and finite-state local behaviors, with correctness properties given by unrestricted arithmetic formulæ over a set of variables, tracking how many processes are in a given local state, to the \mathsf{PRP} problem for systems described by HR grammars, having the same correctness property. This is motivated by several recent developments in the verification of parametric systems with HR -style architecture descriptions. In particular, [ 10 ] reports on an inference of structural invariants ( i.e., over-approximations of the reachable set, that can be derived from the structure of the network) for architectures described using a variant of Separation Logic with inductive definitions (same expressivity as HR grammars) Moreover, [ 9 ] gives an abstraction technique that folds similar network nodes into a finite Petri net, whose coverability problem over-approximates the original parametric coverability problem. In this paper, we give a more general reduction method, that preserves all safety properties specified by arithmetic assertions, rather than the particular case of coverability. Related Work The literature on parametric verification is too large to be recalled here. We point to [ 7 ] for a survey on the (un)decidability results, typically concerning clique or ring architectures. The specification of network architectures using inductive definitions can be traced back to the work on network grammars [ 22 , 20 , 18 ] , that use inductive rules to describe systems with linear (pipeline, token-ring) architectures. These initial works target mainly safety properties, by inferring network invariants [ 23 , 21 ] . Pipeline and clique architectures are also considered by methods based

Read the complete text