, node u has to know if there is another arc e sending and interfering with e. Notice that, necessarily, node u knows if arc e = (u, v ) is sending. However, u does not know if there are other arcs interfering with it. Therefore, order to apply Algolog at the node level, and similarly to decide if an arc e = (u, v) not sending becomes PI (potentially inactive) or stays U)

, On the other hand, if u hears a signal from some node w, then it needs to determine whether or not a signal is aimed to it. From now on, we assume (Hypothesis H) that if

, We now show how, under H, one can emulate, in the primary node model, a mini-slot i of sending on the arc e = (u, v) by dividing it in two sub-mini-slots, denoted by i 1 and i 2 , that is how one can emulate the behavior of lines 5-6 of AlgoLog. As a result, the overhead will only be multiplied by two. During sub-mini-slot i 1

, Sub-mini-slot i 1 : For each arc e = (u, v) such that s(e) = U and ? t,e (i) = 1, then node u sends a signal in the direction of node v

, Within the sub-mini-slot i 1 , if node u detects a signal from some node w, then it knows that arc e = (w, u) is sending and, therefore, interfering with all the arcs with origin u. It remains to deal with interference of an arc e = (u, v) with some arc e due to node v, that is Problem 2. To answer the problem we design sub-mini-slot i 2 as follows: Sub-mini-slot i 2 : ? Case 1: If in sub-mini-slot i 1 node v has sent a signal

, ? Case 2: If in sub-mini-slot i 1 node v has not sent a signal, but has heard a signal from at least two of its neighbors, then v sends a signal (busy) to all of its neighbors

?. Case, If in sub-mini-slot i 1 node v has not sent any signal and has heard a signal from exactly one of its neighbors (say node u), then v sends a signal (busy) to all of its neighbors, vol.3

, Emulating lines 7-10 of AlgoLog After the two sub-mini-slots i 1 and i 2 , a node u can determine for each arc e = (u, v) if there is an arc sending and interfering with e. That happens exactly in the following three cases: ? Case a: In sub-mini-slot i 1

, ? Case b: In sub-mini-slot i 1 , node u hears a signal from some node w

, ? Case c: In sub-mini-slot i 2 , node u hears a signal (busy) from node v

, and in Case c e = (v, w) if the signal busy was sent in sub-mini-slot i 2 due to Case 1 or e = (w, v) if the signal busy was sent in sub-mini-slot i 2 due to Case 2 or Case 3. Furthermore, if we are not in one of Cases 1-3, then there is no arc interfering with e. Depending on what happens in sub-mini-slots i 1 and i 2 , a node u can know when there is an interference between an arc e = (u, v) and another arc e , so that it is able to make decisions which exactly emulate decisions taken in the link model (cf. lines 7-10 in Figure 2). More precisely, these three cases there is an arc e sending and interfering with e = (u, v), namely

, ? if e is not sending (i.e. ? t (f, i) = 0) and if there is an arc e sending and interfering with e

, ) and, so, are sending. In sub-mini-slot i 1 (Figure 16(b)), u 1 sends a signal to u 2, As an illustration of the above, consider the oriented grid displayed in Figure 16. Here, we assume that at the beginning of sub-mini-slot i, all the arcs are undetermined and five of them satisfy ? t,e (i) = 1 namely

, The state of an arc is represented by a dash line for PI (Potentially Inactive), a solid line for U (Undetermined), and Blue bold for A (Active). For each arc e = (u, v), the label 'case x' with x ? {a, b, c}

, Therefore, node u 1 changes the state of the arc (u 1 , u 4 ) from U to P I. For the arc (u 1 , u 2 ), there is no arc sending and interfering with it. Therefore, node u 1 changes the state of the arc (u 1 , u 2 ) from U to A. Consider node u 2 . In sub mini-slot i 1 , it hears a signal from u 1 and so it knows, p.33

, This node hears a signal from u 2 in sub-mini-slot i 2 (Case 3 as u 2 heard in sub-min-slot i 1 a signal from u 1 ). Therefore, by Case c, u 3 knows that there is a sending arc

, Emulating lines 11-16 of AlgoLog We can also emulate the synchronization slot (lines 11-12 of AlgoLog in Figure 2) with two submini-slots identical to the sub-mini-slots i 1 and i 2 . Each node u will know, exactly as above, for an arc e if there is an arc e sending and interfering with it (Cases a,b,c) and, therefore

, ) is active) sends a signal of synchronization to u 2 . Then, in the second sub-mini-slot of synchronization, u 1 sends a signal busy (Case 1) and u 2 sends a signal busy

, ) from P I to I, and u 4 will change the state of (u 4 , u 1 ) from P I to I as for these two arcs there is an interference with

F. Baccelli and B. Laszczyszyn, Stochastic Geometry and Wireless Networks, vol.II, 2010.
URL : https://hal.archives-ouvertes.fr/inria-00403039

H. Balakrishnan, C. L. Barrett, V. S. Kumar, M. V. Marathe, and S. Thite, The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks, J. Selected Areas in Communication, vol.22, issue.6, pp.1069-1079, 2004.

J. Bermond, D. Mazauric, V. Misra, and P. Nain, A distributed scheduling algorithm for wireless networks with constant overhead and arbitrary binary interference, ACM SIGMETRICS Performance Evaluation Review, vol.38, pp.345-346, 2010.
URL : https://hal.archives-ouvertes.fr/inria-00505519

V. Bonifaci, R. Klasing, P. Korteweg, L. Stougie, and A. Marchetti-spaccamela, Data gathering in wireless networks, Graphs and Algorithms in Communication Networks, Studies in Broadband, Optical, Wireless and Ad Hoc Networks, pp.357-377, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00342958

