  While the relationship of time and space is an established topic in
traditional centralised complexity theory, this is not the case in distributed
computing. We aim to remedy this by studying the time and space complexity of
algorithms in a weak message-passing model of distributed computing. While a
constant number of communication rounds implies a constant number of states
visited during the execution, the other direction is not clear at all. We
consider several graph families and show that indeed, there exist non-trivial
graph problems that are solvable by constant-space algorithms but that require
a non-constant running time. This provides us with a new complexity class for
distributed computing and raises interesting questions about the existence of
further combinations of time and space complexity.
