Broadcast is a central problem in distributed computing. Recently, Hussak and Trehan [PODC'19/DC'23] proposed a stateless broadcasting protocol (Amnesiac Flooding), which was surprisingly proven to terminate in asymptotically optimal time (linear in the diameter of the network). However, it remains unclear: (i) Are there other stateless terminating broadcast algorithms with the desirable properties of Amnesiac Flooding, (ii) How robust is Amnesiac Flooding with respect to faults?

Broadcast is a central problem in distributed computing. Recently, Hussak and Trehan [PODC'19/DC'23] proposed a stateless broadcasting protocol (Amnesiac Flooding), which was surprisingly proven to terminate in asymptotically optimal time (linear in the diameter of the network). However, it remains unclear: (i) Are there other stateless terminating broadcast algorithms with the desirable properties of Amnesiac Flooding, (ii) How robust is Amnesiac Flooding with respect to faults? In this paper we make progress on both of these fronts. Under a reasonable restriction (obliviousness to message content) additional to the fault-free synchronous model, we prove that Amnesiac Flooding is the only strictly stateless deterministic protocol that can achieve terminating broadcast. We identify four natural properties of a terminating broadcast protocol that Amnesiac Flooding uniquely satisfies. In contrast, we prove that even minor relax-ations of any of these four criteria allow the construction of other terminating broadcast protocols. On the other hand, we prove that Amnesiac Flooding can become non-terminating or non-broadcasting, even if we allow just one node to drop a single message on a single edge in a single round. As a tool for proving this, we focus on the set of all configurations of transmissions between nodes in the network, and obtain a dichotomy characterizing the configurations, starting from which, Amnesiac Flooding terminates. Additionally, we charac-terise the structure of sets of Byzantine agents capable of forcing non-termination or non-broadcast of the protocol on arbitrary networks .

A simple greedy algorithm to find a maximal independent set (MIS) in a graph starts with the empty set and visits every vertex, adding it to the set if and only if none of its neighbours are already in the set. In this paper, we consider (the complexity of decision problems related to) the generalisation of this MIS algorithm wherein any starting set is allowed. Two main approaches are leveraged. Firstly, we view the MIS algorithm as a sequential update of a Boolean network according to a permutation of the vertex set. Secondly, we introduce the concept of a constituency of a graph: a set of vertices that is dominated by an independent set. Recognizing a constituency is NP -complete, a fact we leverage repeatedly in our investigation. Our contributions are multiple: we establish that deciding whether all maximal independent sets can be reached from some configuration is coNP -complete; that fixing words (which reach a MIS from any starting configuration) and fixing permutations (briefly, permises) are coNP -complete to recognize; and that permissible graphs (graphs with a permis) are coNP -hard to recognize. We also exhibit large classes of permissible and non-permissible graphs, notably near-comparability graphs which may be of independent interest. Lastly, we extend our study to digraphs, where we search for kernels. Since the natural generalisation of our approach may not necessarily find a kernel, we introduce two further Boolean networks for digraphs: one always finds an independent set, and the other always finds a dominating set.

In this paper we introduce a new operation for Linear Programming (LP), called LP complementation , which resembles many properties of LP duality. Given a maximisation (resp. minimisation) LP P , we define its complement Q as a specific minimisation (resp. maximisation) LP which has the same objective function as P . Our central result is the LP complementation theorem, that relates the optimal value of P and the optimal value of its complement by . The LP complementation operation can be applied if and only if P has an optimum value greater than 1. To illustrate this, we first apply LP complementation to hypergraphs . For any hypergraph H , we review the four classical LPs, namely covering K ( H ) , packing P ( H ) , matching M ( H ) , and transversal T ( H ) . For every hypergraph H = ( V , E ) , we call the complement of H . For each of the above four LPs, we relate the optimal values of the LP for the dual hypergraph to that of the complement hypergraph (e.g. ). We then apply LP complementation to fractional graph theory . We prove that the LP for the fractional in-dominating number of a digraph D is the complement of the LP for the fractional total out-dominating number of the digraph complement of D . Furthermore we apply the hypergraph complementation theorem to matroids. We establish that the fractional matching number of a matroid coincide with its edge toughness. As our last application of LP complementation, we introduce the natural problem Vertex Cover with Budget (VCB) : for a graph G = ( V , E ) and a positive integer b , what is the maximum number t b of vertex covers S 1 , … , S t b of G , such that every vertex v ∈ V appears in at most b vertex covers? The integer b can be viewed as a “budget” that we can spend on each vertex and, given this budget, we aim to cover all edges for as long as possible. We relate VCB with the LP Q G for the fractional chromatic number χ f of a graph G . More specifically, we prove that, as b → ∞ , the optimum for VCB satisfies t b ∼ t f ⋅ b , where t f is the optimal solution to the complement LP of Q G . Finally, our results imply that, for any finite budget b , it is NP-hard to decide whether t b ≥ b + c for any 1 ≤ c ≤ b − 1 .