P. Brémaud, Markov Chains, Gibbs Fields, Monte Carlo Simulation, and Queues, Texts in Applied Mathematics, vol.31, 1999.

A. Brzezinski, G. Zussman, and E. Modiano, Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach, Proc. ACM MobiCom, pp.26-37, 2006.

L. X. Bui, S. Sanghavi, and R. Srikant, Distributed link scheduling with constant overhead, IEEE/ACM Transactions on Networking, vol.17, issue.5, pp.1467-1480, 2009.

K. Cameron, Induced matchings, Discrete Applied Mathematics, vol.24, issue.1-3, pp.97-102, 1989.

P. Chaporkar, K. Kar, X. Luo, and S. Sarkar, Throughput and fairness guarantees through maximal scheduling in wireless networks, IEEE Transactions on Information Theory, vol.54, issue.2, pp.572-594, 2008.

H. Chen, X. Xie, and H. Wu, A queue-aware scheduling algorithm for multihop relay wireless cellular networks, Proc. IEEE Mobile WiMAX Symposium, pp.63-68, 2009.

R. Diestel, Graph Theory (Graduate Texts in Mathematics, 1997.

A. Eryilmaz, O. Asuman, and E. Modiano, Polynomial complexity algorithms for full utilization of multi-hop wireless networks, Proc. IEEE INFOCOM, pp.499-507, 2007.

S. Fiorini and R. J. Wilson, Edge-colourings of graphs, Research Notes in Mathematics, vol.16, 1977.

A. Gupta, X. Lin, and R. Srikant, Low-complexity distributed scheduling algorithms for wireless networks, IEEE/ACM Transactions on Networking, vol.17, issue.6, pp.1846-1859, 2009.

P. Gupta and P. R. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory, vol.46, issue.2, pp.388-404, 2000.

L. Jiang, D. Shah, J. Shin, and J. Walrand, Distributed random access algorithm: scheduling and congestion control, IEEE Transactions on Information Theory, vol.56, issue.12, pp.6182-6207, 2010.

L. Jiang and J. Walrand, A distributed CSMA algorithm for throughput and utility maximization in a wireless networks, Proc. 46th Allerton Conference on Communication, Control, and Computing, 2008.

L. Jiang and J. Walrand, Approaching throughput-optimality in distributed CSMA scheduling algorithms with collisions, IEEE/ACM Transactions on Networking, vol.19, issue.3, pp.816-829, 2011.

R. Klasing, N. Morales, and S. Pérennes, On the complexity of bandwidth allocation in radio networks, Theoretical Computer Science, vol.406, issue.3, pp.225-239, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00342875

V. S. Kumar, M. Marathe, S. Parthasarathy, and A. Srinivasan, End-to-end packet-scheduling in wireless ad-hoc networks, Proc. ACM-SIAM SODA, pp.1021-1030, 2004.

L. Lovász and M. D. Plummer, Matching Theory, Annals of Discrete Mathematics, vol.29, 1986.

R. Mazumdar, G. Sharma, and N. Shroff, Maximum weighted matching with interference constraints, Proc. FAWN, 2006.

S. P. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability, 1993.

J. Misra and D. Gries, A constructive proof of vizing's theorem, Information Processing Letters, p.41, 1992.

E. Modiano, D. Shah, and G. Zussman, Maximizing throughput in wireless networks via gossiping, Proc. ACM SIGMETRICS -IFIP PERFORMANCE, vol.34, pp.27-38, 2006.

S. Rajagopalan, D. Shah, and J. Shin, Network adiabatic theorem: an efficient randomized protocol for contention resolution, Proc. ACM SIGMETRICS -IFIP PERFORMANCE, vol.37, pp.133-144, 2009.

S. Sanghavi, L. Bui, and R. Srikant, Distributed link scheduling with constant overhead, Proc. ACM SIGMETRICS, pp.313-324, 2007.

D. Shad and D. Wischik, Log-weight scheduling in switched networks, Queueing Systems (QUESTA), vol.71, pp.97-136, 2012.

D. Shah and J. Shin, Randomized scheduling algorithm for queueing networks, Ann. Appl. Probab, vol.22, issue.1, pp.128-171, 2012.

D. Shah, J. Shin, and P. Tetali, Medium access using queues, Proc. IEEE 52nd Annual Symposium on Foundations of Computer Sciences (FOCS), 2011.

D. Shah and D. Wischik, Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse, Ann. Appl. Probab, vol.22, issue.1, pp.70-127, 2012.

H. Shokri-ghadikolaei, C. Fischione, and E. Modiano, On the accuracy of interference models in wireless communications, ICC 2016, IEEE international Conference on Communications, pp.1-6, 2016.

H. Shokri-ghadikolaei, C. Fischione, and E. Modiano, Interference model similarity index and its applications to mmwave networks: Extended version, IEEE Transactions on Wireless Communications, vol.10, p.2017

F. Simatos, N. Bouman, and S. Borst, Lingering issues in distributed scheduling, Proceedings of the ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '13, pp.141-152, 2013.
URL : https://hal.archives-ouvertes.fr/hal-01888052

L. J. Stockmeyer and V. V. Vazirani, NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters, vol.15, issue.1, pp.14-19, 1982.

L. Tassiulas, Scheduling and performance limits of networks with constantly changing topology, IEEE Transactions on Information Theory, vol.43, issue.3, pp.1067-1073, 1997.

L. Tassiulas and A. Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks, IEEE Transactions on Automatic Control, vol.37, issue.12, 1992.

P. Wan, Multiflows in multihop wireless networks, Proc. ACM MobiHoc, pp.85-94, 2009.

X. Wu, R. Srikant, and J. R. Perkins, Queue length stability of maximal greeedy schedules in wireless networks, Proc. of Information Theory and Applications Inaugural Workshop, 2006.