, In mini-slot i 2 (Figure 16(c)), according to Case (1), us describe the two mini-slots for the oriented grid depicted in Figure 16. Here we suppose that at the beginning of mini-slot i, all the arcs are undetermined and five of them satisfy ? t,e (i) = 1 namely, vol.16

, There decisions are the following:-Case a: if in mini-slot i 1 node u hears a signal, then:-it changes the state of the arcs f with origin u such that s( f ) = U and ? t ( f , i) = 0 from U to PI, According to what happens in mini-slots i 1 and i 2 , the nodes take decisions which exactly emulate the decisions taken in the link model (lines 7-10)

C. , heard a signal from any of its neighbors, but has sent signals to at least two of its neighbors then:-it changes the state of the arcs f with origin u such that s( f ) = U and ? t ( f , i) = 0 from U to PI.-it leaves the state of the arcs f with origin u such that s( f ) = U, mini-slot i 1 node u has not

, Case c: if in mini-slot i 1 node u has not heard a signal from any of its neighbors and has sent a signal only to node v, then:-u changes the state of all the arcs f different than (u, v) with origin u which necessarily satisfy s( f ) = U

, u, v) at U.-Case d: if in mini-slot i 1 node u has not sent a signal and has not heard a signal from any of its neighbors, then-if in mini-slot i 2 node u hears a signal sent by node w and if arc f = (u, w) satisfies s( f ) = U (necessarily ? t ( f , i) = 0, mini-slot i 2 node u hears a signal sent by node v it leaves the state of arc e =

, mini-slot i 2 node u has not heard a signal from node w and if arc f = (u, w) satisfies s( f ) = U (necessarily ? t ( f , i) = 0)

, In the proof, we describe the decisions taken by the nodes after the two mini-slots, for the oriented grid depicted in Figure 16. 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). The four cases correspond to arcs labeled case x ? {a, b, c, Proposition 4 proves the equivalence between AlgoLog and AlgoLogNodes

, Proposition 4 Under the primary node interference model, decisions taken by AlgoLogNodes after the two mini-slots i 1 and i 2 emulate the decisions taken by AlgoLog after mini-slot i, pp.7-10

, Throughout the proof, we focus on mini-slot i = 1,. .. , T , of slot t. Recall that under AlgoLogNodes mini-slot i is composed of the two (sub-) mini-slots i 1 and i 2

, e (i) = 1 then v has sent a signal in mini-slot i 1 and, from Case (1), in mini-slot i 2 , v has sent a signal to u so that, from Case (c), u leaves e undetermined, First, consider an arc e = (u, v) such that s(e) = U and ? t,e (i) = 1. Under AlgoLog, e sends a signal in the mini-slot i and from there two things may happen: (i) hears a signal from w and

, When (ii) occurs, we are in Case (c) above and u changes the state of e from U to A

. Second, ) such that s( f ) = U and ? t, f (i) = 0. In AlgoLog, f does not send any signal in the mini-slot i and from there two things may happen: (i') f hears a signal from an arc f in I( f ) and it changes its state from U to PI or (ii') f does not hear any signal and its state remains in U

, When (i') occurs, we need to investigate four cases according to the origin or destination of f (i.e. either f has destination/origin u or w):-If there is an arc f = (w , u) with destination u satisfying s( f ) = U and ? t, f (i) = 1, then u hears in mini-slot i 1 a signal from w and so by Case

F. Baccelli, B. B?aszczyszyn, ;. Balakrishnan, C. L. Barrett, V. S. Kumar et al., The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks, Graphs and Algorithms in Communication Networks, Studies in Broadband, Optical, Wireless and Ad Hoc Networks, vol.II, pp.357-377, 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

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.

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.

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.

F. G. Foster, On the stochastic matrices associated with certain queuing processes, Ann. Math. Statistics, vol.24, pp.355-360, 1953.

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

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

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.

. Fig, Two mini-slots of AlgoLogNodes (that emulates AlgoLog) for an oriented grid network, vol.16

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.

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

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

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. P. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability, 1993.

Y. Orlovich, G. Finke, V. Gordon, and I. Zverovich, Approximability results for the maximum and minimum maximal induced matching problems, Discrete Optimization, vol.5, issue.3, pp.584-593, 2008.

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.

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

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

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.

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.

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

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.

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.