  In this paper, we investigate online distributed job dispatching in an edge
computing system residing in a Metropolitan Area Network (MAN). Specifically,
job dispatchers are implemented on access points (APs) which collect jobs from
mobile users and distribute each job to a server at the edge or the cloud. A
signaling mechanism with periodic broadcast is introduced to facilitate
cooperation among APs. The transmission latency is non-negligible in MAN, which
leads to outdated information sharing among APs. Moreover, the fully-observed
system state is discouraged as reception of all broadcast is time consuming.
Therefore, we formulate the distributed optimization of job dispatching
strategies among the APs as a Markov decision process with partial and outdated
system state, i.e., partially observable Markov Decision Process (POMDP). The
conventional solution for POMDP is impractical due to huge time complexity. We
propose a novel low-complexity solution framework for distributed job
dispatching, based on which the optimization of job dispatching policy can be
decoupled via an alternative policy iteration algorithm, so that the
distributed policy iteration of each AP can be made according to partial and
outdated observation. A theoretical performance lower bound is proved for our
approximate MDP solution. Furthermore, we conduct extensive simulations based
on the Google Cluster trace. The evaluation results show that our policy can
achieve as high as $20.67\%$ reduction in average job response time compared
with heuristic baselines, and our algorithm consistently performs well under
various parameter settings.
