Computing majority with triple queries

Motivated from the well-known problem of establishing efficient diagnostic techniques for detecting faults in fault-tolerant computer systems we study a problem for computing majority with restricted tests in a set of items of two types (e.g., faulty and non-faulty). Stated in a more abstract form, consider a bin containing n balls colored with two colors. In a k-query, k balls are selected by a questioner and an oracle gives an answer which (depending on the computation model being considered) is related to the distribution of colors of the balls in this k-tuple. The oracle never reveals the colors of the individual balls. Following a number of queries and answers the questioner is said to determine majority if either (1) it can output a ball of the majority color provided that such a color exists, or (2) otherwise can determine that there is no majority color. We investigate the minimum number of queries required to determine majority in two computation models. We give algorithms to compute the minimum number of 3-queries which are needed so that the questioner can determine the majority color and provide tight and almost tight upper and lower bounds on the number of queries needed in each case. Our results indicate a surprising difference between the number of queries to determine majority with double versus triple queries.