Specification, modeling and analysis of interactions among peers that communicate via messages are becoming increasingly important due to the emerging area of web services. Collaboration diagrams provide a convenient visual model for characterizing such interactions. An interaction can be characterized as a global sequence of messages exchanged among a set of peers, listed in the order they are sent. A collaboration diagram can be used to specify the set of allowable interactions among the peers participating to a composite web service. Specification of the interactions from such a global perspective leads to the realizability problem: Is it possible to construct a set of peers that generate exactly the specified interactions? In this paper we investigate the realizability of interactions specified by collaboration diagrams. We formalize the realizability problem by modeling peers as concurrently executing finite state machines. We give sufficient realizability conditions for different classes of collaboration diagrams. We generalize the collaboration diagrams to collaboration diagram graphs and show that collaboration diagram graphs are equivalent to conversation protocols. We show that the sufficient conditions for realizability of conversation protocols can be adopted to realizability of collaboration diagram graphs.