Project P127
Timeout budget
A request through four hops, bounded by a fixed timeout for every caller or by the user's deadline passed down: the same wait and answer for the user, but only the fixed timeouts leave work running that nobody waits for.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-17
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
A request passes through hops A, B, C and D. Each does its own work, then calls the next and waits for its reply. Two ways to bound the wait: a fixed timeout for every caller, or the user's deadline passed down.
main.eml- the menu, the hops, one request under both schemes event by event, both side by side, one hop slower and slower, and the settingshops.eml- the hops' start times, the fixed scheme, the work done after someone stopped waiting, the deadline scheme, and a summary
How each part works:
- As in the corpus case
timeout-budget-across-hops: - fixed: every caller waits at most the timeout for its callee. A hop that gives up cannot stop the hops below it, which keep working; - budget: the user's deadline, the same number, is passed down. No hop starts after it, and work still running at the deadline stops there. - Times are milliseconds from the user's call. With A 400, B 600, C 800 and D 1000 and a timeout of 5000, both schemes answer in 2800 ms. With D at 8000, both fail at 5000 ms; under fixed timeouts D works on to 9800 ms, 4800 ms of work after the user has given up.
- The user waits the same time and gets the same answer under both schemes, whatever the hops do. The fixed scheme leaves work running after someone above stopped waiting exactly when the request fails; the deadline never does.
- As in the corpus case
timeout-vs-completion, a timeout is a fact about the caller: under fixed timeouts the user is told the request failed, and every hop still does all its work.
What is checked: menu choices 1 to 7; a hop A, B, C or D; a hop's work from 0 to 20000 ms; a timeout from 100 to 20000 ms. An empty answer cancels.
Sessions: sessions/basic.in gives: - the hops and one request, both schemes answering in 2800 ms; - D slower and slower, from 0 to 10000 ms; - D at 8000 ms: one request, event by event; - a timeout of 3000 ms, side by side.
sessions/bad-input.in gives: - menu choices 0 and x; - hops: a cancel and E for the sweep, a cancel and Z to set; - work for A: a cancel, 20001 and x; timeouts: a cancel, 99, 20001 and abc; - A at 0 ms with a timeout of 100 ms: A replies "failed" to the user just in time, while B, C and D work on.
Built on the verified corpus cases timeout-budget-across-hops (per-hop timeouts add up, and a deadline passed down stops the waste) and timeout-vs-completion (the client gives up; the server finishes anyway).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Timeout budget ==
A request through hops A, B, C and D, each doing its own work and then waiting for the next, bounded by fixed timeouts or by a deadline passed down.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 0
Pick a number from 1 to 7.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> x
Pick a number from 1 to 7.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 4
hop (A, B, C or D)>
Cancelled.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 4
hop (A, B, C or D)> E
Type A, B, C or D.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 5
hop (A, B, C or D)>
Cancelled.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 5
hop (A, B, C or D)> Z
Type A, B, C or D.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 5
hop (A, B, C or D)> A
work (0 to 20000 ms)>
Cancelled.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 5
hop (A, B, C or D)> A
work (0 to 20000 ms)> 20001
Type a whole number from 0 to 20000.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 5
hop (A, B, C or D)> A
work (0 to 20000 ms)> x
Type a whole number from 0 to 20000.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 6
timeout (100 to 20000 ms)>
Cancelled.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 6
timeout (100 to 20000 ms)> 99
Type a whole number from 100 to 20000.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 6
timeout (100 to 20000 ms)> 20001
Type a whole number from 100 to 20000.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 6
timeout (100 to 20000 ms)> abc
Type a whole number from 100 to 20000.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 5
hop (A, B, C or D)> A
work (0 to 20000 ms)> 0
A now works 0 ms.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 6
timeout (100 to 20000 ms)> 100
Timeout and deadline now 100 ms.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 2
Fixed timeouts:
0 ms the user calls A, and waits up to 100 ms
0 ms A starts its work, 0 ms
0 ms A calls B, and waits up to 100 ms
0 ms B starts its work, 600 ms
100 ms A gives up on B, and replies: failed
100 ms A replies to the user: failed
600 ms B calls C, and waits up to 100 ms
600 ms C starts its work, 800 ms
700 ms B gives up on C, and replies: failed
700 ms B replies to A, which has already given up
1400 ms C calls D, and waits up to 100 ms
1400 ms D starts its work, 1000 ms
1500 ms C gives up on D, and replies: failed
1500 ms C replies to B, which has already given up
2400 ms D finishes its work
2400 ms D replies to C, which has already given up
A deadline passed down:
0 ms the user calls A, with a deadline at 100 ms
0 ms A starts its work, 0 ms, with 100 ms left
0 ms A calls B
0 ms B starts its work, 600 ms, with 100 ms left
100 ms B stops at the deadline, 500 ms of its work not done
100 ms the deadline: the request failed, and no work runs past it
fixed: the user waits 100 ms, failed; 2300 ms of work done after someone above had stopped waiting
the user is told it failed, yet every hop does all its work
budget: the user waits 100 ms, failed; 2 of 4 hops started, no work after the deadline
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 7
Bye.
What was typed (34 lines)
0
x
4
4
E
5
5
Z
5
A
5
A
20001
5
A
x
6
6
99
6
20001
6
abc
5
A
0
6
100
2
7
basic
interpreter: byte-equal== Timeout budget ==
A request through hops A, B, C and D, each doing its own work and then waiting for the next, bounded by fixed timeouts or by a deadline passed down.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 1
Each hop's own work: A 400 ms, B 600 ms, C 800 ms, D 1000 ms; 2800 ms in all when nothing waits.
Timeout: every caller waits up to 5000 ms (fixed), or the user's deadline of 5000 ms is passed down (budget).
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 2
Fixed timeouts:
0 ms the user calls A, and waits up to 5000 ms
0 ms A starts its work, 400 ms
400 ms A calls B, and waits up to 5000 ms
400 ms B starts its work, 600 ms
1000 ms B calls C, and waits up to 5000 ms
1000 ms C starts its work, 800 ms
1800 ms C calls D, and waits up to 5000 ms
1800 ms D starts its work, 1000 ms
2800 ms D finishes its work
2800 ms D replies to C: ok
2800 ms C replies to B: ok
2800 ms B replies to A: ok
2800 ms A replies to the user: ok
A deadline passed down:
0 ms the user calls A, with a deadline at 5000 ms
0 ms A starts its work, 400 ms, with 5000 ms left
400 ms A calls B
400 ms B starts its work, 600 ms, with 4600 ms left
1000 ms B calls C
1000 ms C starts its work, 800 ms, with 4000 ms left
1800 ms C calls D
1800 ms D starts its work, 1000 ms, with 3200 ms left
2800 ms D finishes its work
2800 ms the user gets the reply: ok
fixed: the user waits 2800 ms, ok; 0 ms of work done after someone above had stopped waiting
budget: the user waits 2800 ms, ok; 4 of 4 hops started, no work after the deadline
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 4
hop (A, B, C or D)> D
D slower and slower, the others as they are, timeout 5000 ms:
D's work fixed: wait result wasted budget: wait result hops
0 1800 ok 0 1800 ok 4
1000 2800 ok 0 2800 ok 4
2000 3800 ok 0 3800 ok 4
3000 4800 ok 0 4800 ok 4
4000 5000 failed 800 5000 failed 4
5000 5000 failed 1800 5000 failed 4
6000 5000 failed 2800 5000 failed 4
7000 5000 failed 3800 5000 failed 4
8000 5000 failed 4800 5000 failed 4
9000 5000 failed 5800 5000 failed 4
10000 5000 failed 6800 5000 failed 4
Both wait the same; only the fixed timeouts leave work running that nobody waits for.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 5
hop (A, B, C or D)> D
work (0 to 20000 ms)> 8000
D now works 8000 ms.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 2
Fixed timeouts:
0 ms the user calls A, and waits up to 5000 ms
0 ms A starts its work, 400 ms
400 ms A calls B, and waits up to 5000 ms
400 ms B starts its work, 600 ms
1000 ms B calls C, and waits up to 5000 ms
1000 ms C starts its work, 800 ms
1800 ms C calls D, and waits up to 5000 ms
1800 ms D starts its work, 8000 ms
5000 ms the user gives up: the request failed
5400 ms A gives up on B, and replies: failed
5400 ms A replies to the user, who has already given up
6000 ms B gives up on C, and replies: failed
6000 ms B replies to A, which has already given up
6800 ms C gives up on D, and replies: failed
6800 ms C replies to B, which has already given up
9800 ms D finishes its work
9800 ms D replies to C, which has already given up
A deadline passed down:
0 ms the user calls A, with a deadline at 5000 ms
0 ms A starts its work, 400 ms, with 5000 ms left
400 ms A calls B
400 ms B starts its work, 600 ms, with 4600 ms left
1000 ms B calls C
1000 ms C starts its work, 800 ms, with 4000 ms left
1800 ms C calls D
1800 ms D starts its work, 8000 ms, with 3200 ms left
5000 ms D stops at the deadline, 4800 ms of its work not done
5000 ms the deadline: the request failed, and no work runs past it
fixed: the user waits 5000 ms, failed; 4800 ms of work done after someone above had stopped waiting
the user is told it failed, yet every hop does all its work
budget: the user waits 5000 ms, failed; 4 of 4 hops started, no work after the deadline
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 6
timeout (100 to 20000 ms)> 3000
Timeout and deadline now 3000 ms.
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 3
fixed: the user waits 3000 ms, failed; 6800 ms of work done after someone above had stopped waiting
the user is told it failed, yet every hop does all its work
budget: the user waits 3000 ms, failed; 4 of 4 hops started, no work after the deadline
1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit
choice> 7
Bye.
What was typed (12 lines)
1
2
4
D
5
D
8000
2
6
3000
3
7
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P127 timeout budget: the hops, one request under fixed timeouts and under
# a passed-down deadline, both side by side, one hop slower and slower, and
# the settings.
import hops
def plain(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def pad(s, n):
s => out
while len(out) < n:
out + " " => out
return out
def lpad(s, n):
s => out
while len(out) < n:
" " + out => out
return out
def ok_text(ok):
if ok:
return "ok"
return "failed"
def show(work, t):
"" => line
0 => total
for i in [0:3]:
if line != "":
line + ", " => line
line + hops.names()[i] + " " + str(work[i]) + " ms" => line
total + work[i] => total
("Each hop's own work: " + line + "; " + str(total) + " ms in all when nothing waits.") ^0
("Timeout: every caller waits up to " + str(t) + " ms (fixed), or the user's deadline of " + str(t) + " ms is passed down (budget).") ^0
def order(ev):
# events sorted by time; events at the same time keep their order
[] => out
for e in ev:
[] => nxt
False => placed
for x in out:
if not placed and e[0] < x[0]:
nxt + [e] => nxt
True => placed
nxt + [x] => nxt
if not placed:
nxt + [e] => nxt
nxt => out
return out
def print_events(ev):
for e in order(ev):
(" " + lpad(str(e[0]), 6) + " ms " + e[1]) ^0
def timeline_fixed(work, t):
hops.fixed(work, t) => r
r[0] => hs
hops.names() => nm
[[0, "the user calls A, and waits up to " + str(t) + " ms"]] => ev
for i in [0:3]:
ev + [[hs[i][0], nm[i] + " starts its work, " + str(work[i]) + " ms"]] => ev
if i < 3:
ev + [[hs[i][1], nm[i] + " calls " + nm[i + 1] + ", and waits up to " + str(t) + " ms"]] => ev
ev + [[hs[3][1], "D finishes its work"]] => ev
for j in [0:2]:
2 - j => i
if hs[i][4] >= 0:
ev + [[hs[i][4], nm[i] + " gives up on " + nm[i + 1] + ", and replies: failed"]] => ev
ev + [[hs[i + 1][2], nm[i + 1] + " replies to " + nm[i] + ", which has already given up"]] => ev
else:
ev + [[hs[i + 1][2], nm[i + 1] + " replies to " + nm[i] + ": " + ok_text(hs[i + 1][3])]] => ev
if r[1][2] >= 0:
ev + [[t, "the user gives up: the request failed"]] => ev
ev + [[hs[0][2], "A replies to the user, who has already given up"]] => ev
else:
ev + [[hs[0][2], "A replies to the user: " + ok_text(r[1][1])]] => ev
"Fixed timeouts:" ^0
print_events(ev)
def timeline_budget(work, t):
hops.budget(work, t) => r
r[0] => hs
hops.names() => nm
[[0, "the user calls A, with a deadline at " + str(t) + " ms"]] => ev
False => stopped
for i in [0:3]:
if not stopped:
if hs[i][0] < 0:
ev + [[t, nm[i] + " is not started: the deadline has come"]] => ev
True => stopped
else:
ev + [[hs[i][0], nm[i] + " starts its work, " + str(work[i]) + " ms, with " + str(t - hs[i][0]) + " ms left"]] => ev
if not hs[i][2]:
ev + [[t, nm[i] + " stops at the deadline, " + str(hs[i][0] + work[i] - t) + " ms of its work not done"]] => ev
True => stopped
elif i < 3:
ev + [[hs[i][1], nm[i] + " calls " + nm[i + 1]]] => ev
else:
ev + [[hs[i][1], "D finishes its work"]] => ev
if r[1][1]:
ev + [[r[1][0], "the user gets the reply: ok"]] => ev
else:
ev + [[t, "the deadline: the request failed, and no work runs past it"]] => ev
"A deadline passed down:" ^0
print_events(ev)
def summary_lines(work, t):
hops.summary(work, t) => s
s[0] => f
s[1] => b
(" fixed: the user waits " + str(f[0]) + " ms, " + ok_text(f[1]) + "; " + str(f[2]) + " ms of work done after someone above had stopped waiting") ^0
if not f[1]:
" the user is told it failed, yet every hop does all its work" ^0
(" budget: the user waits " + str(b[0]) + " ms, " + ok_text(b[1]) + "; " + str(b[2]) + " of 4 hops started, no work after the deadline") ^0
def sweep(work, t):
plain(input("hop (A, B, C or D)> ")) => h
if h == "":
"Cancelled." ^0
return
0 - 1 => k
for i in [0:3]:
if hops.names()[i] == h:
i => k
if k < 0:
"Type A, B, C or D." ^0
return
(h + " slower and slower, the others as they are, timeout " + str(t) + " ms:") ^0
" " + pad(h + "'s work", 10) + " fixed: wait result wasted budget: wait result hops" ^0
for step in [0:10]:
[] => w
for i in [0:3]:
if i == k:
w + [step * 1000] => w
else:
w + [work[i]] => w
hops.summary(w, t) => s
(" " + lpad(str(step * 1000), 10) + lpad(str(s[0][0]), 14) + " " + pad(ok_text(s[0][1]), 6) + lpad(str(s[0][2]), 8) + lpad(str(s[1][0]), 15) + " " + pad(ok_text(s[1][1]), 6) + lpad(str(s[1][2]), 6)) ^0
"Both wait the same; only the fixed timeouts leave work running that nobody waits for." ^0
def ask_ms(prompt, low, high):
plain(input(prompt)) => t
if t == "":
"Cancelled." ^0
return 0 - 1
if len(t) > 5:
("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0
return 0 - 1
for c in t:
if c < "0" or c > "9":
("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0
return 0 - 1
if int(t) < low or int(t) > high:
("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0
return 0 - 1
return int(t)
def set_work(work):
plain(input("hop (A, B, C or D)> ")) => h
if h == "":
"Cancelled." ^0
return work
0 - 1 => k
for i in [0:3]:
if hops.names()[i] == h:
i => k
if k < 0:
"Type A, B, C or D." ^0
return work
ask_ms("work (0 to 20000 ms)> ", 0, 20000) => w
if w < 0:
return work
[] => out
for i in [0:3]:
if i == k:
out + [w] => out
else:
out + [work[i]] => out
(h + " now works " + str(w) + " ms.") ^0
return out
[400, 600, 800, 1000] => work
5000 => t
"== Timeout budget ==" ^0
"A request through hops A, B, C and D, each doing its own work and then waiting for the next, bounded by fixed timeouts or by a deadline passed down." ^0
True => running
while running:
"" ^0
"1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
show(work, t)
elif choice == "2":
timeline_fixed(work, t)
timeline_budget(work, t)
summary_lines(work, t)
elif choice == "3":
summary_lines(work, t)
elif choice == "4":
sweep(work, t)
elif choice == "5":
set_work(work) => work
elif choice == "6":
ask_ms("timeout (100 to 20000 ms)> ", 100, 20000) => x
if x >= 0:
x => t
("Timeout and deadline now " + str(t) + " ms.") ^0
elif choice == "7":
False => running
else:
"Pick a number from 1 to 7." ^0
"Bye." ^0
Python projection (main.py)
import hops
def plain(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def pad(s, n):
out = s
while len(out) < n:
out = out + " "
return out
def lpad(s, n):
out = s
while len(out) < n:
out = " " + out
return out
def ok_text(ok):
if ok:
return "ok"
return "failed"
def show(work, t):
line = ""
total = 0
for i in range(0, 4):
if line != "":
line = line + ", "
line = line + hops.names()[i] + " " + str(work[i]) + " ms"
total = total + work[i]
print("Each hop's own work: " + line + "; " + str(total) + " ms in all when nothing waits.")
print("Timeout: every caller waits up to " + str(t) + " ms (fixed), or the user's deadline of " + str(t) + " ms is passed down (budget).")
def order(ev):
out = []
for e in ev:
nxt = []
placed = False
for x in out:
if not placed and e[0] < x[0]:
nxt = nxt + [e]
placed = True
nxt = nxt + [x]
if not placed:
nxt = nxt + [e]
out = nxt
return out
def print_events(ev):
for e in order(ev):
print(" " + lpad(str(e[0]), 6) + " ms " + e[1])
def timeline_fixed(work, t):
r = hops.fixed(work, t)
hs = r[0]
nm = hops.names()
ev = [[0, "the user calls A, and waits up to " + str(t) + " ms"]]
for i in range(0, 4):
ev = ev + [[hs[i][0], nm[i] + " starts its work, " + str(work[i]) + " ms"]]
if i < 3:
ev = ev + [[hs[i][1], nm[i] + " calls " + nm[i + 1] + ", and waits up to " + str(t) + " ms"]]
ev = ev + [[hs[3][1], "D finishes its work"]]
for j in range(0, 3):
i = 2 - j
if hs[i][4] >= 0:
ev = ev + [[hs[i][4], nm[i] + " gives up on " + nm[i + 1] + ", and replies: failed"]]
ev = ev + [[hs[i + 1][2], nm[i + 1] + " replies to " + nm[i] + ", which has already given up"]]
else:
ev = ev + [[hs[i + 1][2], nm[i + 1] + " replies to " + nm[i] + ": " + ok_text(hs[i + 1][3])]]
if r[1][2] >= 0:
ev = ev + [[t, "the user gives up: the request failed"]]
ev = ev + [[hs[0][2], "A replies to the user, who has already given up"]]
else:
ev = ev + [[hs[0][2], "A replies to the user: " + ok_text(r[1][1])]]
print("Fixed timeouts:")
print_events(ev)
def timeline_budget(work, t):
r = hops.budget(work, t)
hs = r[0]
nm = hops.names()
ev = [[0, "the user calls A, with a deadline at " + str(t) + " ms"]]
stopped = False
for i in range(0, 4):
if not stopped:
if hs[i][0] < 0:
ev = ev + [[t, nm[i] + " is not started: the deadline has come"]]
stopped = True
else:
ev = ev + [[hs[i][0], nm[i] + " starts its work, " + str(work[i]) + " ms, with " + str(t - hs[i][0]) + " ms left"]]
if not hs[i][2]:
ev = ev + [[t, nm[i] + " stops at the deadline, " + str(hs[i][0] + work[i] - t) + " ms of its work not done"]]
stopped = True
elif i < 3:
ev = ev + [[hs[i][1], nm[i] + " calls " + nm[i + 1]]]
else:
ev = ev + [[hs[i][1], "D finishes its work"]]
if r[1][1]:
ev = ev + [[r[1][0], "the user gets the reply: ok"]]
else:
ev = ev + [[t, "the deadline: the request failed, and no work runs past it"]]
print("A deadline passed down:")
print_events(ev)
def summary_lines(work, t):
s = hops.summary(work, t)
f = s[0]
b = s[1]
print(" fixed: the user waits " + str(f[0]) + " ms, " + ok_text(f[1]) + "; " + str(f[2]) + " ms of work done after someone above had stopped waiting")
if not f[1]:
print(" the user is told it failed, yet every hop does all its work")
print(" budget: the user waits " + str(b[0]) + " ms, " + ok_text(b[1]) + "; " + str(b[2]) + " of 4 hops started, no work after the deadline")
def sweep(work, t):
h = plain(input("hop (A, B, C or D)> "))
if h == "":
print("Cancelled.")
return
k = 0 - 1
for i in range(0, 4):
if hops.names()[i] == h:
k = i
if k < 0:
print("Type A, B, C or D.")
return
print(h + " slower and slower, the others as they are, timeout " + str(t) + " ms:")
print(" " + pad(h + "'s work", 10) + " fixed: wait result wasted budget: wait result hops")
for step in range(0, 11):
w = []
for i in range(0, 4):
if i == k:
w = w + [step * 1000]
else:
w = w + [work[i]]
s = hops.summary(w, t)
print(" " + lpad(str(step * 1000), 10) + lpad(str(s[0][0]), 14) + " " + pad(ok_text(s[0][1]), 6) + lpad(str(s[0][2]), 8) + lpad(str(s[1][0]), 15) + " " + pad(ok_text(s[1][1]), 6) + lpad(str(s[1][2]), 6))
print("Both wait the same; only the fixed timeouts leave work running that nobody waits for.")
def ask_ms(prompt, low, high):
t = plain(input(prompt))
if t == "":
print("Cancelled.")
return 0 - 1
if len(t) > 5:
print("Type a whole number from " + str(low) + " to " + str(high) + ".")
return 0 - 1
for c in t:
if c < "0" or c > "9":
print("Type a whole number from " + str(low) + " to " + str(high) + ".")
return 0 - 1
if int(t) < low or int(t) > high:
print("Type a whole number from " + str(low) + " to " + str(high) + ".")
return 0 - 1
return int(t)
def set_work(work):
h = plain(input("hop (A, B, C or D)> "))
if h == "":
print("Cancelled.")
return work
k = 0 - 1
for i in range(0, 4):
if hops.names()[i] == h:
k = i
if k < 0:
print("Type A, B, C or D.")
return work
w = ask_ms("work (0 to 20000 ms)> ", 0, 20000)
if w < 0:
return work
out = []
for i in range(0, 4):
if i == k:
out = out + [w]
else:
out = out + [work[i]]
print(h + " now works " + str(w) + " ms.")
return out
work = [400, 600, 800, 1000]
t = 5000
print("== Timeout budget ==")
print("A request through hops A, B, C and D, each doing its own work and then waiting for the next, bounded by fixed timeouts or by a deadline passed down.")
running = True
while running:
print("")
print("1) hops 2) one request 3) side by side 4) one hop slower 5) set a hop 6) timeout 7) quit")
choice = plain(input("choice> "))
if choice == "1":
show(work, t)
elif choice == "2":
timeline_fixed(work, t)
timeline_budget(work, t)
summary_lines(work, t)
elif choice == "3":
summary_lines(work, t)
elif choice == "4":
sweep(work, t)
elif choice == "5":
work = set_work(work)
elif choice == "6":
x = ask_ms("timeout (100 to 20000 ms)> ", 100, 20000)
if x >= 0:
t = x
print("Timeout and deadline now " + str(t) + " ms.")
elif choice == "7":
running = False
else:
print("Pick a number from 1 to 7.")
print("Bye.")
hops.eml
eml# P127 timeout budget - a request passes through hops A, B, C and D: each
# does its own work, then calls the next and waits for its reply. As in the
# corpus case timeout-budget-across-hops, two ways to bound the wait:
# fixed every caller waits at most the timeout for its callee; a hop
# that gives up cannot stop the hops below it, which keep working;
# budget the user's deadline, the same timeout, is passed down; no hop
# starts after it, and work still running at the deadline stops.
# As in timeout-vs-completion, a timeout is a fact about the caller: under
# fixed timeouts the user can be told the request failed while every hop
# finishes its work anyway.
#
# Times are milliseconds from the user's call.
def names():
return ["A", "B", "C", "D"]
def starts(work):
[] => out
0 => s
for w in work:
out + [s] => out
s + w => s
return out
def fixed(work, t):
# per hop [start, end of its work, reply time, ok, gave up at or -1],
# and the user's [wait, ok, gave up at or -1]
len(work) => n
starts(work) => st
[] => hops
for i in [0:n - 1]:
hops + [[st[i], st[i] + work[i], st[i] + work[i], True, 0 - 1]] => hops
for j in [0:n - 2]:
n - 2 - j => i
hops[i][1] => call
if hops[i + 1][2] - call <= t:
hops[i + 1][2] => hops[i][2]
hops[i + 1][3] => hops[i][3]
else:
call + t => hops[i][2]
False => hops[i][3]
call + t => hops[i][4]
if hops[0][2] <= t:
return [hops, [hops[0][2], hops[0][3], 0 - 1]]
return [hops, [t, False, t]]
def wasted(work, t):
# milliseconds of work done after someone above that hop stopped waiting
fixed(work, t) => r
r[0] => hops
r[1][2] => cut
0 => total
for i in [0:len(work) - 1]:
if cut >= 0 and hops[i][1] > cut:
hops[i][1] - max2(hops[i][0], cut) => more
total + more => total
if hops[i][4] >= 0 and (cut < 0 or hops[i][4] < cut):
hops[i][4] => cut
return total
def max2(x, y):
if x > y:
return x
return y
def budget(work, d):
# per hop [start or -1 if never started, when its work ended or stopped,
# finished]; the user's [wait, ok]
starts(work) => st
[] => hops
0 => total
for i in [0:len(work) - 1]:
total + work[i] => total
if st[i] >= d:
hops + [[0 - 1, 0 - 1, False]] => hops
elif st[i] + work[i] > d:
hops + [[st[i], d, False]] => hops
else:
hops + [[st[i], st[i] + work[i], True]] => hops
if total <= d:
return [hops, [total, True]]
return [hops, [d, False]]
def summary(work, t):
# [fixed wait, ok, wasted, every hop's work done], [budget wait, ok,
# hops started, every hop's work done]
fixed(work, t)[1] => f
budget(work, t) => b
0 => started
True => done
for h in b[0]:
if h[0] >= 0:
started + 1 => started
if not h[2]:
False => done
return [[f[0], f[1], wasted(work, t), True], [b[1][0], b[1][1], started, done]]
Python projection (hops.py)
def names():
return ["A", "B", "C", "D"]
def starts(work):
out = []
s = 0
for w in work:
out = out + [s]
s = s + w
return out
def fixed(work, t):
n = len(work)
st = starts(work)
hops = []
for i in range(0, n):
hops = hops + [[st[i], st[i] + work[i], st[i] + work[i], True, 0 - 1]]
for j in range(0, n - 2+1):
i = n - 2 - j
call = hops[i][1]
if hops[i + 1][2] - call <= t:
hops[i][2] = hops[i + 1][2]
hops[i][3] = hops[i + 1][3]
else:
hops[i][2] = call + t
hops[i][3] = False
hops[i][4] = call + t
if hops[0][2] <= t:
return [hops, [hops[0][2], hops[0][3], 0 - 1]]
return [hops, [t, False, t]]
def wasted(work, t):
r = fixed(work, t)
hops = r[0]
cut = r[1][2]
total = 0
for i in range(0, len(work)):
if cut >= 0 and hops[i][1] > cut:
more = hops[i][1] - max2(hops[i][0], cut)
total = total + more
if hops[i][4] >= 0 and (cut < 0 or hops[i][4] < cut):
cut = hops[i][4]
return total
def max2(x, y):
if x > y:
return x
return y
def budget(work, d):
st = starts(work)
hops = []
total = 0
for i in range(0, len(work)):
total = total + work[i]
if st[i] >= d:
hops = hops + [[0 - 1, 0 - 1, False]]
elif st[i] + work[i] > d:
hops = hops + [[st[i], d, False]]
else:
hops = hops + [[st[i], st[i] + work[i], True]]
if total <= d:
return [hops, [total, True]]
return [hops, [d, False]]
def summary(work, t):
f = fixed(work, t)[1]
b = budget(work, t)
started = 0
done = True
for h in b[0]:
if h[0] >= 0:
started = started + 1
if not h[2]:
done = False
return [[f[0], f[1], wasted(work, t), True], [b[1][0], b[1][1], started, done]]