Dynamic Analysis of the Arrow Distributed Protocol*

ABSTRACT Arrow is a prominent distributed protocol which globally orders requests initiated by the nodes in a distributed system. In this paper we present a dynamic analysis of the Arrow protocol. We prove that Arrow is O(log D)-competitive, where D is the diameter of the spanning tree on which Arrow operates. In addition, we show that our analysis is almost tight by proving that for all trees the competitive ratio of Arrow is \Omega (log D / log log D)