Bilateral Ranking Negotiations

Issue title: Concurrency Specification and Programming (CS&P 2003)

Article type: Research Article

Authors: Mazurkiewicz, Antoni

Affiliations: Institute of Computer Science of PAS, Ordona 21, 01-237 Warsaw, Poland

Abstract: In general, a negotiation within a group of participants is a process, which starting with participants in some arbitrary (initial) states eventually come to an agreement with all participants being in the negotiated state. The formal method used for discussing the considered issue are local computations; in general, they consist in transforming states of whole structures by way of transforming states of some of their substructures. Negotiation procedures are local computations that act according to negotiation protocols. The paper aims to discuss communication structures that admit negotiations limited to direct communications between at most two negotiating partners (bilateral negotiations). As a formal model of the communication structures graphs are used, with nodes representing participants of negotiations, edges the direct links between them, and a total (linear) ordering of nodes as the goal of negotiations; in our setup substructures subjected to transformations consist of two adjecent nodes only. There are known protocols that can solve particular problems; the question arises whether the same problems can be solved by local computations using substructures of size at most two. The present paper aims to offer an answer to this question.

Journal: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 1-16, 2004