Use of transaction agents to perform distributed transactions. According to one embodiment of the invention a coordinator transaction agent that includes an itinerary and a state machine is instantiated. The itinerary indicates a plurality of network elements and the plurality of network elements is in communication with the coordinator transaction agent. The coordinator transaction agent causes itself to be replicated onto the plurality of network elements according to the itinerary. Each of the replicated transaction agents causing an indication of their replication to be communicated back to the coordinator transaction agent. The coordinator transaction agent coordinating operations of the state machine in each of the replicated transaction agents to implement a distributed state machine.