Communication Gap for Finite Memory Devices
Tomasz Jurdzinski and Miroslaw Kutylowski
So far, not much is known on communication issues for computations on
distributed systems, where the components are weak and simultaneously
the communication bandwidth is severely limited. We consider synchronous
systems consisting of finite automata which communicate by sending
messages while working on a shared read-only data. We consider the
number of messages necessary to recognize a language as a its complexity
measure.
We present an interesting phenomenon that the systems described require
either a constant number of messages or at least Omega((logloglog n)^c)
of them (in the worst case) for input data of length n and some constant
c. Thus, in the hierarchy of message complexity classes there is a gap
between the languages requiring only O(1) messages and those that need a
non-constant number of messages. We show a similar result for systems of
one-way automata. In this case, there is no language that requires
omega(1) and o(log n) messages (in the worst case). These results hold
for any fixed number of automata in the system.
The lower bound arguments presented in this paper depend very much on
results concerning solving systems of diophantine equations and
inequalities.