Abstract
This paper considers the broadcast/receive communication model in which message collisions and message conflicts can occur because processes share frequency bands. (A collision occurs when, during the same round, messages are sent to the same process by too many neighbors. A conflict occurs when a process and one of its neighbors broadcast during the same round.) More precisely, the paper considers the case where, during a round, a process may either broadcast a message to its neighbors or receive a message from at most m of them. This captures communication-related constraints or a local memory constraint stating that, whatever the number of neighbors of a process, its local memory allows it to receive and store at most m messages during each round. The paper defines first the corresponding generic vertex multi-coloring problem (a vertex can have several colors). It focuses then on tree networks, for which it presents a lower bound on the number of colors K that are necessary (namely, \(K=\lceil \frac{\varDelta }{m}\rceil +1\), where \(\varDelta \) is the maximal degree of the communication graph), and an associated coloring algorithm, which is optimal with respect to K.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
\(\log ^* n\) is the number of times the function \(\log \) needs to be iteratively applied in \(\log (\log (\log ( ...(\log n))))\) to obtain a value \(\le 2\). As an example, if n is the number of atoms in the universe, \(\log ^* n \backsimeq 5\).
- 3.
Some initial asymmetry is necessary to solve breaking symmetry problems with a deterministic algorithm.
- 4.
Depending on the underlying hardware (e.g., multi-frequency bandwidth, duplexer, diplexer), variants of this broadcast/receive communication pattern can be envisaged. The algorithms presented in this paper can be modified to take them into account.
- 5.
As we will see, conflicts are prevented by the message exchange pattern imposed by the algorithm.
- 6.
Differently from a set, a multiset (also called a a bag), can contain several times the same element. Hence, while \(\{a,b,c\}\) and \(\{a,b,a,c,c,c\}\) are the same set, they are different multisets.
- 7.
This is because (a) distance-2 coloring ensures that any vertex and its neighbors have different colors, and (b) there are at most m colors \(c_1,...,c_x \in [0.. (K*m)-1]\) (hence \(x\le m\)), such that \((c_1 \mathsf{~mod~} K) = \cdots = (c_x \mathsf{~mod~} K) =c \in [0..(K-1)]\).
References
Angluin, D.: Local and global properties in networks of processors. In: Proceedings of 12th ACM Symposium on Theory of Computation (STOC 1981), pp. 82–93. ACM Press (1981)
Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley-Interscience, Hoboken (2004)
Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. J. ACM 58(5), 23 (2011)
Barenboim, L., Elkin, M.: Distributed Gaph Coloring, Fundamental and Recent Developments, p. 155. Morgan & Claypool Publishers (2014)
Barenboim, L., Elkin, M., Kuhn, F.: Distributed (Delta+1)-coloring in linear (in Delta) time. SIAM J. Comput. 43(1), 72–95 (2014)
Blair, J., Manne, F.: An efficient self-stabilizing distance-2 coloring algorithm. In: Kutten, S., Žerovnik, J. (eds.) SIROCCO 2009. LNCS, vol. 5869, pp. 237–251. Springer, Heidelberg (2010). doi:10.1007/978-3-642-11476-2_19
Bozdağ, D., Catalyurek, U., Gebremedhin, A.H., Manne, F., Boman, E.G., Özgüner, F.: A parallel distance-2 graph coloring algorithm for distributed memory computers. In: Yang, L.T., Rana, O.F., Martino, B., Dongarra, J. (eds.) HPCC 2005. LNCS, vol. 3726, pp. 796–806. Springer, Heidelberg (2005). doi:10.1007/11557654_90
Bozdag, D., Gebremedhin, A.S., Manne, F., Boman, G., Çatalyürek, U.V.: A framework for scalable greedy coloring on distributed-memory parallel computers. J. Parallel Distrib. Comput. 68(4), 515–535 (2008)
Chipara, O., Lu, C., Stankovic, J., Roman, G.-C.: Dynamic conflict-free transmission scheduling for sensor network queries. IEEE Trans. Mobile Comput. 10(5), 734–748 (2011)
Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32–53 (1986)
Frey, D., Lakhlef, H., Raynal, M.: Optimal collision/conflict-free distance-2 coloring in synchronous broadcast/receive tree networks. Research Report (2015). https://hal.inria.fr/hal-01248428
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)
Gebremedhin, A.H., Manne, F., Pothen, A.: Parallel distance-k coloring algorithms for numerical optimization. In: Monien, B., Feldmann, R. (eds.) Euro-Par 2002. LNCS, vol. 2400, pp. 912–921. Springer, Heidelberg (2002). doi:10.1007/3-540-45706-2_130
Goldberg, A., Plotkin, S., Shannon, G.: Parallel symmetry-breaking in sparse graphs. SIAM J. Disc. Math. 1(4), 434–446 (1988)
Herman, T., Tixeuil, S.: A sistributed TDMA slot assignment algorithm for wireless sensor networks. In: Nikoletseas, S.E., Rolim, J.D.P. (eds.) ALGOSENSORS 2004. LNCS, vol. 3121, pp. 45–58. Springer, Heidelberg (2004). doi:10.1007/978-3-540-27820-7_6
Hugh, H.H., Molloy, M., Reed, B.: Colouring a graph frugally. Combinatorica 17(4), 469–482 (1997)
Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings of 25th ACM Symposium Principles of Distributed Computing (PODC 2006), pp. 7–15. ACM Press (2006)
Lakhlef, H., Raynal, M., Taïani, F.: Vertex coloring with communication and local memory constraints in synchronous broadcast networks. Tech report 2035, p. 24. IRISA, Université de Rennes (F) (2016). https://hal.inria.fr/hal-01300095
Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1996)
Molloy, M., Bruce, R.B.: Asymptotically optimal frugal colouring. J. Comb. Theory Ser. B 100(2), 247–249 (2010). Corrigendum in J. Comb. Theory Ser. B 100(2), 226–246 (2010)
Peleg, D.: Distributed Computing, A Locally Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications, p. 343 (2000). ISBN 0-89871-464-8
Raynal, M.: Fault-Tolerant Agreement in Synchronous Message-Passing Systems, p. 165. Morgan & Claypool Publishers (2010). ISBN 978-1-60845-525-6
Raynal, M.: Distributed Algorithms for Message-Passing Systems. Springer, Heidelberg (2013). ISBN 978-3-642-38122-5
Acknowledgments
This work has been partially supported by the Franco-German DFG-ANR Project 40300781 DISCMAT (devoted to connections between mathematics and distributed computing), and the Franco-Hong Kong ANR-RGC Joint Research Programme 12-IS02-004-02 CO2Dim.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Lakhlef, H., Raynal, M., Taïani, F. (2017). Vertex Coloring with Communication and Local Memory Constraints in Synchronous Broadcast Networks. In: Chrobak, M., Fernández Anta, A., Gąsieniec, L., Klasing, R. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2016. Lecture Notes in Computer Science(), vol 10050. Springer, Cham. https://doi.org/10.1007/978-3-319-53058-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-53058-1_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53057-4
Online ISBN: 978-3-319-53058-1
eBook Packages: Computer ScienceComputer Science (R0)