Bilateral Ranking Negotiations

• Autorzy: Mazurkiewicz A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

structured graphs; bilateral negotiations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 60, nr 1-4
• Strony: 1--16
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Mazurkiewicz A.

• Institute of Computer Science, Polish Academy of Science, Ordona 21, 01-237 Warsaw, Poland,

Bibliografia

• [1] ANGLUIN,D.: Local and global properties in networks of processors, in: Proc. of 12th Symp. on Theory-of Computing (1980) 82-93
• [2] COURCELLE,B., MÉTIVIER,Y.: Coverings and Minors: application to local computations in graphs, in: Europ. Journal of Combinatorics 15 (1994) 127-138
• [3] DIJKSTRA,E. W.: Solution of a problem in concurrent programming control. Comm, of ACM 8 (1965) 569
• [4] FISHER,M.J., LYNCH,N.A.. MERRITT,A.: Easy impossibility proofs for distributed consensus problems, in: Distributed Computing 1 (1986)26-29
• [5] GODARD,E.:(Ph.D. dissertation) A characterization of families of graphs in which election is possible, in: Proc. of Foundations of Software Sei. and Comp. Structures. LNCS 2303 (2002) 159-171
• [6] GODARD,E., MÉTIVIER,Y., MUSCHOLL, A.: The power of local computations in graphs with initial knowledge, in: Proc. of Theory and Applications of Graph Transformations '98 1764 LNCS (2000) 71-84
• [7] LE LANN,G.: Distributed systems - towards a formal approach, in: Information Processing 77 (IFIP), Gilchrist B., (editor), North-Holland (Amsterdam). (1977) 155-160.
• [8] LITOVSKY,I., MÉTIVIER, Y., SOPEÑA,E.: Graph relabelling systems and distributed algorithms, in: H.Ehrig, H.-J.Kreowski, U.Montanari, and G.Rozenberg (eds) Handbook of graph grammars and computing by graph transformation 3, World Scientific (1999) I - 56
• [9] LITOVSKY,I., METIVIER,Y., ZIELONKA, W.: On the recognition of families of graphs with local computations, in: Information & Computation 118 (1995) 110-119
• [10] MAZURKIEWICZ, A.: Solvability of the asynchronous ranking problem, in: Inf. Processing Letters 28 (1988)221-224.
• [11] MAZURKIEWICZ,A.: Distributed enumeration, in: Inf. Processing Letters 61 (1997) 233-239
• [12 MAZURKIEWICZ,A.: Locally Computable enumerations, in: Proc. of XI Intern. Symposium FCT97, Lecture Notes in Computer Science 1279 (1997) 51 -66
• [13] MAZURKIEWICZ,A.: Distributed Ordering in Trees, to appear (2002)