The domatic number of a graph is the maximum number of vertex disjoint dominating sets that partition the vertex set of the graph. In this paper we consider the fractional variant of this notion. Graphs with fractional domatic number 1 are exactly the graphs that contain an isolated vertex. Furthermore, it is known that all other graphs have fractional domatic number at least 2. In this note we characterize graphs with fractional domatic number 2. More specifically, we show that a graph without isolated vertices has fractional domatic number 2 if and only if it has a vertex of degree 1 or a connected component isomorphic to a 4-cycle. We conjecture that if the fractional domatic number is more than 2, then it is at least 7/3.

Finite dynamical systems (FDSs) are commonly used to model systems with a finite number of states that evolve deterministically and at discrete time steps. Considered up to isomorphism, those correspond to functional graphs. As such, FDSs have a sum and product operation, which correspond to the direct sum and direct product of their respective graphs; the collection of FDSs endowed with these operations then forms a semiring. The algebraic structure of the product of FDSs is particularly interesting. For instance, an FDS can be factorised if and only if it is composed of two sub-systems running in parallel. In this work, we further the understanding of the factorisation, division, and root finding problems for FDSs. Firstly, an FDS A is cancellative if one can divide by it unambiguously, i.e. AX=AY implies X=Y. We prove that an FDS A is cancellative if and only if it has a fixed point. Secondly, we prove that if an FDS A has a k-th root (i.e. B such that Bk=A), then it is unique. Thirdly, unlike integers, the monoid of FDS product does not have unique factorisation into irreducibles. We instead exhibit a large class of monoids of FDSs with unique factorisation. To obtain our main results, we introduce the unrolling of an FDS, which can be viewed as a space-time expansion of the system. This allows us to work with (possibly infinite) trees, where the product is easier to handle than its counterpart for FDSs.

Abstract We present a construction of partial spread bent functions using subspaces generated by linear recurring sequences (LRS). We first show that the kernels of the linear mappings defined by two LRS have a trivial intersection if and only if their feedback polynomials are relatively prime. Then, we characterize the appropriate parameters for a family of pairwise coprime polynomials to generate a partial spread required for the support of a bent function, showing that such families exist if and only if the degrees of the underlying polynomials are either 1 or 2. We then count the resulting sets of polynomials and prove that, for degree 1, our LRS construction coincides with the Desarguesian partial spread. Finally, we perform a computer search of all $$\mathcal{PS}\mathcal{}^-$$ PS - and $$\mathcal{PS}\mathcal{}^+$$ PS + bent functions of $$n=8$$ n = 8 variables generated by our construction and compute their 2-ranks. The results show that many of these functions defined by polynomials of degree $$d=2$$ d = 2 are not EA-equivalent to any Maiorana–McFarland or Desarguesian partial spread function.

The properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding and index coding, and in the context of hat games, such as the guessing game and Winkler's hat game. In this paper, we relate the problems mentioned above to properties of FDSs, including the number of fixed points, their stability, and their instability. We first introduce the guessing dimension and the coset dimension of an FDS and their counterparts for directed graphs. Based on the coset dimension, we then refine the existing equivalences between network coding and index coding. We also introduce the concept of the instability of FDSs and we study the stability and the instability of directed graphs. We prove that the instability always reaches the size of a minimum feedback vertex set for large enough alphabets. We also obtain some nonstable bounds independent of the number of vertices of the graph. We then relate the stability and the instability to the guessing number. We also exhibit a class of sparse graphs with large girth that have high stability and high instability; our approach is code-theoretic and uses the guessing dimension. Finally, we prove that the affine instability is always asymptotically greater than or equal to the linear guessing number.

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations toward their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear network coding. The guessing number approach converts this problem into determining the number of fixed points of coding functions f : An→ Anover a finite alphabet A (usually referred to as Boolean networks if A = {0, 1}) with a given interaction graph that describes which local functions depend on which variables. In this paper, we generalize the so-called reduction of coding functions in order to eliminate variables. We then determine the maximum number of fixed points of a fully reduced coding function, whose interaction graph has a loop on every vertex. Since the reduction preserves the number of fixed points, we then apply these ideas and results to obtain four main results on the linear network coding solvability problem. First, we prove that non-decreasing coding functions cannot solve any more instances than routing already does. Second, we show that the triangle-free undirected graphs are linearly solvable if and only if they are solvable by routing. This is the first classification result for the linear network coding solvability problem. Third, we exhibit a new class of non-linearly solvable graphs. Fourth, we determine large classes of strictly linearly solvable graphs.

Hat problems have recently become a popular topic in combinatorics and discrete mathematics. These have been shown to be strongly related to coding theory, network coding, and auctions. We consider the following version of the hat game, introduced by Winkler and studied by Butler et al. A team is composed of several players; each player is assigned a hat of a given color; they do not see their own color but can see some other hats, according to a directed graph. The team wins if they have a strategy such that, for any possible assignment of colors to their hats, at least one player guesses their own hat color correctly. In this paper, we discover some new classes of graphs which allow a winning strategy, thus answering some of the open questions of Butler et al. We also derive upper bounds on the maximal number of possible hat colors that allow for a winning strategy for a given graph.

In this paper, we are interested in the number of fixed points of functions $f:A^n\to A^n$ over a finite alphabet $A$ defined on a given signed digraph $D$. We first use techniques from network coding to derive some lower bounds on the number of fixed points that only depends on $D$. We then discover relationships between the number of fixed points of $f$ and problems in coding theory, especially the design of codes for the asymmetric channel. Using these relationships, we derive upper and lower bounds on the number of fixed points, which significantly improve those given in the literature. We also unveil some interesting behavior of the number of fixed points of functions with a given signed digraph when the alphabet varies. We finally prove that signed digraphs with more (disjoint) positive cycles actually do not necessarily have functions with more fixed points.

Two generalizations of the Hartmann-Tzeng (HT) bound on the minimum distance of q-ary cyclic codes are proposed. The first one is proven by embedding the given cyclic code into a cyclic product code. Furthermore, we show that unique decoding up to this bound is always possible and outline a quadratic-time syndrome-based error decoding algorithm. The second bound is stronger and the proof is more involved. Our technique of embedding the code into a cyclic product code can be applied to other bounds, too and therefore generalizes them.

Network coding is a new technique to transmit data through a network by letting the intermediate nodes combine the packets they receive. Given a network, the network coding solvability problem decides whether all the packets requested by the destinations can be transmitted. In this paper, we introduce a new approach to this problem. We define a closure operator on a digraph closely related to the network coding instance and we show that the constraints for network coding can all be expressed according to that closure operator. Thus, a solution for the network coding problem is equivalent to a so-called solution of the closure operator. We can then define the closure solvability problem in general, which surprisingly reduces to finding secret-sharing matroids when the closure operator is a matroid. Based on this reformulation, we can easily prove that any multiple unicast where each node receives at least as many arcs as there are sources solvable by linear functions. We also give an alternative proof that any nontrivial multiple unicast with two source-receiver pairs is always solvable over all sufficiently large alphabets. Based on singular properties of the closure operator, we are able to generalize the way in which networks can be split into two distinct parts; we also provide a new way of identifying and removing useless nodes in a network. We also introduce the concept of network sharing, where one solvable network can be used to accommodate another solvable network coding instance. Finally, the guessing graph approach to network coding solvability is generalized to any closure operator, which yields bounds on the amount of information that can be transmitted through a network.

