MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Here are some further examples: Linial (1992) shows that 3-colouring a cycle requires $\Omega(\log^* n)$ communication rounds (and this is tight). Similar but more general results include, e.g., Czygrinow et al. (2008), which is a neat application of Ramsey's theorem. For something different, see, e.g., Kuhn et al. (2004).