Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions

详细信息    查看全文

• 作者：Yuda Zhao ; Haifeng Yu ; Binbin Chen
• 关键词：Communication complexity ; Time complexity ; Communication ; time tradeoff ; Fault tolerance ; Aggregate functions
• 刊名：Distributed Computing
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：29
• 期：1
• 页码：17-38
• 全文大小：771 KB
• 参考文献：1.Bawa, M., Gionis, A., Garcia-Molina, H., Motwani, R.: The price of validity in dynamic networks. J. Comput. Syst. Sci. 73(3), 245–264 (2007)CrossRef MathSciNet MATH
  2.Blokhuis, A.: On the sperner capacity of the cyclic triangle. J. Algebraic Comb. 2(2), 123–124 (1993)CrossRef MathSciNet MATH
  3.Calderbank, A.R., Frankl, P., Graham, R.L., Li, W.-C.W., Shepp, L.A.: The sperner capacity of linear and nonlinear codes for the cyclic triangle. J. Algebraic Comb. 2(1), 31–48 (1993)CrossRef MathSciNet MATH
  4.Chen, B., Yu, H., Zhao, Y., Gibbons, P.B.: The cost of fault tolerance in multi-party communication complexity. J. ACM 61(3), 19:1–19:64 (2014)
  5.Considine, J., Li, F., Kollios, G., Byers, J.: Approximate aggregation techniques for sensor databases. In: ICDE (March 2004)
  6.Frederickson, G.: Tradeoffs for selection in distributed networks. In: PODC (1983)
  7.Impagliazzo, R., Williams, R.: Communication complexity with synchronized clocks. In: CCC (June 2010)
  8.Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: FOCS (October 2003)
  9.Kuhn, F., Locher, T., Wattenhofer. R.: Tight bounds for distributed selection. In: SPAA (2007)
  10.Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic graphs. In: STOC (2010)
  11.Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1996)CrossRef
  12.Madden, S., Franklin, M., Hellerstein, J., Hong, W.: Tag: a tiny aggregation service for ad-hoc sensor networks. In: OSDI (December 2002)
  13.Mosk-Aoyama, D., Shah, D.: Computing separable functions via gossip. In: PODC (July 2006)
  14.Nath, S., Gibbons, P.B., Seshany, S., Anderson, Z.: Synopsis diffusion for robust aggregation in sensor networks. ACM Trans. Sens. Netw. 4(2), 7:1–7:40 (2008)
  15.Newman, I.: Private versus common random bits in communication complexity. Inform. Process. Lett. 39(2), 67–71 (1991)CrossRef MathSciNet MATH
  16.Patt-Shamir, B.: A note on efficient aggregate queries in sensor networks. In: PODC (2004)
  17.Shrira, L., Francez, N., and Rodeh, M.: Distributed k-selection: from a sequential to a distributed algorithm. In: PODC (1983)
  
• 作者单位：Yuda Zhao (1)
  Haifeng Yu (1)
  Binbin Chen (2)
  
  1. School of Computing, National University of Singapore, Computing 1, 13 Computing Drive, Singapore, 117417, Republic of Singapore
  2. Advanced Digital Sciences Center, 1 Fusionopolis Way, #08-10 Connexis North Tower, Singapore, 138632, Republic of Singapore
  
• 刊物类别：Computer Science
• 刊物主题：Computer Communication Networks
  Computer Hardware
  Computer Systems Organization and Communication Networks
  Software Engineering, Programming and Operating Systems
  Theory of Computation
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1432-0452

文摘

This paper considers the problem of computing general commutative and associative aggregate functions (such as Sum) over distributed inputs held by nodes in a distributed system, while tolerating failures. Specifically, there are N nodes in the system, and the topology among them is modeled as a general undirected graph. Whenever a node sends a message, the message is received by all of its neighbors in the graph. Each node has an input, and the goal is for a special root node (e.g., the base station in wireless sensor networks or the gateway node in wireless ad hoc networks) to learn a certain commutative and associate aggregate of all these inputs. All nodes in the system except the root node may experience crash failures, with the total number of edges incidental to failed nodes being upper bounded by f. The timing model is synchronous where protocols proceed in rounds. Within such a context, we focus on the following question: Under any given constraint on time complexity, what is the lowest communication complexity, in terms of the number of bits sent (i.e., locally broadcast) by each node, needed for computing general commutative and associate aggregate functions? This work, for the first time, reduces the gap between the upper bound and the lower bound for the above question from polynomial to polylog. To achieve this reduction, we present significant improvements over both the existing upper bounds and the existing lower bounds on the problem.