This paper describes a novel approach for obtaining semantic interoperability among data sources in a bottom-up, semi-automatic manner without relying on pre-existing, global semantic models. We assume that large amounts of data exist that have been organized and annotated according to local schemas. Seeing semantics as a form of agreement, our approach enables the participating data sources to incrementally de-velop global agreement in an evolutionary and completely decentralized process that solely relies on pair-wise, local interactions: Participants provide translations between schemas they are interested in and can learn about other translations by routing queries (gossiping). In previous work we relied on the realistic assumption that such transla-tions would be provided manually only. In contrast to that, we assume in this paper that only some translations exist and generate random translations for reaching overall sematic agreement automatically. To support the participants in assessing the seman-tic quality of the achieved agreements we develop a formal framework that takes into account both syntactic and semantic criteria. The assessment process is incremental and the quality ratings are adjusted along with the operation of the system. Ultimately, this process results in global agreement, i.e., the semantics that all participants under-stand. We discuss strategies to efficiently find translations and provide results from our experiments to justify our claims. We specifically focus on semantic analyses and pro-vide pointers to the possible quality that is achievable through semantic analysis only. Our approach applies to any system which provides a communication infrastructure (existing websites or databases, decentralized systems, P2P systems) and offers the op-portunity to study semantic interoperability as a global phenomenon in a network of information sharing parties.