W3C home > Mailing lists > Public > public-interledger@w3.org > June 2017

Alternative algorithm for timeouts

From: Enrique Arizon Benito <enrique.arizon.benito@everis.com>
Date: Fri, 30 Jun 2017 12:07:00 +0000
To: "public-interledger@w3.org" <public-interledger@w3.org>
Message-ID: <C23179174213FF4A8B0ADF823E0D2DD0C93E8177@MBXEUR04.usersad.everis.int>
At this moment the algorithm to establish a timeout is something like:

  1.  start transaction
  2.  set timeout as "NOW" + Constant_Timeout_time
  3.  wait
  4.  "NOW" > timeout
     *   YES -> timeout transaction
     *   NOW -> Got to 3

This introduces random false timeouts due to race-conditions. It could be possible for the receiving ledger to execute the transfer and for the originating ledger to time out due to the finite time to propagate the fulfillment back through all connectors.

I think next alternative algorithm minimized (nearly avoids) all false timeouts due to race conditions?

- The sending ledger keeps a list of txs not yet executed (that can timeout)  *for each* destination ledger.

   Those txs are stored in an ordered list acording to the sending time [tx1, tx2, tx3, tx4, ...]

- When tx"M" with M = N + K arrives, a timeout is established for tx"N" for each "N" < M - K

- Finally after a given timeout,  tx"N" is cancelled

Said it otherway:

-  transaction in the list does NOT time-out unless two next condition happens:

  - tx"M" fulfillment with M > N + K has arrived

  - tx"N" has timed out.

The logic is next:

 - It's possible that at some point there is an overload in the destination ledger. At this point the average time to process the incomming transfer, executing and returning the fulfillment will increase approaching the initial timeout. The closer it is to the timeout the more probable for race condition during the "travel back".

- Due to the destination ledger system overload, is quite possible that all TXs are delayed and it makes sense for the originating ledger to wait more than ussual.
- Suppose now that tx"M" arrives. At this moment sending ledger setup a timeout for each tx"N" with N < M - K.

  It's quite sensible to think that if there was a system overload in the destination ledger once it's back to normal all pending transfer will arrive shortly after.

  It's also quite sensible to think that if tx"M" arrives, and timeout passes, most probably tx"N" has really timeout (it never reached the destinantion ledger) and that no race condition will arise since they never reached the destination ledger.




Este correo y la información contenida o adjunta al mismo es privada y confidencial y va dirigida exclusivamente a su destinatario. everis informa a quien pueda haber recibido este correo por error que contiene información confidencial cuyo uso, copia, reproducción o distribución está expresamente prohibida. Si no es Vd. el destinatario del mismo y recibe este correo por error, le rogamos lo ponga en conocimiento del emisor y proceda a su eliminación sin copiarlo, imprimirlo o utilizarlo de ningún modo.

This message and the information contained in or attached to it are private and confidential and intended exclusively for the addressee. everis informs to whom it may receive it in error that it contains privileged information and its use, copy, reproduction or distribution is prohibited. If you are not an intended recipient of this E-mail, please notify the sender, delete it and do not read, act upon, print, disclose, copy, retain or redistribute any portion of this E-mail.
Received on Friday, 30 June 2017 12:07:31 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 16:14:08 UTC