Az informatikában az exponenciális visszalépés (angolul exponential backoff) olyan algoritmus, amely egy folyamat erőforrásfelhasználását egy exponenciális függvény szerint csökkenti, amíg az el nem éri az elfogadható mértéket.
Egyik leggyakoribb alkalmazása a hálózatok tervezésénél a torlódáselkerülésre használt kettes exponenciális visszalépés protokoll (binary exponential back-off algorithm). Például egy LAN egy ütközési tartományában lévő számítógépek adni próbálnak a csatornán, majd ütközés esetén egy adott tartományból választanak egy véletlen időtartamot és ennek lejárta előtt nem próbálkoznak újra adással. Amennyiben újabb ütközés van, a véletlen várakozási idők meghatározására használt tartományt minden alkalommal megduplázzák.
Például az Ethernet protokoll esetében a visszalépési időt véletlenszerűen választják a:
tartományból, ahol az alap várakozási idő: Ethernet esetén 51,2 μs, Fast Ethernetnél, 5,12 μs és , ahol az ütközések száma. Mivel a várakozási idő várható értéke 10 ütközés után már nem növekszik, ezt a változatot csonkolt bináris exponenciális visszalépés algoritmusnak (truncated binary exponential backoff) nevezik.
Források Seok-Kyu Kweon, Kang G. Shin: Statistical Real-Time Communication over Ethernet (PDF), acm.org
Kategória:Algoritmusok