Processes in a concurrent system need to coordinate using an underlying shared memory or a message-passing system in order to solve agreement tasks such as, for example, consensus or set agreement. However, coordination is often needed to "break the symmetry" of processes that are initially in the same state, for example, to get exclusive access to a shared resource, to get distinct names, or to elect a leader. This paper introduces and studies the family of generalized symmetry breaking (GSB) tasks, that includes election, renaming and many other symmetry breaking tasks. Differently from agreement tasks, a GSB task is "inputless", in the sense that processes do not propose values; the task only specifies the symmetry breaking requirement, independently of the system's initial state (where processes differ only on their identifiers). Among various results characterizing the family of GSB tasks, it is shown that perfect renaming is universal for all GSB tasks. The paper then studies the power of renaming with respect to $k$-set agreement. It shows that, in a system of $n$ processes, perfect renaming is strictly stronger than $(n-1)$-set agreement, but not stronger than $(n-2)$-set agreement. Furthermore, $(n+1)$ renaming cannot solve even $(n-1)$-set agreement. As a consequence, there are cases where set agreement and renaming are incomparable when looking at their power to implement each other. Finally, the paper shows that there is a large family of GSB tasks that are more powerful than $(n-1)$-set agreement. Some of these tasks are equivalent to $n$-renaming, while others lie strictly between $n$-renaming and $(n+1)$-renaming. Moreover, none of these GSB tasks can solve $(n-2)$-set agreement. Hence, the GSB tasks have a rich structure and are interesting in their own. The proofs of these results are based on combinatorial topology techniques and new ideas about different notions of non-determinism that can be associated with shared objects. Interestingly, this paper sheds a new light on the relations linking set agreement and symmetry breaking.
