Skip to main content
SpringerLink
Log in

Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We study, from the perspective of competitive analysis, the trade-off between communication cost and delay cost, or simply the send-or-wait dilemma on a hierarchical rooted tree. The problem is an abstraction of the message aggregation problem on communication networks and an organizational problem in network hierarchies.

We consider the most natural variant of the problem, the distributed asynchronous regime, and give tight (within a small additive constant) upper and lower bounds on the competitive ratio of the optimization problem. We also consider the centralized version of the problem, in which there is a central entity which remains updated about any incoming messages to the network and which can control the internal delivery of messages in the network. For the centralized setting, we combine a natural rent-to-buy strategy with prediction techniques to achieve the first constant competitive ratio algorithm for any non-trivial class of network topologies.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Khanna, S., Naor, J., Raz, D.: Control message aggregation in group communication protocols. In: International Colloquium on Automata Languages and Programming, pp. 135–146 (2002)

    Chapter  Google Scholar 

  2. Papadimitriou, C.H., Servan-Schreiber, E.: The origins of the deadline: Optimizing communication in organizations. Presented at Complexity in Economics, 1999

  3. Servan-Schreiber, E.: Communication in hierarchies: explaining deadlines. Ph.D. Thesis, University of California Berkeley, ISBN 0-493-11342-8 (2000)

  4. Dooly, D.R., Goldman, S.A., Scott, S.D.: On-line analysis of the TCP acknowledgment delay problem. J. ACM 48, 243–273 (2001)

    Article  MathSciNet  Google Scholar 

  5. Bortnikov, E., Cohen, R.: Schemes for scheduling of control messages by hierarchical protocols. In: Conference on Computer Communications (INFOCOM), vol. 2, pp. 865–872 (1998)

    Google Scholar 

  6. Papadimitriou, C.: Computational aspects of organizational theory. In: European Symposium on Algorithms, pp. 559–564 (1996)

    Google Scholar 

  7. Karlin, A.R., Kenyon, C., Randall, D.: Dynamic TCP acknowledgment and other stories about e/(e−1). Algorithmica 36(3), 209–224 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  8. Badrinath, B.R., Sudame, P.: Gathercast: the design and implementation of a programmable aggregation for the Internet. In: Computer Communications and Networks, pp. 206–213 (2000)

    Google Scholar 

  9. Vaya, S.: Deliver-or-delay dilemma in organization networks. Manuscript (2011)

Download references

Author information

Authors and Affiliations

  1. Departamento de Computação, Universidade Federal do Ceará, Fortaleza, Brazil

    Carlos Fisch Brito

  2. Department of Computer Science, University of Athens Panepistimiopolis, Ilissia Athens, 15784, Greece

    Elias Koutsoupias

  3. Department of Computer Science and Engineering, Indian Institute of Technology, Patna, 800013, India

    Shailesh Vaya

Authors
  1. Carlos Fisch Brito
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Elias Koutsoupias
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shailesh Vaya
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shailesh Vaya.

Additional information

Most of the research in this work was conducted while the authors were at UCLA.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brito, C.F., Koutsoupias, E. & Vaya, S. Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?. Algorithmica 64, 584–605 (2012). https://doi.org/10.1007/s00453-011-9567-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-011-9567-5

Keywords

Search

Navigation