While random linear network coding is a powerful tool for disseminating information in communication networks, it is highly susceptible to errors caused by various sources. Due to error propagation, errors greatly deteriorate the throughput of network coding and seriously undermine both reliability and security of data. Hence, error control for network coding is vital. Recently, constant-dimension codes (CDCs), especially Kötter-Kschischang (KK) codes, have been proposed for error control in random linear network coding. KK codes can also be constructed from Gabidulin codes, an important class of rank metric codes. Rank metric decoders have been recently proposed for both Gabidulin and KK codes, but they have high computational complexities. Furthermore, it is not clear whether such decoders are feasible and suitable for hardware implementations. In this paper, we reduce the complexities of rank metric decoders and propose novel decoder architectures for both codes. The synthesis results of our decoder architectures for Gabidulin and KK codes with limited error-correcting capabilities over small fields show that our architectures not only are affordable, but also achieve high throughput.

A symbolic approach to communication networks, where the topology of the underlying network is contained in a set of formal terms, was recently introduced. Many communication problems can be recast as dispersion problems in this setup. The so-called min-cut of a term set represents its number of degrees of freedom. For any assignment of function symbols, its dispersion measures the amount of information sent to the destinations. It was proved that the maximum dispersion asymptotically reaches the min-cut of the term set. In this paper, we refine this result in two ways. First, we prove a max-flow min-cut theorem for the Rényi entropy with order less than one, given that the inputs are equiprobably distributed; conversely, there is no max-flow min-cut theorem for Rényi entropy with order greater than one. Second, although linear coding functions have the practical appeal of low complexity, we prove that they are insufficient in general to reach the min-cut. More specifically, there exist term sets which have an arbitrarily large dispersion for non-linear coding functions, yet limited dispersion when linear coding functions are considered. Conversely, we show that if there is a solution based on low degree polynomials, then there exists a linear solution.

Traditionally, communication networks are modeled and analyzed in terms of information flows in graphs. In this paper, we introduce a new symbolic approach to communication networks, where the topology of the underlying network is contained in a set of formal terms. To any choice of coding functions we associate a measure of performance, referred to as the dispersion. Many communication problems can be recast as dispersion problems in this setup. We state and prove variants of a theorem concerning dispersion of information in communication networks which generalizes the network coding theorem. The dispersion theorem resembles the max-flow min-cut theorem for commodity networks and states that the minimal cut value can be asymptotically achieved by the use of coding functions based on a routing scheme that uses dynamic headers.

Models for noncoherent error control in random linear network coding (RLNC) and store and forward (SAF) have been recently proposed. In this paper, we model different types of random network communications as the transmission of flats of matroids. This novel framework encompasses RLNC and SAF and allows us to introduce a novel protocol, referred to as random affine network coding (RANC), based on affine combinations of packets. Although the models previously proposed for RLNC and SAF only consider error control, using our framework, we first evaluate and compare the performance of different network protocols in the error-free case. We define and determine the rate, average delay, and throughput of such protocols, and we also investigate the possibilities of partial decoding before the entire message is received. We thus show that RANC outperforms RLNC in terms of data rate and throughput thanks to a more efficient encoding of messages into packets. Second, we model the possible alterations of a message by the network as an operator channel, which generalizes the channels proposed for RLNC and SAF. Error control is thus reduced to a coding-theoretic problem on flats of a matroid, where two distinct metrics can be used for error correction. We study the maximum cardinality of codes on flats in general, and codes for error correction in RANC in particular. We finally design a class of nearly optimal codes for RANC based on rank metric codes for which we propose a low-complexity decoding algorithm. The gain of RANC over RLNC is thus preserved with no additional cost in terms of complexity.

The guessing number of a directed graph (digraph), equivalent to the entropy of that digraph, was introduced as a direct criterion on the solvability of a network coding instance. This paper makes two contributions on the guessing number. First, we introduce an undirected graph on all possible configurations of the digraph, referred to as the guessing graph, which encapsulates the essence of dependence amongst configurations. We prove that the guessing number of a digraph is equal to the logarithm of the independence number of its guessing graph. Therefore, network coding solvability is no more a problem on the operations made by each node, but is simplified into a problem on the messages that can transit through the network. By studying the guessing graph of a given digraph, and how to combine digraphs or alphabets, we are thus able to derive bounds on the guessing number of digraphs. Second, we construct specific digraphs with high guessing numbers, yielding network coding instances where a large amount of information can transit. We first propose a construction of digraphs with finite parameters based on cyclic codes, with guessing number equal to the degree of the generator polynomial. We then construct an infinite class of digraphs with arbitrary girth for which the ratio between the linear guessing number and the number of vertices tends to one, despite these digraphs being arbitrarily sparse. These constructions yield solvable network coding instances with a relatively small number of intermediate nodes for which the node operations are known and linear, although these instances are sparse and the sources are arbitrarily far from their corresponding sinks.

