## 5 An O(1)-Competitive Algorithm
### Potential Function \(\Phi(t)\)
To compute the upper-bound, consider that a lagging job \(j_{i}\) on \(u\) is executed at the rate of \(\left(s_{ua}.\frac{imp_{u}(j_{i})}{\sum_{k~{}=~{}1}^{uu}imp_{u}(j_{k})}\right)\) or \(\left(s_{ua}.\frac{imp_{u}(j_{i})}{imp_{ua}}\right)\), therefore the change in \(\omega_{i}\) is at the rate of \(\left(-s_{ua}.\frac{imp_{u}(j_{i})}{imp_{ua}}\right)\). \(imp_{ua}\geq imp_{gl_{u}}>\eta^{\alpha}\), \(s_{ua}~{}=~{}(1+\
icefrac{{\Delta}}{{3m}})\cdot\eta\)  
\[\frac{d\Phi_{ua}}{dt}=\sum\
olimits_{i~{}=~{}1}^{lg_{u}}\left(\frac{1}{1-\delta }\right)\left(\sum\
olimits_{k~{}=~{}1}^{i}imp_{u}(j_{k})\cdot\eta^{-1}\right) \left(-s_{ua}.\frac{imp_{u}(j_{i})}{imp_{ua}}\right)\]As only one job executes on a processor, therefore \(\frac{imp_{u}(j_{u})}{int_{pu}}\ =\ 1\) and \(lg_{u}\ =\ i\ =\ 1\),  
\[ \begin{array}{ll}\frac{d\Phi_{uu}}{dt}&=\left(\frac{1}{1-\delta}\right)\left( imp_{lg_{u}}\cdot\eta^{-1}\right)\cdot\left(-s_{uu}\right)\\ &=-\left(\frac{1}{1-\delta}\right)\left(s_{uu}\cdot imp_{lg_{u}}\cdot\eta^{-1} \right)\\ &=-\left(\frac{1}{1-\delta}\right)\left(\left(1+\
icefrac{{\Delta}}{{3m}} \right)\cdot\eta\cdot imp_{lg_{u}}\cdot\eta^{-1}\right)\\ &\frac{d\Phi_{uu}}{dt}\ =\ -\frac{\left(1+\
icefrac{{\Delta}}{{3m}} \right)}{\left(1-\delta\right)}\cdot imp_{lg_{u}}\end{array}  \tag{11}\]  
\(\Box\)  
**Lemma 4. **_If \(n_{a}>m\) and \(imp_{lg_{u}}\preceq\eta^{\alpha}\)_  
(a) \(\frac{d\Phi_{uu}}{dt}\leq\frac{s_{uu}\alpha^{\alpha}}{\alpha}+(1-2\delta)\cdot imp _{lg_{u}}\); (b) \(\frac{d\Phi_{uu}}{dt}\leq-\frac{s_{uu}}{\left(2-2\delta\right)}\left(\frac{imp_ {lg_{u}}}{imp_{uu}}\right)\)  
**Proof. ** If \(n_{a}>m\) then:  
(a) It is required to upper-bound \(\frac{d\Phi_{uu}}{dt}\) for a processor \(u\). To calculate the upper-bound, the worst-case is considered which occurs if Opt is executing a job on \(u\) with the largest coefficient \(c_{lg_{u}}\ =\ Imp_{lg_{u}}\)1-2\(\delta\). At this time, \(\omega_{i}\) increases at the rate of \(s_{uu}\) (because of Opt on \(u\)). \[\frac{d\Phi_{uu}}{dt}\leq c_{lg_{u}}s_{uu}\ =\ Imp_{lg_{u}}\)1-2\(\delta\cdot s_{uu} \tag{12}\]  
Using [PERSON]'s inequality, Lemma 1 (Equation (6)) in (12) such that \(A=s_{uo}\), \(B=imp_{lg_{u}}\)1-2\(\delta\), \(x=\alpha\) and \(y=\frac{1}{1-2\delta}\) we have:  
\[\frac{d\Phi_{uo}}{dt}\leq\frac{s_{uu}\alpha}{\alpha}+(1-2\delta)\cdot imp_{lg _{u}} \tag{13}\]  
(b) Next, it is required to upper-bound \(\frac{d\Phi_{uu}}{dt}\) for a processor \(u\), to compute the upper-bound consider that a lagging job \(j_{i}\) on \(u\) is executed at the rate of \(\left(s_{uu}\cdot\frac{imp_{u}(j_{i})}{\sum_{k\ -1}^{n_{u}}imp_{u}(j_{k})}\right)\) or \(\left(s_{uu}\cdot\frac{imp_{u}(j_{i})}{imp_{uu}}\right)\), therefore the change in \(\omega_{i}\) is at the rate of \(\left(-s_{uu}\cdot\frac{imp_{u}(j_{i})}{imp_{uu}}\right)\). To make the discussion straightforward, let \(h_{ui}\ =\ \sum_{k\ -1}^{i}imp_{u}(j_{k})\), \(h_{u0}\ =\ 0\), \(h_{ulg_{u}}\ =\ Imp_{lg_{u}}\) and \(imp_{u}(j_{i})\ =\ h_{ui}-h_{ui-1}\). (by using Equation (3):  
\[ \begin{array}{ll}\frac{d\Phi_{uu}}{dt}&=\sum_{i=1}^{lg_{u}}\left(\left(\sum _{k\ -1}^{i}imp_{u}(j_{k})\right)^{1-2\delta}\right)\left(-s_{uu}\cdot\frac{imp_{u} (j_{i})}{imp_{uu}}\right)\\ &=-\frac{s_{uu}}{imp_{u}}\sum_{i=1}^{lg_{u}}\left(\left(h_{ui}\right)^{1-2 \delta}\right)\cdot\left(h_{ui}-h_{ui-1}\right)\\ &\leq-\frac{s_{uu}}{imp_{uu}}\sum_{i=1}^{lg_{u}}\int_{h_{ui-1}}^{h_{ui}}f^{1-2 \delta}\ df\\ &\leq-\frac{s_{uu}}{imp_{uu}}\sum_{i=1}^{lg_{u}}f^{1-2\delta}\ df\\ &\leq-\frac{s_{uu}}{imp_{uu}}\cdot\frac{h_{ulg_{u}}}{\left(2-2\delta\right)} \\ &=-\frac{s_{uu}}{imp_{uu}}\cdot\frac{imp_{lg_{u}}^{2-2\delta}}{\left(2-2\delta \right)}\\ \end{array} \]  
\[\frac{d\Phi_{uu}}{dt}\leq-\frac{s_{uu}}{(2-2\delta)}\left(\frac{imp_{lg_{u}}^{ 2-2\delta}}{imp_{uu}}\right) \tag{14}\]  
\(\Box\)  
**Lemma 5.