Anonymous adversarial dynamic networks with logarithmic memory and communication

In seminal work on Adversarial Dynamic Networks, Kuhn, Lynch and Oshman (STOC 2010) [19] studied dynamic networks in which links are selected by an adversary and the number of network nodes is initially unknown. In such networks, they showed upper and lower bounds for computing the size of the network and any computable function of the nodes initial inputs. In this work, we address the same question in dynamic networks which additionally are: anonymous, possibly disconnected, and where internal memory and links’ bandwith are logarithmically limited. In the above framework, we study a fundamental communication principle – the All-to-all problem: each node has an input message to be delivered to all other nodes. (Once a node receives all inputs, any function can be computed locally.) Because of anonymity, each node needs to receive only a set of all input messages, each accompanied by a number of their initiating nodes (message multiplicity). We prove that this can be done deterministically in time proportional to the total number of messages’ bits multiplied by a small polynomial in networks’ parameters – namely, in the (initially unknown) number of nodes n and in the lower bound on the isoperimetric numbers of dynamically evolving graphs imin. Our results prove that a polynomial bit-throughput is possible in adversarial and anonymous dynamic networks with logarithmically limited bandwidth and internal memory.