A distributed system with transaction support may have a transaction component and one or more data components. The transaction component may manage a transaction using a log sequence number for each operation, and then transmit operations to one or more data components with log sequence numbers. The data components may perform the data operations in an idempotent manner and return a reply. The transaction component may then write the operation, its log sequence number, and information from the reply message to its log. The transaction component is able to commit a transaction, as well as retry or undo portions of a transaction, by using the information stored on its log. This may be possible even when a single transaction uses multiple data components, which may be located on different devices or manage separate and independent data sources.