  Given the proximity of many wireless users and their diversity in consuming
local resources (e.g., data-plans, computation and energy resources),
device-to-device (D2D) resource sharing is a promising approach towards
realizing a sharing economy. This paper adopts an easy-to-implement greedy
matching algorithm with distributed fashion and only sub-linear O(log n)
parallel complexity (in user number n) for large-scale D2D sharing. Practical
cases indicate that the greedy matching's average performance is far better
than the worst-case approximation ratio 50% as compared to the optimum.
However, there is no rigorous average-case analysis in the literature to back
up such encouraging findings and this paper is the first to present such
analysis for multiple representative classes of graphs. For 1D linear networks,
we prove that our greedy algorithm performs better than 86.5% of the optimum.
For 2D grids, though dynamic programming cannot be directly applied, we still
prove this average performance ratio to be above 76%. For the more challenging
Erdos-Renyi random graphs, we equivalently reduce to the asymptotic analysis of
random trees and successfully prove a ratio up to 79%. Finally, we conduct
experiments using real data to simulate realistic D2D networks, and show that
our analytical performance measure approximates well practical cases.
