On the complexity of global computation in the presence of link failures: the general case
Tóm tắt
This paper presents Ω(m logn) and Ω(mn) messages lower bounds on the problem of computing a gobal sensitive function in biderectional networks with link failures (i.e., dynamically changing topology), wheren andm are the total number of nodes and links in the network. The Ω(m logn) lower bound is under the assumption thatn is a-priori known to the nodes, while the second bound is for the case in which such knowledge is not available. A global sensitive function ofn variables is a function that may not be computed without the knowledge of the values of all then variables (e.g. maximum, sum, etc). Thus, computing such a function at one node of a distributed network requires this node to communicate with every other node in the network. Though lower bounds higher than Ω(m) messages are known for this problem in the context of link failures, none holds for dense bidirectional networks. Moreover, we are not aware of any other nontrivial lower bound higher than Ω(m) for dense bidirectional networks.
Tài liệu tham khảo
Frederickson GN, Lynch NA: Electing a leader in a synchronous ring. ACM 34(1): 98–115 (1987)
Pach J, Korach E, Rotem D: A technique for proving lower bounds for distributed maximum-finding algorithms. In: Proc of the 14th Annu ACM Symp on Theory of Computing, pp 378–382, 1982
Frederickson GN, Lynch NA: A general lower bound for electing a leader in a ring. Tech Rep CSD-TR-512. Purdue University, 1985
Goldreich O, Shrira L: The effect of link failures on computations in asynchronous rings. In: Proc of the ACM Symp on Principles of Distributed Computing, 1986
Linial N: Distributive graph algorithms — global solutions from local data. In: Proc of the 28th IEEE Annu Symp on Foundation of Computer Science, pp 331–335, 1987
Cidon I, Shavitt Y: Message terminate algorithms for rings of unknown size. In: Proc of the 6th Int Workshop on Distributed Algorithms. Lect Notes Comput Sci, vol 647. Springer, Berlin Heidelberg New York 1992, pp 264–276
Goldreich O, Shrira L: Consultation in the presence of faults: two lower bounds. Tech Rep, Technion, 1985
Afek Y, Landau GM, Schieber B, Yung M: The power of multimedia: combining point-to-point and multiaccess networks. Inf Comput 84(1): 97–118 (1990).
Segall A: Distributed network protocols. IEEE Trans Inf Theory, IT-29(1): 23–35 (1983)
Goldreich O, Shrira L: On the complexity of computation in the presence of link failures: the case of a ring. Distrib Comput 5: 121–131 (1991)
Goldreich O, Sneh D: On the complexity of global computation in the presence of link failures: the case of uni-directional faults. In: Proc 11 th ACM Symp on Principles of Distributed Computing, pp 103–111, 1992
Afek Y, Gafni E: End-to-end communication in unreliable networks. In: Proc of the 7th ACM Symp on Principles of Distributed Computing, pp 131–148, 1988
Afek Y, Gafni E: Bootstrap network resynchronization: an efficient technique end-to-end communication. In: Proc of the 10th Annu ACM Symp on Principles of Distributed Computing (PODC), 1991