Codes in the projective space and codes in the Grassmannian over a finite field-referred to as subspace codes and constant-dimension codes (CDCs), respectively-have been proposed for error control in random linear network coding. For subspace codes and CDCs, a subspace metric was introduced to correct both errors and erasures, and an injection metric was proposed to correct adversarial errors. In this paper, we investigate the packing and covering properties of subspace codes with both metrics. We first determine some fundamental geometric properties of the projective space with both metrics. Using these properties, we then derive bounds on the cardinalities of packing and covering subspace codes, and determine the asymptotic rates of optimal packing and optimal covering subspace codes with both metrics. Our results not only provide guiding principles for the code design for error control in random linear network coding, but also illustrate the difference between the two metrics from a geometric perspective. In particular, our results show that optimal packing CDCs are optimal packing subspace codes up to a scalar for both metrics if and only if their dimension is half of their length (up to rounding). In this case, CDCs suffer from only limited rate loss as opposed to subspace codes with the same minimum distance. We also show that optimal covering CDCs can be used to construct asymptotically optimal covering subspace codes with the injection metric only.

Constant-dimension codes have recently received attention due to their significance to error control in noncoherent random linear network coding. What the maximal cardinality of any constant-dimension code with finite dimension and minimum distance is and how to construct the optimal constant-dimension code (or codes) that achieves the maximal cardinality both remain open research problems. In this paper, we introduce a new approach to solving these two problems. We first establish a connection between constant-rank codes and constant-dimension codes. Via this connection, we show that optimal constant-dimension codes correspond to optimal constant-rank codes over matrices with sufficiently many rows. As such, the two aforementioned problems are equivalent to determining the maximum cardinality of constant-rank codes and to constructing optimal constant-rank codes, respectively. To this end, we then derive bounds on the maximum cardinality of a constant-rank code with a given minimum rank distance, propose explicit constructions of optimal or asymptotically optimal constant-rank codes, and establish asymptotic bounds on the maximum rate of a constant-rank code.

Constant-dimension codes (CDCs) have been investigated for noncoherent error correction in random network coding. The maximum cardinality of CDCs with given minimum distance and how to construct optimal CDCs are both open problems, although CDCs obtained by lifting Gabidulin codes, referred to as KK codes, are nearly optimal. In this paper, we first construct a new class of CDCs based on KK codes, referred to as augmented KK codes, whose cardinalities are greater than previously proposed CDCs. We then propose a low-complexity decoding algorithm for our augmented KK codes using that for KK codes. Our decoding algorithm corrects more errors than a bounded subspace distance decoder by taking advantage of the structure of our augmented KK codes. In the rest of the paper we investigate the covering properties of CDCs. We first derive bounds on the minimum cardinality of a CDC with a given covering radius and then determine the asymptotic behavior of this quantity. Moreover, we show that liftings of rank metric codes have the highest possible covering radius, and hence liftings of rank metric codes are not optimal packing CDCs. Finally, we construct good covering CDCs by permuting liftings of rank metric codes.

Constant-dimension codes (CDCs) have been considered for error correction in random linear network coding, and low-complexity bounded distance decoders have been proposed. However, error performance, decoder error probability (DEP) in particular, of these bounded distance decoders has received little attention. In this paper, we first establish some fundamental geometric properties of the projective space. In particular, we show that the volume of the intersection of two spheres depends on only the two radii as well as the distance between and the dimensions of the two centers. Using these geometric properties, we then consider bounded distance decoders in both subspace and injection metrics and derive analytical expressions of their DEPs for CDCs over a symmetric operator channel, which ultimately depend on their distance distributions. Finally, we focus on CDCs obtained by lifting rank metric codes since their distance distributions are known, and obtain two important results. First, we obtain asymptotically tight upper bounds on the DEPs of bounded distance decoders in both metrics; the upper bounds decrease exponentially with the square of the minimum distance. Second, we show that the DEP for KK codes, obtained by lifting Gabidulin codes, is the highest up to a scalar among all CDCs obtained by lifting rank metric codes.

