Skip to main content
SpringerLink
Log in

Allowing each node to communicate only once in a distributed system: shared whiteboard models

  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed way. When computing graph-theoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems. We exhibit problems that separate these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model.

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

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Babai, L., Gál, A., Kimmel, P.G., Lokam, S.V.: Communication complexity of simultaneous messages. SIAM J. Comput. 33, 137–166 (2004)

  2. Becker, F., Matamala, M., Nisse, N., Rapaport, I., Suchan, K., Todinca, I.: Adding a referee to an interconnection network: What can(not) be computed in one round. In: Parallel and Distributed Processing Symposium, International, pp. 508–514. IEEE Computer Society (2011)

  3. Chandra, A.K., Furst, M.L., Lipton, R.J.: Multi-party protocols. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, STOC ’83, pp. 94–99. ACM (1983)

  4. Feldman, J., Muthukrishnan, S.M., Sidiropoulos, A., Stein, C., Svitkina, Z.: On distributing symmetric streaming computations. ACM Trans. Algorithms 6, 66:1–66:19 (2010)

    Article  MathSciNet  Google Scholar 

  5. Fraigniaud, P., Korman, A., Peleg, D.: Towards a complexity theory for local distributed computing. J. ACM 60(5), 35 (2013)

    Article  MathSciNet  Google Scholar 

  6. Grumbach, S., Wu, Z.: Logical locality entails frugal distributed computation over graphs. In: Proceedings of 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science, 5911, pp. 154–165 (2009)

  7. Kostochka, A.V.: Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica 4(4), 307–316 (1984)

  8. Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 300–309. ACM (2004)

  9. Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  10. Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259–1277 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  11. Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM Monographs on Discrete Mathematics and Applications (2000)

  12. Thomason, A.: An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc. 95, 261–265 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  13. Thomason, A.: The extremal function for complete minors. J. Comb. Theory. Ser. B 81(2), 318–338 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  14. Wright, E.: Equal sums of like powers. Bull. Amer. Math. Soc. 8, 755–757 (1948)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIFO, Université d’Orléans, Orléans, France

    Florent Becker & Ioan Todinca

  2. Inria Paris - LIAFA, Université Paris Diderot, Paris, France

    Adrian Kosowski

  3. DIM-CMM (UMI 2807 CNRS), Universidad de Chile, Santiago, Chile

    Martin Matamala & Ivan Rapaport

  4. CNRS, I3S, Sophia-Antipolis, Inria & Univ. Nice Sophia-Antipolis, Nice, France

    Nicolas Nisse

  5. Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Santiago, Chile

    Karol Suchan

  6. Faculty of Applied Mathematics, AGH - University of Science and Technology, Kraków, Poland

    Karol Suchan

Authors
  1. Florent Becker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Adrian Kosowski
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Martin Matamala
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Nicolas Nisse
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ivan Rapaport
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Karol Suchan
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Ioan Todinca
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Martin Matamala.

Additional information

This paper is the union of two preliminary versions appeared in the proceedings of SPAA 2012 (Allowing each node to communicate only once in a distributed system: shared whiteboard models) and IPDPS 2011 (Adding a referee to an interconnection network: What can (not) be computed in one round?). It has been partially supported by programs Fondap and Basal-CMM (M.M., I.R., K.S.), Fondecyt 1100192 (M.M.), 1130061 (I.R.), FP7 STREP EULER (N.N.), ANR AGAPE (I.T.), ANR Displexity (A.K.), NCN under contract DEC-2011/02/A/ST6/00201 (A.K.), Ecos-Conicyt C09E04 (M.M., I.R., I.T.), Ecos-Sud Chili C12E03 (N.N, K.S.) and Associated Team Inria AlDyNet (N.N, K.S.).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Becker, F., Kosowski, A., Matamala, M. et al. Allowing each node to communicate only once in a distributed system: shared whiteboard models. Distrib. Comput. 28, 189–200 (2015). https://doi.org/10.1007/s00446-014-0221-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-014-0221-8

Keywords

Search

Navigation