Is suitable the byzantine generals problem to solve a problem with the report of availability of stroke unit beds?

Question

We are working in a Emergency Medical Service (EMS), wich carries patients in ambulance to the hospital. We are very concerned with the stroke in our community, because we have few beds for many stroke patients. Our problem is:

1. We have 9 hospitals with stroke units.
2. Each hospital has 4 beds in its unit.
3. Each year we have about 2000 stroke code activations, and each patient must be in a stroke unit about 4 days. There are about 2000 stroke patients that not arrive using the EMS.
4. We should transfer each stroke to a stroke unit with a bed available, if not there is a system fault and the consecuence is the activation of one aditional ambulance that must transfer the patient between hospitals (to a hospital wich has a free stroke unit bed) with the consequent loss of time.
5. Each hospital must call the EMS coordinator when its unit is full. When it releases a patient (so the unit has free beds), each hospital must call the EMS coordinator as well.

We have "enough beds" to cover the system, but we have many "system faults". We are looking for a trustless system with error tolerance, to communicate the beds avalilbility (like cryptocurrency trustless system), because:

1. Maybe there are errors with the communication system (call by phone, unsigned).
2. Negligent staff members of stroke unit may report that the unit is full when it is not actually full.
3. Negligent staff members of stroke unit may also delay the report of the release of unit beds.

I ask this because the problem is similar to the Byzantine generals one ...

Using the role of the game theory, is there a solution (maybe with signed messages) where we can reduce the possibility of error in the availability of beds in stroke units, using a communication system that maybe has errors because some staff maybe does not behave frankly?

Answer 1

This is not an answer to the question you asked, but instead an answer to a question that I suspect that you should have asked:

You've got $8000$ days of bed-use ($2000$ stroke patients times $4$ days).

You've got $13140$ days of beds ($9$ hospitals, $4$ beds each, $365$ days).

If your patient-arrival pattern was completely uniform, you'd have about $60\%$ occupancy. If there's even a modest variation, then even if you always knew what beds were available, you'd find yourself oversubscribed quite often.

I don't think your problem is an algorithmic one.

Here's the (very simple) simulation code, and some typical output. In this code, I simulate the uniformly random arrival of 4000 patients per year, and simply imagine that there's a single hospital with 36 stroke beds, and that when more than 36 stroke patients are present, they convert beds to stroke-beds.

function census_plot()
close all;
years = 4; % 3 year simulation.
days = years * 365;
count = zeros(days, 1); 
patients = 4000 * years; 
beds = 36;

initial = floor(.6 * 36); % start year with 60% occupancy of beds. 
count(1) = initial; % each patient may have been here from 1-4 days already
count(2) = 0.75 * initial;
count(3) = 0.5 * initial;
count(4) = 0.25 * initial;

arrival_dates = randi(days, [patients, 1]);
arrivals = zeros(days, 1);
for i = 1:patients
    arrivals(arrival_dates(i)) = arrivals(arrival_dates(i)) + 1;
end
plot(arrivals);
title('daily arrivals');
disp (['max arrivals: ', num2str(max(arrivals))]);
q = arrivals + [0; arrivals(1:end-1)] +...
    [0;0; arrivals(1:end-2)] + [0;0;0; arrivals(1:end-3)];
% q contains the number of patients (aside from the initial batch) 
% in beds on each day
disp(['max census: ' , num2str(max(q))]);
count = count + q; % and that's the total. 
figure;
plot(1:days, count, 'b', [1, days], [beds, beds], 'r');
title('daily census');
figure(gcf);
disp(['mean census: ', num2str(mean(count))]);
disp(['number of days over max census: ', num2str(sum(count>beds))]);
disp(['fraction of days over max census: ', num2str(sum(count>beds))/days]);

And here's the output from a typical run: Arrivals (in number of patients per day):

Census (i.e., number of beds occupied by stroke-patients. The red line indicates the number of stroke-beds.