Codes in the projective space over a finite field, referred to as subspace codes, and in particular codes in the Grassmannians, referred to as constant-dimension codes (CDCs), have been proposed for error control in random network coding. In this paper, we study the packing and covering properties of subspace codes, which can be used with the subspace metric or the injection metric. We first determine some fundamental geometric properties of the projective space. Using these results, we derive bounds on the cardinalities of packing and covering subspace codes, and determine the asymptotic rate of optimal packing and optimal covering subspace codes for both metrics. We thus show that optimal packing CDCs are asymptotically optimal packing subspace codes for both metrics. However, optimal covering CDCs can be used to construct asymptotically optimal covering subspace codes only for the injection metric.

Constant-dimension codes have recently received attention due to their significance to error control in noncoherent random network coding. In this paper, we show that constant-rank codes are closely related to constant-dimension codes and we study the properties of constant-rank codes. We first introduce a relation between vectors in GF(qm)nand subspaces of GF(q)mor GF(q)n, and use it to establish a relation between constant-rank codes and constant-dimension codes. We then derive bounds on the maximum cardinality of constant-rank codes with given rank weight and minimum rank distance. Finally, we investigate the asymptotic behavior of the maximal cardinality of constant-rank codes with given rank weight and minimum rank distance.

In this correspondence, we first introduce the concept of elementary linear subspace, which has similar properties to those of a set of coordinates. We then use elementary linear subspaces to derive properties of maximum rank distance (MRD) codes that parallel those of maximum distance separable codes. Using these properties, we show that, for MRD codes with error correction capability , the decoder error probability of bounded rank distance decoders decreases exponentially with based on the assumption that all errors with the same rank are equally likely.

This paper investigates packing and covering properties of codes with the rank metric. First, we investigate packing properties of rank metric codes. Then, we study sphere covering properties of rank metric codes, derive bounds on their parameters, and investigate their asymptotic covering properties.

In this paper, we investigate the covering properties of rank metric codes. We first study the properties of balls with rank radii, and derive several useful results. We then derive both upper and lower bounds on the minimal cardinality of a code with given length and rank covering radius. Using these bounds, we obtain some covering properties of linear rank metric codes.

This paper investigates the relationship between the rank weight distribution of a linear code and that of its dual code. The main result of this paper is that, similar to the MacWilliams identity for the Hamming metric, the rank weight distribution of any linear code can be expressed as an analytical expression of that of its dual code. Remarkably, our new identity has a similar form to the MacWilliams identity for the Hamming metric. Our identity is also closely related to Delsarte's MacWilliams identity for the q-distance. We use a linear space based approach in the proof for our new identity, and adapt this approach to provide an alternative proof of the MacWilliams identity for the Hamming metric. Finally, we determine the relationship between moments of the rank distribution of a linear code and those of its dual code, and provide an alternative derivation of the rank weight distribution of maximum rank distance codes.

In this paper, we study properties of rank metric codes in general and maximum rank distance (MRD) codes in particular. For codes with the rank metric, we first establish Gilbert and sphere-packing bounds, and then obtain the asymptotic forms of these two bounds and the Singleton bound. Based on the asymptotic bounds, we observe that asymptotically Gilbert-Varsharmov bound is exceeded by MRD codes and sphere-packing bound cannot be attained. We also establish bounds on the rank covering radius of maximal codes, and show that all MRD codes are maximal codes and all the MRD codes known so far achieve the maximum rank covering radius.

The Gabidulin-Paramonov-Tretjakov (GPT) public-key cryptosystem and the GPT system with column scrambler, both based on Gabidulin codes, seem to have some advantages over McEliece's public-key cryptosystems using Goppa codes. Since the parameters of the GPT-type systems affect the work factors of attacks in different fashions and determine the effectiveness of these attacks in some cases, we evaluate the security and study the choice of parameters of the GPT-type cryptosystems with respect to some well-known structural and decoding attacks jointly. The performances of the GPT system with column scrambler and the GPT system are compared with that of McEliece's system