## 4 Implementation and Running Time  
If the reader is not interested in implementation details and having truly linear time algorithms, it is advised to skip this section. The original Algorithm GS is thought to be a linear time local algorithm by its definition, but that is not obvious at all, as when getting a proposal from a man \(m\), a woman \(w\) must look up in some dictionary, what is the value of \(\mathrm{pri}(w,m)\). In order to implement Algorithm GS as a linear time local algorithm, we first assume that the lists of men are sorted (this assumption can be weakened to requiring that the priorities are natural numbers not exceeding the length of the list, because in this case a mancan do bucket (or counting) sort in linear time), and moreover we have to make **any** one of following assumptions. * The system is \"wired\" along acceptable pairs, which means here that when a man \(m\) sends a proposal to a woman \(w\), she sees on which wire this call is coming in, and the priority \(\mathrm{pri}(m,w)\) is written on that wire. Or, equivalently, better fitting to our mobile phone centralized world, there are no wires, but when an accessible man \(m\) calls woman \(w\), then not only his phone number (his index in \(U\)) is shown, but also his position in the phone-book of \(w\), such that his index in \(w\)'s array. * Women can throw dice, and so they can use the perfect hashing approach of [21]. * Women has a black-box procedure, which on input \(m\) outputs in constant time \(\mathrm{pri}(w,m)\). * Men has some extra knowledge, for each acceptable woman \(w\) they know their own position in the list of \(w\), such as their index in \(w\)'s array. _Remark. [PERSON] and [PERSON] in [22] made a stronger assumption, the existence of ranking arrays. For complete preference lists it is still equivalent to the above assumptions._  
Here we may assume any of these assumptions, but we will concentrate (and use) the fourth one, because that fits the best in our description of the algorithm. To make the new algorithm linear time and local, we must define the communication between acceptable pairs, as well as the data structure needed for the participants. In our local implementation of the new algorithm all men run the same algorithm, as well as all women. First we describe the algorithm of an arbitrary woman \(w\). She stores \(3\) non-changing arrays, her own status (maiden or engaged), and if she is engaged then she also stores the name, priority and status of her fiance. The first array \(U_{w}\) contains all the acceptable men in arbitrary order of priorities. The second array \(PR_{w}\) contains the corresponding priorities at \(w\). The third array \(I_{w}\) stores the relative positions, such that if \(w\) is in the \(i\)th position in the list of man \(U_{w}(j)\) then \(I_{w}(j)=i\) (this list is initialized at the beginning with accepting messages from men). Woman \(w\) gets proposals in the form \((m,i,\text{status}(m))\), where \(\text{status}(m)\) can be one of lad or bachelor, and \(i\) is the index in \(w\)'s array \(U_{w}\) where she stores \(m\). If \(w\) is maiden and gets a proposal from man \(m\) then she changes her status to engaged, she stores \((m,\mathrm{pri}(w,m),\text{status}(m))\), and she tells all the men in her list about her new status (engaged), together with her index stored in \(I_{w}\). If she later gets a proposal from man \(m^{\prime}\) then she first asks his fiance \(m\), whether he is uncertain. Now she has all the information needed to make a decision, she stores the name, priority and status of the new fiance, and she sends the message \"rejected\" to the non-preferred man. An algorithm of a man \(m\) is slightly more complicated due to continuous reordering needed in his list, and the fact that he must always know whether he is uncertain.