Multilateral Ranking Negotiations

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

Abstrakty

EN

In general, negotiations within a group of participants are processes, that starting with participants in some arbitrary (initial) states eventually will achieve an agreement with all participants being in the required negotiated states. Process of negotiation is performed according to a negotiation protocol. Here, an ordering of participants is taken as the negotiation goal; constructing a negotiation protocol for this purpose is referred to as the ranking problem. The formal method used for discussing the considered issue are local computations; in general, they consist in transforming states of the whole structure by way of transforming states of its substructures. The paper aims to discuss communication structures that admit negotiations limited to direct communications between participants of a single 'association' at a time. Necessary and sufficient conditions for existence of such a ranking protocol for considered structures are formulated and a universal protocol for ranking is given. The paper is a generalization of bilateral negotiations presented in [14], where negotiations are limited to associations containing at most two members; the multilateral protocol presented in this paper covers the case of bilateral negotiations.

Słowa kluczowe

EN

bilateral negotiations; multilateral negotations; communication structures

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 63, nr 2,3
• Strony: 241--258
• Opis fizyczny: Bibliogr. 14 poz., rys., tab.

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] CHALOPIN, J., M´ETIVIER, Y.: Election and Local Computations on Edges (2004) (to appear in LNCS).
• [3] COURCELLE, B., M´ETIVIER, Y.: Coverings and Minors: application to local computations in graphs, in: Europ. Journal of Combinatorics 15 (1994) 127-138.
• [4] DIJKSTRA, E.W.: Solution of a problem in concurrent programming control, Comm. of ACM 8 (1965) 569.
• [5] FISHER, M.J., LYNCH, N.A., MERRITT, A.: Easy impossibility proofs for distributed consensus problems, in: Distributed Computing 1 (1986) 26-29.
• [6] GODARD, E.:(Ph.D. dissertation) A characterization of families of graphs in which election is possible, in: Proc. of Foundations of Software Sci. and Comp. Structures, LNCS 2303 (2002) 159-171.
• [7] GODARD, E., M´ETIVIER, 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.
• [8] LE LANN, G.: Distributed systems – towards a formal approach, in: Information Processing 77 (IFIP), Gilchrist B., (editor), North-Holland (Amsterdam), (1977) 155-160.
• [9] LITOVSKY, I., M´E TIVIER, Y., SOPENA, 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) 1- 56.
• [10] LITOVSKY, I., M´ETIVIER, Y., ZIELONKA, W.: On the recognition of families of graphs with local computations, in: Information & Computation 118 (1995) 110-119.
• [11] MAZURKIEWICZ, A.: Solvability of the asynchronous ranking problem, in: Inf. Processing Letters 28 (1988) 221-224.
• [12] MAZURKIEWICZ, A.: Distributed enumeration, in: Inf. Processing Letters 61 (1997) 233-239.
• [13] MAZURKIEWICZ, A.: Locally Computable enumerations, in: Proc. of XI Intern. Symposium FCT’97, Lecture Notes in Computer Science 1279 (1997) 51-66.
• [14] MAZURKIEWICZ, A.: Bilateral Ranking Negotiations, (Proc. of CS&P’03) Fundamenta Informaticae 60 (2004) 1-16.