Robust decoding for timing channels

To transmit information by timing arrivals to a single-server queue, we con sider using the exponential server channel's maximum-likelihood decoder, Fo r any server with service times that are stationary and ergodic with mean 1 /mu seconds, we show that the rate e(-1)mu nats per second (capacity of the exponential server timing channel) is achievable using this decoder. We sh ow that a similar result holds for the timing channel with feedback. We als o show that if the server jams communication by adding an arbitrary amount of time to the nominal service time, then the rate e(-1)mu(1)mu(2)/(mu(1) mu(2)) nats per second is achievable with random codes, where the nominal service times are stationary and ergodic with mean 1/mu(1) seconds, and the arithmetic mean of the delays added by the server does not exceed 1/mu(2) seconds. This is a model of an arbitrarily varying channel where the curren t delay and the current input can affect future outputs. We also show the c ounterpart of these results for single-server discrete-time queues.