So okay. Let's get the CS notation out of the way:
"Message passing" at full decentralization:
- O(1) from a single node's perspective
- O(n) from a whole-network zoom-out perspective (inherent: add a user, it's one more user)
Okay, that's reasonable and what you'd expect