While cloud computing is the current standard for outsourcing computation, it can be prohibitively expensive for cities and infrastructure operators to deploy services, especially for streaming applications. At the same time, there are underutilized computing resources within cities and local edge-computing deployments. Using these slack resources may enable significantly lower pricing than comparable cloud computing; such resources would incur minimal marginal expenditure since their deployment and operation are mostly sunk costs. However, there are challenges associated with using these resources. First, they are not effectively aggregated or provisioned. Second, there is a lack of trust between customers and suppliers of computing resources, given that they are distinct stakeholders and behave according to their own interests. Third, delays in processing inputs may diminish the value of the streaming applications. To resolve these challenges, we introduce an architecture, combining a distributed trusted computing base, such as a blockchain, with an efficient messaging system like Apache Pulsar. Using this architecture, we design a decentralized computation market where customers and suppliers make offers to deploy and host streaming applications. The proposed architecture is independent of any particular blockchain implementation—as long as it supports smart contracts—and ensures that the market is robust to failures, while incurring the latency intrinsic in blockchain solutions only on deployment, rather than every output. We evaluate the market protocol using game-theoretic analysis to show that deviation from the protocol is discouraged. Finally, we evaluate the performance of a prototype implementation based on experiments with a streaming computer-vision application.