Abstract A dynamic database in a communications network consists of a set of messages, where a sequence of different versions of each message is generated over time in a repeated and uncoordinated process and where the appearances of the various message versions are distributed among the nodes. The message versions are to be disseminated in the network so that each message version eventually resides at each node. Flooding is a distributed procedure for disseminating message versions. The use of flooding to disseminate repeated and uncoordinated message versions is an integral part of a generic adaptive routing mechanism similar to that used in ARPANET and proposed for the INTERNET and is an element of a method proposed for improving survivability in intra‐LATA networks. A model is formulated to analyze the performance of the dissemination by flooding of repeated and uncoordinated message versions. The worst‐case time complexity is established, showing that flooding is an optimal procedure in terms of this measure. Special properties of flooding in a tree are also established. A key parameter is a separator, which is a lower bound on the time interval between the initial generation of a particular version of any message and the initial generation of the next version of that message.

Performance properties are established for the dissemination by flooding of a database that is initially distributed among the nodes of a communications network. An example of this general process is the dissemination of network status information as a component of the adaptive routing mechanism in a network like Arpanet. Bounds are given on the progress of the dissemination process at a sequence of times before the completion of the process, whereas earlier results only bounded the time until completion. The present bounds further extended earlier analysis by treating the diameter explicitly as a parameter. Specialized versions of the bounds are given for k-connected networks. The bounds yield a recognition property whereby a node can recognize that it has received the entire database without having a priori knowledge of the size of the database. An earlier assumption about a fixed time for correct message transmission over any edge is relaxed to assume only an upper bound on these transmission times.>

The author establishes the worst-case time complexity of all-to-all broadcast, which involves the simultaneous broadcast of messages from each node in a network to each other node, as with the dissemination of network status information for adaptive routing in ARPANET, by flooding. It it shown to be almost two times the optimum. This suboptimality of flooding results from the selection method permitting some message(s) to be consistently blocked by others. It is possible to avoid such blocking and attain the optimal worst-case time complexity by flooding within a spanning subtree. Simulations examine the performance of all-to-all broadcast by flooding using different selection methods. The best overall performance came using random selection, with FIFO next best, followed by LIFO, and in-order last. This relative performance is consistent with the hypothesis that flooding will generally perform better if implemented with a selection method that tends to avoid having some message(s) consistently blocked by others. Simulations show that the optimal worst-case time complexity is rarely exceeded, and then by only a relatively small amount.>

An efficient and flexible algorithm is presented for finding a k shortest loopless path with distinct initial links from one node to each other node. Low-order polynomial bounds are established for the worst-case time complexity of the algorithm, showing it to offer a substantial improvement over applying known algorithms to the problem. The algorithm can incorporate various extensions, including the ability to handle an algebraic objective, which enhance its applicability to diverse network models. In addition, the k shortest path formulation and algorithm are proposed as a basis for network survivability measures where path length bounds exist.>

Concurrent broadcast involves the dissemination of a database, consisting of messages initially distributed among the nodes of a network, so that a copy of the entire database eventually resides at each node. One application is the dissemination of network status information for adaptive routing in a communications network. This paper examines the time complexity and communication complexity of several distributed procedures for concurrent broadcast. The procedures do not use information depending on the network topology. The worst-case time complexity of a flooding procedure for concurrent broadcast is shown to be linear in the number of nodes plus the number of messages, and no other procedure for concurrent broadcast has a better worst-case time complexity. A variant of flooding is proposed to eliminate redundant message receipts from the flooding process by real-time signaling between neighbors concerning messages residing at each. This variant can reduce communication complexity, while having a worst-case time complexity similar in form to that of the flooding procedure. Special properties of concurrent broadcast in a tree are also given. The present time complexity results can be used to bound the time during which inconsistent databases may reside at different nodes, to evaluate and compare procedures for (or including) concurrent broadcast, and to schedule a sequence of instances of concurrent broadcast so that the instances do not overlap and there is no need for sequence numbers.

Abstract The connection between the minimum‐cut problem in a capacitated network and certain combinatorial problems is well‐known. This article presents and analyzes a selection problem in the context of a cooperative game, with emphasis on the key role of associated minimum‐cut problems. Each coalition selects economic activities from private activities available to its members and public activities available to all coalitions. For each coalition, a minimum‐cut problem finds an optimal selection and the value of the characteristic function. The game is a convex game. Applying the Greedy Algorithm involves solving n minimum‐cut problems, where n is the number of players. The solution of n minimum‐cut problem determines whether a proposed payoff vector is in the core. An optimal selection of activities varies monotonically with the coalition membership and with the value of each activity. The Shapley value and each extreme point of the core vary monotonically with the value of each activity.